1

There are $n$ types of different articles. The names of the types are - $A_1,A_2,A_3,...,A_n$ Number of article $A_1$ is $B_1$ , $A_2$ is $B_2$... same goes upto $A_n$. We have to choose k articles.Repetition is allowed.

A colorful version would be something like this- You go to a bakery,you need to buy k cakes.You see that there are n types of cakes ie. chocolate,vanilla,mango,pineapple,orange etc.. and also notice that there are only c chocolate cakes,v vanilla cakes,m mango cakes,p pineaple cakes and so on.In how many ways can you buy k cakes when you don't take order into concern?

Soham
  • 2,029
  • See if this isn't a duplicate of http://math.stackexchange.com/questions/686/combinations-of-selecting-n-objects-with-k-different-types? – Gerry Myerson Mar 14 '13 at 04:22
  • 1
    NONONO it is not.In that problem the supply of each type of cake is not fixed but here it is. – Soham Mar 14 '13 at 04:31

2 Answers2

2

Try "sum of number of total number of cakes"-choose-k:

$$\binom {\sum_{i = 1}^n B_i\\}{k}$$

This does not take order into account, nor does it matter what the types of cakes chosen happen to be. The precise number of any particular type, aside from being a term in the sum of all cakes, doesn't matter. All you need is the total number of cakes available, and $k$, the number of cakes you need to choose.

amWhy
  • 209,954
  • I don't know what to say,your solution does seem right but it is notoriously simple and now I'm wondering that how could I not solve this problem? Or was I unable to convey my idea of the problem?Well I need some time to ponder over this. Anyways,thanks! – Soham Mar 14 '13 at 04:51
  • You're welcome. The types of cake don't matter, nor the number of each: its just like a problem where each of the different kinds of cakes are put into identical boxes: we select $k$ boxes from however many boxes there happen to be, in total. What we end up with is simply k cakes, and then we can learn which types of cakes those happen to be. – amWhy Mar 14 '13 at 04:55
  • 2
    Hey I just thought it this way and found that your solution has overcounted.. Let us assume we are choosing $k_1$ of the $A_1$ and so on... thus $k_1$+$k_2$...$k_n$=$k$ This particular choice should contribute 1 to the total count. But i'm feeling that we have chosen this many times.I'm thinking that while choosing $v_1$ vanilla cakes,we have chosen it $\binom{v_1}{v}$ times. – Soham Apr 12 '13 at 08:30
0

This problem can be rewritten using generating functions.

Let's simplify to the case where we only have two objects. Suppose there are 5 vanilla cupcakes and 3 chocolate ones. If we're picking 3 objects, then we look for the coefficient of $x^3$ in the expansion of:

$$(1 + x + x^2 + x^3 + x^4 + x^5)(1 + x + x^2 + x^3)$$

The logic is that, the term we pick out from the first polynomial is how many vanilla cupcakes we pick, and the term from the second is chocolate. We can rewrite this:

$$\frac{(x^6 - 1)(x^4 - 1)}{(x - 1)^2}$$

And so, you are looking for the coefficient of $x^k$ in:

$$\frac{(x^{B_1} - 1)(x^{B_2} - 1) \cdots (x^{B_n} - 1)}{(x - 1)^n}$$

Though, I don't know a closed form expression for this.

Alex Zorn
  • 4,304
  • There probably isn't a (useful) closed form. You can use the binomial theorem to expand $(1-x)^{-n}$ so you're looking for the coefficient of $x^k$ in a product, and in practice (and if the numbers aren't too big) you can work out an answer, but I don't expect a useful formula. – Gerry Myerson Mar 14 '13 at 04:50