http://www2.informatik.hu-berlin.de/alkox/lehre/lvws1011/coalg/bin_packing.pdf
Bin Packing: We are given a set $I=\{1,\ldots \, n\}$ of items, where items $i \in I$ has size $s_i \in (0,1]$ and set $B=\{1, \ldots ,n\}$ of bins with capacity one. Find an assignment $a: I \rightarrow B$ such that the number of non-empty bins is minimal.
So I have this NP-hard problem. However, this lemma has got me confused.
Lemma. Let $\epsilon >0$ and $d \in \mathbb{N}$ be constants. For any instance of Bin Packing where $s_i \geq \epsilon$ and $|\{s_1,\ldots,s_n\}|\geq d$, there is a polynomial time algorithm that solves it optimally.
I'm fine understanding the number of items in a bin is bounded by $m = \lfloor 1/\epsilon \rfloor$. However, it says that the number of different assignments for one bin is bounded by $\tbinom {m+d} m$. I don't understand how this is true. Also, I don't understand what is happening. Certainly, shouldn't it be bounded by $\tbinom {n} k$. Don't understand the combinatorics of this.
There are $ \tbinom {n+k} k$ string containing ''k'' ones and ''n'' zeros. This is from wikipedia. So that would mean that the number of different assignment is the same as having a string with m ones and d zeroes. So confused.
It doesn't matter which of two items of the same size you put into a bin. Add to the $d$ different sizes a $(d+1)$-th size representing an unused slot; then there are
$$ \binom{m+d+1-1}m=\binom{m+d}m $$
different ways of assigning one of the $d+1$ sizes to each of the bin's $m$ slots (see e.g. Wikipedia). It may help to imagine putting the slots into the size categories instead of the other way around.