I carelessly typed in the wrong generating function (but have corrected it below). It shouldn't be just (1+x²+x³+x^4)²; I forgot the term (1+x)². Sorry about that!
I love combinatorics.
For these questions, you need to use generating functions to solve it.
You have 1 M, 4 i's, 4 s's, and 1 p. You require the number of combinations of 3 letters from these letters.
The generating function in this case is
The answer is the coefficient of the term x³ in the expansion of the above expression.
If you want a group of g letters where g is a positive integer, you require the coefficient of x^g in the expansion of
This can be easily solved by using a program, but unfortunately I don't have one.
For the third one, you require the coefficient of x^g in the expansion of
(1+x²+x³+...+x^n1) (1+x²+x³+...+x^n2) (1+x²+x³+...+x^n3) ... (1+x²+x³+...+x^nl)
I tried to include a link to generating functions in wikipedia but I encountered error 999 when I tried to submit it... is there a solution?
The first answer's combination formula works only when each letter is distinct. In that case you require the coefficient x^q in the expansion of (1+x)^n where n is the number of distinct letters and q is the number of letters you want in each combination. In that case it is of course nCq = n!/(q!(n-q)!), which is the binomial coefficient.
Does anyone know of any free online calculator for evaluating the expansion of an expression like (x^3 + x^8 + x^10) (x^2 + x^4 + x^5 + x^7), or at least finding the coefficient of a specific term in the expansion of the multinomials?
Many thanks if there's one online because I don't have a program to do all the business of simplying...
Of course it won't work for g = 11 because there are only 10 letters in "Mississipi".
Are these questions from a specific problem set (with/without solutions), or did you made these up?
With the correct expansion of the generating function (x+1)² (1+x²+x³+x^4)², you should get 1 for g = 10.
Do you have a program to do all the calculations? I hope you do.
Did your teacher use a different approach other than generating functions to do the first question? But don't tell me that his approach is basic enumeration of all the combinations! :-)
OK. In that case it is PERMUTATION instead of COMBINATION.
Since it is permutation, you want to find the coefficient of x³/3! in the expansion of
(1 + x)² (1 + x + x²/2! + x³/3! + x^4/4!)².
Edit: for the last expression, it wouldn't be affected if you write
(1 + x + x²/2! + x³/3! + x^4/4!)²
as (1 + x + x²/2! + x³/3! + x^4/4! + x^5/5! + ...)² = exp(x)² = exp(2x)
= 1 + 2x + 4x²/2! + 8x³/3! + ...
multiply this by x² + 2x + 1 to find the coefficient of x³/3!:
x² * 2x = 2x³ = 12x³/3!
2x * 4x²/2! = 8x³/2! = 24x³/3!
1 * 8x³/3! = 8x³/3!
sum these gives the coefficient of x³/3! as 44.
If you want to know why this works, I would recommend a text book on combinatorics.
Here's the basic theory of generating function, though (note that the notation C(n,k) = nCk provide n >= k):
Consider the expansion of (1+x)^n
(1+x)^n = C(n,0) + C(n,1)x + C(n,2)x² + C(n,3)x³ + ....
The coefficient of x^r is C(n,r) and this is the number of ways of choosing r things from n different things. This arises because in the multiplication of n brackets, (1+x)(1+x)(1+x)(1+x)....to n terms, we can choose the r brackets from which to take the x and (n-r) brackets from which to choose 1 in C(n,r) ways. So the coefficient of x^r gives the number of ways of selecting r things from n things. Thus if we have 3 A's, 2 B's and 5 C's and require the number of combinations of 4 letters that can be chosen from these letters, the generating function is:
(1+x+x²+x³) (1+x+x²) (1+x+x²+x³+x^4+x^5)
and we require the coefficient of x^4 in this expansion
= 1 + 3x + 6x² + 9x³ + 11x^4 + 12x^5 + 11x^6 + 9x^7 + 6x^8 + 3x^9 + x^10
and we can see that coefficient of x^4 is 11, so there are 11 combinations of 4 letters that can be made from the 10 letters available.
Exponential Generating Functions
We could write the expansion of (1+x)^n in a different form.
If P(n,r) is the number of permutations of r things that can be made from n different things then we have:
(1+x)^n = P(n,0) + P(n,1).x + P(n,2)x²/2! + P(n,3).x³/3! + ...
and the coefficient of x^r/r! will be P(n,r)
This arises because the number of PERMUTATIONS of the x's (considered to be different from each other) that could be made from choosing r brackets to contribute an x and n-r brackets to contribute a 1, is indeed P(n,r). So in this type of generating function the coefficient of x^r/r! is the number of permutations that could be made by selecting r things from n things.
Thus if we have 3 A's, 2 B's and 5 C's and require the number of permutations of 4 letters that can be chosen from these letters, the generating function is:
(1+x+x²/2!+x³/3!) (1+x+x²/2!) (1+x+x²/2!+x³/3!+x^4/4!+x^5/5!)
Since we need only coeffients up to x^4 we could write this
(1+x+x²/2!+x³/3!) (1+x+x²/2!) e^x
= (1 + 2x + 2x² + 7x³/6 + 5x^4/12 + x^5/12) e^x
= 1 + 3x + 9x²/2 + 13x³/3 + 71x^4/24 + 181x^5/120 + ...
And we require the coefficient of x^4/4! = coefficient of x^4/24.
From above working we see that this is 71. So there will be 71 permutations of 4 letters taken from the 10 letters available.
Note that you can use e^x if the number of letters that you require is not greater than the number of letters available. In this problem we could use up to 5 letters C and only required 4 letters for each permutation.
The whole problem is much easier if for instance you had the following question. How many different permutations of 4 letters can be made from 5 A's, 6 B's and 7 C's?
The answer will be given by the coefficient of x^4/4! in the expansion of:
(1 + x + x^2/2! + x^3/3! + x^4/4! + x^5/5! + ...)³
= [e^x]³ = e^(3x)
= 1 + (3x) + (3x)²/2! + (3x)³/3! + (3x)^4/4! + (3x)^5/5! + ...
and the coefficient of x^4/4! is clearly 3^4 = 81
So there will be 81 permutations of 4 letters that can be made from the 18 letters available.
We could calculate this directly, since we have 3 letters to choose from for each of the 4 positions, giving 3^4 = 81 sequences.
This is from Ask Dr. Math.