Counting Combinations of a List of Numbers Let's say I have the following list of 9 (including repetitions) single-digit numbers: 7,7,7,5,5,3,2,2,2.  I want to know, for an arbitrary list of natural numbers, how many ways I can select one, two,...,all of them without the obvious double counting. For example, for the list above I can select two of them in the following 9 ways:
77 75 55 53 32 22 73 72 52,

and again for the list above I can select three of them in the following 15 ways:
777 775 755 553 532 322 222 773 772 722 552 522 753 752 732

(let me know if I missed some).
I've tried thinking of it as a counting without replacement problem, e.g. thinking of each number as a colored marble in an urn but can't seem to get the proper formula.

Suppose we have $N$ balls colored $n$ different colors. For each color $k$, let $d_k$ be the number of balls of color $k$. Our goal is to find the number $a_r$ of ways to choose $r\leq N$ balls without repetition and ignoring order, where balls of the same color are considered identical. Now, any such choice of $r$ balls is completely determined by how many balls of each color it has. In other words, we're reduced to finding the number of $n$-tuples $(e_1,\ldots,e_n)$ of non-negative integers satisfying


*

*$e_k\leq d_k$ for all $k$, and

*$e_1+\cdots+e_k=r$.


Here's where we make use of a really nice algebraic trick: consider the product of polynomials
$$f(X)=\prod_{k=1}^n\left(1+X+X^2+\cdots+X^{d_k}\right).$$
Expanding this out, we get
$$\begin{align*}
f(X) &= \left(\sum_{j_1=0}^{d_1}X^{j_1}\right)\cdots\left(\sum_{j_n=0}^{d_n} X^{j_n}\right)\\
&= \sum_{j_1=0}^{d_1}\cdots\sum_{j_n=0}^{d_n} X^{j_1+\cdots +j_n},
\end{align*}$$
so the coefficient of $X^r$ is 
$$\sum_{j_1+\cdots+j_n=r}1,$$
where $j_k$ is required to be less than or equal to $d_k$ for all $k$. But this is exactly $a_r$. Thus, all we need to do is find a nice representation of the coefficients of $f(X)$.
To do this, recall that $1+X+X^2+\cdots+X^m=(1-X^{m+1})/(1-X)$ for all $m$, and that $(1-X)^{-n}=\sum_{r=0}^\infty \binom{n+r-1}{n-1}X^r$. Then 
$$\begin{align*} 
f(X) &= \frac{(1-X^{d_1+1})\cdots(1-X^{d_n+1})}{(1-X)^n}\\
&= (1-X^{d_1+1})\cdots(1-X^{d_n+1})\left[\binom{n-1}{n-1}+\binom{n+1-1}{n-1}X + \binom{n+2-1}{n-1}X^2+\cdots\right].
\end{align*}$$ 
Now, $(1-X^{d_1+1})\cdots(1-X^{d_n+1})$ expands to 
$$ 1- \sum_{k=1}^n X^{d_k+1} + \sum_{k_1,k_2=1}^n X^{d_{k_1}+d_{k_2}+2} - \cdots + (-1)^n\sum_{k_1,\ldots,k_n=1}^n X^{d_{k_1}+\cdots+d_{k_n}+n}, $$
where in each sum, the $k_i$'s are required to be distinct. To multiply this together with the series in brackets, let's figure out what happens when we multiply the series in brackets with a single guy of the form $X^s$, where $s$ is a positive integer. Well,
$$\begin{align*}
X^s\cdot\frac{1}{(1-X)^n} &= X^s\left[\binom{n-1}{n-1}+\binom{n+1-1}{n-1}X + \binom{n+2-1}{n-1}X^2+\cdots\right]\\
&= \binom{n-1}{n-1}X^s+\binom{n+1-1}{n-1}X^{s+1} + \binom{n+2-1}{n-1}X^{s+2}+\cdots\\
&= \binom{n+s-s-1}{n-1}X^s + \binom{n+s+1-s-1}{n-1}X^{s+1} + \binom{n+s+2-s-1}{n-1}X^{s+2}\cdots\\
&= \sum_{r=s}^\infty \binom{n+r-s-1}{n-1}X^r.
\end{align*}$$
But when $\binom{n+r-s-1}{n-1}=0$ whenever $r<s$ (by the definition of the binomial coefficient), so we can tack on all the $r<s$ terms to the above series expression and not change anything:
$$X^s\cdot\frac{1}{(1-X)^n} = \sum_{r=0}^\infty \binom{n+r-s-1}{n-1}X^r.$$
Finally, returning to our expansion of $(1-X^{d_1+1})\cdots(1-X^{d_n+1})$ and multiplying by the series, we get that the $r$th coefficient of $f(X)$, i.e. $a_r$, is 
$$a_r= 1- \sum_{k=1}^n \tbinom{n+r-d_k-2}{n-1} + \sum_{k_1,k_2=1}^n \tbinom{n+r-d_{k_1}-d_{k_2}-3}{n-1} - \cdots + (-1)^n\sum_{k_1,\ldots,k_n=1}^n \tbinom{n+r-d_{k_1}-\cdots-d_{k_n}-n-1}{n-1},$$
where, as before, in each sum, the $k_i$'s are required to be distinct.
