I'm new to Combinatorics and am wondering if there is a well-known generalization to the binomial coefficients in the following sense:
The binomial coefficients, $n \choose d$, can be considered as the number of ways in which $d$ objects can be chosen from among $n$ such that order of selection doesn't matter and no object may be selected more than once, while the multi-set coefficients, ${\big(\!{n\choose d}\!\big)}={n+d-1\choose d}$, enumerate the ways in which $d$ objects can be chosen from among $n$ objects such that order doesn't matter but any object may be chosen any number of times.
Is there a middle ground? Specifically, one in which $d$ objects are chosen from among $n$ such that order doesn't matter but the $i^{th}$ object may be selected no more than $k_i$ times?
Heuristically, there are two fairly obvious approaches for calculating these numbers (aside from brute force). Let's call these numbers $C(n,d;K)$ for convenience, where $K\equiv \{k_1,k_2,...,k_n\}$. First, one could find the coefficients of polynomials of the form $$ {\large\prod_{i=0}^{n}{\huge(}\sum_{j=0}^{k_i}(x^j){\huge)}=\sum_{m=0}^{N}C(n,m;K)x^m} $$ where $k_0\equiv 0$ and $N=\sum_{i=0}^{n}k_i$.
On the other hand, one could use an algorithm similar in logic to that of Pascal's Triangle wherein the $C(n,d;K)$ are calculated by summing $k_n$ terms with $n$-value $n'=n-1$ and with $K'=K-\{k_n\}$ and $N'=N-k_n$ (i.e. from the previous "line" in a generalized Pascal's Triangle). $$ \large{C(n,d;K)=\sum_{m=d-k_n}^{d}C(n',m;K')} $$ with $C(n',m;K')=0$ for all $m<0$ and all $m>N'$.
To help clarify, here's an example: Suppose we have 4 object types with the following $k$-values $k_1=1,\ k_2=2,\ k_3=3,\ k_4=4.$ From this we can construct a generalized Pascal's Triangle:
$\underline{n=0}:\ 1\\\underline{n=1}:\ 1\ \ 1\\\underline{n=2}:\ 1\ \ 2\ \ 2\ \ 1\\\underline{n=3}:\ 1\ \ 3\ \ 5\ \ 6\ \ 5\ \ 3\ \ 1\\\underline{n=4}:\ 1\ \ 4\ \ 9\ \ 15\ \ 20\ \ 22\ \ 20\ \ 15\ \ 9\ \ 4\ \ 1$
Each term in the $n$th row of the triangle is computed by sliding a window of size $k_n+1$ across the $(n-1)^{th}$ row of the triangle and summing the terms within that window (i.e. for the 3rd row [recall that $k_3=3$], $1=0+0+0+1$, $3=0+0+1+2$, $5=0+1+2+2$, and so on).
Like Pascal's Triangle, these generalized triangles have many convenient properties. For instance, the $n^{th}$ row always has $N_n+1$ terms in it; the rows are always symmetrical; and, the final row in the triangle (the one which provides the coefficients we are looking for) doesn't depend on the order in which you compute the previous rows (i.e. the $n=4$ row would look the same in the above example even if the $k$-values were swapped around [e.g. $k_1=2,\ k_2=4$, etc.]). Perhaps the most interesting property is the following: $$ \large{\sum_{m=0}^{N}C(n,m;K)=\prod_{j=0}^{n}(k_j+1)} $$ So in the above example this implies that the sum of the $n^{th}$ row is $(n+1)!$, or in the limiting case of the binomial coefficients (in which all $k_i=1$), the sum of the $n^{th}$ row is $2^n$ - as expected.
Clearly, there are methods for computing these general set coefficients, but I have been unable to find any literature on a concise formula for the $C(n,d;K)$ given all the parameters of the problem or even anything about efficient methods for computing one of these coefficients without the use of the polynomial generating function cited above.
Does anyone know of any such methods or formulae? Any help would be greatly appreciated.
Thanks!
