Krdytkyu

I have been struggling with this brain teaser for some time now. I looked at some combinatorics and partition equations but I can't find the one that captures the solution entirely.

Frame

I have a set with 6 elements (bins) { a , b , c , d , e , f }.

Each element in the set can take an integer value in the range (0,5).

The value N is given by N = a + b + c + d + e + f: The total range for N is (0,30).

Question

For each value of N in the range (0,30) how many unique combinations of elements can I have in the set without repetition.

e.g. if N = 30 there is only 1 possible unique combination {5,5,5,5,5,5}

also for N = 0 there is only 1 possible unique combination {0,0,0,0,0,0}

 for     N =  1 there are 6 possible unique combinations {1,0,0,0,0,0}

                                                         {0,1,0,0,0,0}

                                                         {0,0,1,0,0,0}

                                                         {0,0,0,1,0,0}

                                                         {0,0,0,0,1,0}

                                                         {0,0,0,0,0,1}

Therefore N can be described as a discrete normally distributed integer random variable in the range (0,30).

Please help.

Your problem in general reads as
$$N_{,b} (s,r,m) = text{No}text{. of solutions to};left{ begin{gathered}
0 leqslant text{integer }x_{,j} leqslant r hfill \
x_{,1} + x_{,2} + cdots + x_{,m} = s hfill \
end{gathered} right.$$
where $N_b$ is expressed through the sum
$$
N_b (s,r,m)quad left| {;0 leqslant text{integers }s,m,r} right.quad =
sumlimits_{left( {0, leqslant } right),,k,,left( { leqslant ,frac{s}{r+1}, leqslant ,m} right)}
{left( { - 1} right)^k binom{m}{k}
binom
{ s + m - 1 - kleft( {r + 1} right) }
{ s - kleft( {r + 1} right)} }
$$
and whose o.g.f. in $s$ is as already suggested by N.F. Taussig
$$
F_b (x,r,m) = sumlimits_{0,, leqslant ,,s,,left( { leqslant ,,r,m} right)} {N_b (s,r,m);x^{,s} }
= left( {1 + x + cdots + x^{,r} } right)^m = left( {frac{{1 - x^{,r + 1} }}{{1 - x}}} right)^m
$$

The above is thoroughly explained in this related post and in this paper.

In your case, you just have to put $m=6,;r=5,; s=N$.

You could as suggested by N. F. Taussig use the generating function $(1 + x + x^2 + x^3 + x^4 + x^5)^6$ and the answer will be the coefficient of $x^N$ of the expanded function.

Otherwise This question can be solved using the technique described here

Let there be $N$ stars. Since you want to separate them into $6$ bins, you will need to use $5$ bars. The $5$ bars will "split" the balls into 6 bins. The permutation will always be of the form $${(bin~a)|(bin~b)|(bin~c)|(bin~d)|(bin~e)|(bin~f)}$$ Any permutation of the $N$ stars and $5$ bars will result in a unique solution. The number of ways that it can be arranged where $a, b, c, d, e$ and $f$ non-negative is $N+5choose 5$.

However, this will include cases where the bins can be more than 5. We will need to exclude the cases where $a, b, c, d, e$ or $f$ is greater than 5. This can be achieved by the Principle of Inclusion-Exclusion. We would first subtract the case where only one of $a, b, c, d, e$ or $f$ is greater than 5. This is equivalent to doing the above but with $N-6$ instead of $N$. There are ${6choose 1}$ ways for a bin to be more than 5. Hence you would subtract ${6choose 1}{N-6choose 5}$ from the total number of ways. However in this you will also notice that the case where 2 of the bins is greater than 5 was included twice. You would repeat the steps until the number of ways to have more than 5 balls in $j$ bins become zero.

The general formula would hence be $$sum_{j=0}^{floor(frac{N}{6})} (-1)^jbinom{6}{j}binom{N+5-6j}{5}$$.