Combinatorics Distribution - Number of integer solutions Concept Explanation

I reading my textbook and I don't understand the concept of distributions or number of solutions to an equation. It's explained that this problem is 1/4 types of sampling/distributions problems. An example is provided to illustrate:

In how many ways can 4 identical jobs (indistinguishable balls) be distributed among 26 members (urns) without exclusion (since one member can do multiple jobs)?

A sample outcome might be:
$\text{_____________}$
| A | B | C |...| Z |
$\text{--------------------}$

$\text{_____________}$
| o | oo| | | ||| o |
$\text{_____________}$
| A | B | C |... | Z |
$\text{--------------------}$

Thus, the question is reduced to, "How many $(26-1+4)$ letter words are there consisting of four circles and $(26-1)$ vertical lines?" Therefore, the solution is: $\binom{26-1+4}{4}$

I really don't understand why its $(26-1+4)$. There's only 26 different spots or "urns" to place the 4 jobs. Can someone please explain?

I looked through another text to try and understand and I found it explained as such:

There are $\binom{n+r-1}{r-1}$ distinct nonnegative integer valued vectors $(x_1,...,x_r$ satisfying the equation $(x_1 + ... + x_r = x_n$ for $x\ge0$. $\spadesuit$

How in the world are they deriving this? For distinct positive integers I understand:

Assume I have 8 balls (n=8) and I have 3 urns (r=3): o^o^o^o^o^o^o^o, where o represents a ball and ^ represents a place holder where an urn could be placed. For this scenario:

There are $\binom{n-1}{r-1}$ distinct positive integer valued vectors $(x_1,...,x_n)$ satisfying the equation: $x_1 + ... + x_n = n, x_i>0, i=1,..,r$ $\clubsuit$

It's clear that I could have this specific case ooo|ooo|oo. Here the bar represents a divide for the urn and you see I have 3 sections. So that case is clear. Can anyone please explain this problem to me? I don't understand the nonnegative integer case.

Also, people who post tend to be crazy smart and explain things very in a complicated manner. I'd appreciate it if it could be explained in layman's terms as much as possible.

Thank you!!!

Like so many problems in combinatorics, the key to this problem is understanding precisely what kind of things you are counting. You confusion seems to be arising, at least in part, from the fact that you are trying to count distributions of jobs to urns, and your authors are counting something seemingly different and abstruse to you. I will try to explain why they are in fact the same thing.

Consider the task of distributing 4 jobs among 26 urns as posed in your problem. If you were to naively count distributions of jobs to urns, you might start building distributions as follows in terms of sequences, where the value at the $i$th index in this list represents the number of jobs distributed to the $i$th urn:

$(1, 1, 1, 1, 0, 0, \ldots, 0)$ $(1, 1, 1, 0, 1, 0, \ldots, 0)$ $(1, 1, 1, 0, 0, 1, \ldots, 0)$

...

For a problem this large, you would get frustrated pretty quickly. While it's a nice idea, this type of solution doesn't seem to get us anywhere. So we have to conceptualize the problem in a different way, which leads me to your authors suggestion. Instead of building sequences, a common technique in combinatorics, why not instead pictorally represent the problem with o's and |'s, where o's represent jobs, and |'s (or dividers) represent divisions into urns. That is to say, the first sequence posed would look something like:

o|o|o|o|||||||$\ldots$|

where the two parallel dashes with no 'o's in between would represent an urn with no jobs in it.

The reason this technique is powerful is because it allows us to now count the different kinds of symbolic sequences we can build in a way that represents exactly what we're looking for: distributions of jobs to urns. But how do we count these kinds of distributions?

Well, we can see that as there are 26 urns, and 4 jobs to distribute, there are going to be a total of 29 symbols in our sequence (not 30, because we only need 25 (i.e., 26- 1) dividers to represent division into 26 total urns). Since we require that four of these symbols are 'o's, i.e., jobs, then we see that all possible sequences are formed by "choosing" four of the symbols in the sequence to be 'o's, and allocating the rest to be dividers. These build all the possible distributions we are looking for, and for this particular problem, we see that the number of possible distributions is thus ${26 - 1 + 4 \choose 4}$.

You might rightfully protest, "Why are we choosing 'o's? Shouldn't this method work if we instead chose 25 of the symbols to be dividers?" Well, that's a perfectly reasonable objection; but by the symmetry of $n C r$, we in fact have that ${29 \choose 4} = {29 \choose 25}$. You can see that this type of thinking quickly generalizes to distributions of $n$ indistinguishable things to $k$ distinguishable people; there will be $n$ objects, $k-1$ dividers, and we choose $n$ of the symbols to be objects, so we get ${n + k - 1 \choose n}$ possible distributions.

This explanation might seem a bit overkill (it probably is!), but this type of thinking can help you solve a lot of distribution problems of this kind. The analogue in the case of non-negative vector solutions to $x_{1} + \cdots + x_{k} = n$ is in realizing that this is the same as distributing $n$ indistinguishable things among $k$ distinguishable people, where $x_{i}$ simply represents the number of "things" distributed to the $i$th person.

I hope this helps!

Edit: in response to your next question, I'm not sure why your authors would present it this way (typically, the flow of logic is reversed!) but I can certainly explain.

The key is in noting that strictly positive solutions require $y_{i} > 0$ for all $i$, i.e., $y_{i} \geq 1$. One way to ensure this is to simply add one to each element of the non-negative solutions; that is, set each $y_{i}$ equal to $x_{i} + 1$. Since each $x_{i} \geq 0$, we then have that each $y_{i} \geq 1$ as desired. However, if we wish to leave the number of distributions unchanged, we cannot change what we are doing combinatorially; hence, for each $y_{i}$, if we set $y_{i} = x_{i} + 1$, then we must add 1 to the right hand side of the expression $x_{1} + \cdots + x_{r} = n$ for each $i \in \{1, 2, \cdots, r\}$. Then we have $y_{1} + \cdots + y_{r} = n + 1 + \cdots + 1 = n + 1*r = n + r$.

As a sort of combinatorial exercise, one way you can convince yourself that the number of distributions is unchanged is to think of it as follows. Imagine instead of distributing $n$ objects to $r$ people, accepting distributions where some people get zero objects, we instead consider distributing one object to each of the $r$ people a priori in order to ensure that each person gets at least one object. But to leave the distribution unchanged, that would mean we would distribute $n+r$ objects, allocating one object to each of the $r$ people from the start - hence why in "equation form" we would set $y_{i} = x_{i} + 1$.

Hope this helps! Feel free to post if you need further clarification.

Let's say we have the following problem: Distribution of n identical objects into k boxes.

Let's consider a specific problem: How many ways can you put 4 identical balls into 2 boxes? We will draw a picture to understand the solution to this problem. Imagine 4 identical items are {**}. If we draw a vertical bar somewhere among these 4 stars, this can represent a unique assignment of the balls to the boxes. For example:

$|****$, Box 1=0, Box2=4
$*|***$, Box 1=1, Box2=3
$**|**$, Box 1=2, Box2=2
$***|*$, Box 1=3, Box2=1
$****|$, Box 1=4, Box2=0

Since there is a correspondence between a star/bar picture and assignments of balls to boxes, we can count the star/bar pictures and get an answer to our balls-in-boxes problem. So the question of finding the number of ways to put four identical balls into 2 boxes is the same as the number of ways of arranging four identical stars and one vertical bar which is $\binom{5}{4}=\binom{5}{1}=5$. In this case, we had n indistinguishable objects and k indistinguishable boxes:

The number of ways n identical (indistinguishable) objects can be distributed into k boxes is: $\binom{n+k-1}{k-1}=\binom{n+k-1}{n}$

Now consider the above case where you have 26 distinguishable people and 4 identical jobs which are to be distributed. As in the previous case, we can also represent this with stars and bars. However, in this case we will have 25 bars representing the dividers for the 26 people and 4 stars {**} for the 4 jobs. The total characters in a linear sequence will be 25+4 or (n-1+k) and we will select either 4 jobs or the 25 dividers. So $\binom{29}{4}=\binom{29}{25}$. Thus:

The number of unordered samples of r objects, with replacement, from n distinguishable objects is $\binom{n+r-1}{r}=\binom{n+r-1}{n-1}$. This is equivalent to the number of ways to distribute r indistinguishable balls into n distinguishable urns without exclusion.