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.


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.