# Number of ways to choose without replacement from a “set” that contains duplicates

If we have the set {A,B,C} the number of combinations is easy, if we want to choose k things there are $\frac{3!}{(3-k)!}$ permutations, each permutation is of $k$ things so there are $k!$ permutations of one combination, thus there are $\frac{3!}{k!(3-k)!}$ combinations, as you'd expect.

Now consider the set {A,A,B,C} which I will write {A,a,B,C} just so you can tell which one I am referring to if needed, then we have 4 combinations of length 2:

• Aa = aA
• AB = BA = aB = Ba
• AC = CA = aC = Ca
• BC = CB

We can work this out the following way:

If I choose A (or a) first then there are 3 ways of choosing next (the other A, B or C)

If I don't choose A first there is only one way not covered above (we have chosen B or C so we can choose the other not A to get a combination not included in the above)

Thus there are 4 ways in total.

I am not sure how to generalise this to a set of $m$ unique symbols, where the ith symbol occurs $f_i$ times. (in the above example m was 3, the first symbol, A, had frequency 2 meaning $f_1=2$) where I want to choose k things.

n, the number of things we have to choose from is the same as $\sum^m_{i=1}f_i$

I do accept that this might not have a nice answer (one based on the axiom of choice, that for a decision with m outcomes and another with n that will have n outcomes regardless of what we choose for the first decision means there are $mn$ possible outcomes) which I have used to derive other ways of counting.

## 1 Answer

Its the coefficient of $x^k$ in the polynomial $\Pi_{i=1}^{m}(1+x+x^2+....+x^{f_i})$

Consider the product $\Pi_{i=1}^{m}(1+x_i+x_i^2+....+x_i^{f_i})$ . This product has terms of the form $\Pi_{i=1}^m x_i^{\alpha_i}$ ,such a term represents a combination $\alpha_1$ objects of type $1$, $\alpha_2$ objects of type $2$,.... .We want to find the total number of terms which have total $k$ objects . Substituting $x_i=x$ separates the terms with different "total number of objects". In fact the coefficient of $x^k$ will be the number of terms containing exactly k objects.

• Any reason why? – Alec Teal Feb 20 '14 at 14:45
• See the edited version. – viplov_jain Feb 20 '14 at 16:24