How to show that there are $\binom{M+K}{M}$ different number of type bins?

Question

In textbook by Vazirani's textbook, chapter 9 about Bin Packing. He give the following lemma.

Lemma 9.4 Let $\epsilon >1$ be fixed, and let K be a fixed nonnegative integer. Consider the restriction of the bin packing problem to instances in which each item is of size at least $\epsilon$ and the number of distinct item sizes is K. There is a polynomial time algorithm that optimally solves this restricted problem.

Proof. The number of items in a bin is bounded by $1/\epsilon$. Denote this by M. Therefore, the number of different bin types is bounded by $R = \binom{M+K}{M}$. Which is a large constant. Clearly, the total number of bins used is at most n. Therefore, the number of possible feasible packings is bouned by $P=\binom{n+R}{R}$, which is polynomial in n. Enumerating them and picking the best packing gives the optimal answer.

Question: We know a fact which is: $\binom{n+k-1}{n}$, now in order to find the number of different bin types we it should be something like $\binom{M+K-1}{M}$ why in the proof it is different?!!

Answer 1

The bins contain at most $M$ elements rather than exactly $M$ elements. This is why your formula doesn't work. In order to use your formula, we need to allow for one more type of element, a dummy type, and then we get $\binom{M+(K+1)-1}{M} = \binom{M+K}{M}$.

As an example, suppose that there is one type of element (so $K=1$). In that case, a bin can contain $0,\ldots,M$ elements, in total $M+1 = \binom{M+K}{M}$ choices.