# Multiset Combination in Combinatorics

I want to buy a $k$-combination of doughnuts, where $k$ is any amount less than or equal to the total doughnuts available. At the bakery there are $n$ different types of doughnuts but there are restricted amount left for each type of doughnut.

For example, In this case, the total doughnuts available is
4 + 2 + 3 + 2 + 7 + 2 + 8 = 28
and n = 7

Doughnut type       Amount left
1                     4
2                     2
3                     3
4                     2
5                     7
6                     2
7                     8
=====
28


Let's assume I want to buy a combination of $10$ doughnuts but I cannot have more than, for example $7$ of type $5$ doughnut and I can't have more than $3$ of type $3$ doughnuts. How many combination of $10$ doughnuts can I have altogether?

-
You may want to have a look at the multivariate hypergeometric distribution. –  Sasha May 13 '12 at 20:48

Let $a_i$ be the number of donuts you buy of type $i$. Then you have $$a_1+a_2+\cdots+a_7=10$$ subject to the constraints, $$0\le a_1\le4,0\le a_2\le2,\dots,0\le a_7\le 8$$ If you think about how you would multiply out the following product, you'll see you want the coefficient of $x^{10}$ in $$P(x)=(1+x+x^2+x^3+x^4)(1+x+x^2)\cdots(1+x+x^2+\cdots+x^8)$$ Now all those brackets contain geometric series, so you can rewrite as $$P(x)=(1-x^5)(1-x^3)\cdots(1-x^9)(1-x)^{-7}$$ and you can use the binomial theorem to get $$(1-x)^{-7}=1+{7\choose6}x+{8\choose6}x^2+{9\choose6}x^3+\cdots$$ So all you have to do is pick out the coefficient of $x^{10}$ in $$(1-x^5)(1-x^3)(1-x^4)(1-x^3)(1-x^8)(1-x^3)(1-x^9)\left(1+{7\choose6}x+{8\choose6}x^2+\cdots\right)$$ Now if you multiply out the first 7 terms, you get $$1-3x^3-x^4-x^5+3x^6+3x^7+2x^8-x^9-3x^{10}+{\rm\ higher\ terms}$$ (although you should check my work on that one), where we can ignore the higher terms because they can't contribute to the coefficient of $x^{10}$ that we are looking for. So, finally, you just have to pick out the coefficient of $x^{10}$ in $$(1-3x^3-x^4-x^5+3x^6+3x^7+2x^8-x^9-3x^{10})\left(1+{7\choose6}x+{8\choose6}x^2+\cdots\right)$$

-
i understand the polynomial expansion but how can i derive it from the initial equation i.e how can i derive this; $$P(x)=(1+x+x^2+x^3+x^4)(1+x+x^2)\cdots(1+x+x^2+\cdots+x^8)$$ from this; $$a_1+a_2+\cdots+a_7=10$$ –  user31280 May 15 '12 at 14:30
You can't. You derive $P(x)$ from the constraints. The $1+x+x^2+x^3+x^4$ comes from $0\le a_1\le4$; the $1+x+x^2$ comes from $0\le a_2\le2$; and so on. –  Gerry Myerson May 16 '12 at 0:15

Let C(n, [d_1, d_2, ..., d_k]) be number of combinations for given example, than:

C(n, [d_1, d_2, ..., d_k]) = sum(C(n-i, [d_2, ..., d_k]), i in [0, ..., min(n,d_1)])


Simple python implementation:

def C(n, l):
if n == 0: return 1
if not l: return 0
return sum(C(n-i, l[1:]) for i in xrange(min(n,l[0])+1))

print C(10, [4, 2, 3, 2, 7, 2, 8])

-
Just like in upper description :-) Second variable l is list of number of doughnuts. First line check is sum reached, second if there is no more doughnuts, and last line sums like described. l[1:] means sublist without first element. –  Ante May 14 '12 at 9:42

You can work it out with a recursive algorithm. I'm not sure if there is a neater way, for example with a closed formula - you have to account for the different numbers of doughnuts of each type at some point.

The line of thinking goes like this: if you look at the first type of doughnuts, you can choose freely how many to take. You then subtract that number from the total you want, and apply the same process to the other types. Once you run out of types of doughnuts, you either want a total of 0, in which case you've picked the required number of doughnuts, or you want a non-zero number of doughnuts, which means you picked too few or too many.

So the base of the recursion is that there is one way of picking no doughnuts from no baskets, and zero ways of picking any other number of doughnuts.

From that, you can work backwards, summing up the number of ways of making up the remaining total, given that you pick a certain number from the previous baskets.

I've written some Python code which does the calculations, and I've tried to add descriptions of how it works as much as possible:

#This function returns the number of ways of picking total doughnuts from
#the array numbers, which is an array of numbers of each type of doughnut
#available work recursively: for each possible number of doughnuts picked
#from the first basket, work out how many ways there are of making up the
#rest of the total from the other baskets
def kcombs(numbers,total):
#Base case: there is 1 way of choosing no doughnuts from no baskets
#It's impossible to pick any other number of doughnuts from no baskets
if len(numbers)==0:
if total==0:
return 1
else:
return 0
else:
#Otherwise, we have baskets to choose from.
#we can pick at most total doughnuts from the first basket.
#range(0,numbers[0]+1) represents the options for how many
#doughnuts we pick from the first basket.
#If we pick i doughnuts from the first basket, take that away from the
#total, and then work out how many ways there are of picking that many
#from the other baskets
return sum([
#no. of ways of making up the total from the other baskets
kcombs(numbers[1:],total-i)
#for each choice of no. of doughnuts from the first basket
for i in range(0,numbers[0]+1)
])

if __name__=='__main__':
#some tests
for numbers,total in [
([],0),       #one way of picking nothing from nothing
([],1),       #impossible to pick one from nothing
([1],1),      #one way
([2],1),      #still one way - all doughnuts of one type lookthe same
([2],2),      #still one way...
([2],3),      #impossible to pick 3 from 2
([1,1],2),    #one way - one from each basket
([2,2],2),    #3 ways - both from the first basket, one from each, or
#both from the second basket
([2,2],3),    #2 ways - one from 1st and two from 2nd, or vice versa
([3,1,2],4)   #should be five ways
]:
print('%i from %s: %i ways' % (total,numbers,kcombs(numbers,total)))

-