Multiset Combination in Combinatorics

Question

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?

Answer 1

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)$$

Answer 2

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)))

Answer 3

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])