4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ See the question math.stackexchange.com/q/553960/18880, which I answered yesterday. Although this question is better formulated than that one it asks pretty much the same thing, so I am going to ask to mark it as duplicate. In short, you are looking for the coefficient of $X^d$ in the polynomial $\prod_{i=1}^n(1+X+\cdots+X^{k_i})$, and the properties you ask for follow from that. In the end it comes down to multiplying polynomials in $X$, there is n escape from that. $\endgroup$ – Marc van Leeuwen Nov 7 '13 at 6:02
  • $\begingroup$ I appreciate the quick response. I'm a self-study when it comes to combinatorics, so I've never heard of "stars-and-bars" until just now. A quick search for that term turns up several pages of almost identical questions. Who knew... $\endgroup$ – Geoffrey Nov 7 '13 at 6:06
  • $\begingroup$ Stars-and-bars is just a way to help you remember the formula $\binom{-n}k=(-1)^k\binom{n+k-1}k$ for "negating" the upper index in binomial coefficients in a few combinatorial context where you might encounter them. But it is quite limited as method, and I would prefer learning more general methods. $\endgroup$ – Marc van Leeuwen Nov 7 '13 at 6:30
1
$\begingroup$

Ok, so you want to buy $d$ items in a store with $n$ elements, but where item $i$ only has a stock of $s_i$. What you are looking for is the coefficient of $x^d$ in the product

$(1+x^1+ x^2+ \dots+ x^{s_1})(1+x^1+ x^2+ \dots+ x^{s_2})\dots (1+x^1+ x^2+ \dots+ x^{s_n})=$

$\dfrac{(1-x^{s_1+1})(1-x^{s_2+1})\dots (1-x^{s_n+1})}{(1-x)^n}$

But, I don't think you can get something nicer than that. There is a good method for when all of the stocks are equal. I leave a link here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.