Using Generating Function to calculate number of ways to select committees

89 Views Asked by At

How many ways are there to select three committees from 10 people? The committees serve different purposes, someone has to be in every committee and everyone serves in exactly one committee. (Use the appropriate generating function)
My approach is, $$ (e^x-1)^3 $$ $$ = {e}^{3x} - 3e^{2x}+3e^x - 1 $$


Is it correct?

1

There are 1 best solutions below

0
On

We can solve the problem first assuming that some committees can be left empty. So, if the exponent of $x$ is the people in the first committee, the exponent of $y$ is the people in the first committee, and the exponent of $z$ is the people in the first committee, then expanding the following expression the coefficient of each term indicates in how many ways you can form committees with the number of people in each committee indicated by the exponents: $(x+y+z)^{10}$. E.g., the coefficient of $x^3 y^5 z^2$ is 2520, hence there are 2520 ways to form committees con 3 people in the first one, 5 in the second one, and 2 in the third one.

Next, if every committee must have someone in it we must eliminate from our generating function the terms in which some exponent is zero. Using the inclusion-exclusion rule we get: $$ f(x,y,z) = (x+y+z)^{10} - (x+y)^{10} - (x+z)^{10} - (y+z)^{10} + x^{10} + y^{10} + z^{10} $$ Finally, the sum of all coefficients is $f(1,1,1) = 55980$, and that is the number of committees that can be formed verifying the conditions stated.