combinatorics - generating functions 2

htata123 · #1 $Old$ November 4th, 2009, 01:28 PM

Hi, another question that requires generating functions;

We select an odd number of people from a group of n people, to serve on a committee. Then we select an even number of people from this committee to serve on a subcommittee. (Zero is an even number too). In how many different ways can we do this?

Thanks in advance for any help i can get.

awkward · #2 $Old$ November 6th, 2009, 06:06 PM

Quote:

Originally Posted by htata123 $View Post$

Hi, another question that requires generating functions;

We select an odd number of people from a group of n people, to serve on a committee. Then we select an even number of people from this committee to serve on a subcommittee. (Zero is an even number too). In how many different ways can we do this?

Thanks in advance for any help i can get.

It's no entirely clear whether you want a generating function for the answer or just need to use generating function techniques in deriving the answer. I'm going to assume the latter.

The first committee can be selected in $\sum_{i \; odd}\binom{n}{i}$ ways, and then the subcommittee can be selected in $\sum_{j \;even} \binom{i}{j}$ ways; so the total number of ways the committee and subcommittee can be selected is
$\sum_{i \; odd} \sum_{j \;even} \binom{n}{i} \binom{i}{j}$ .

Let's start by finding f(x), the ordinary power series generating function for the number of ways to select the committee. From the binomial theorem,
$(1+x)^n = \sum_i \binom{n}{i} x^i$ .... (1), and
$(1-x)^n = \sum_i (-1)^n \binom{n}{i} x^i$ .... (2)
Subtracting (2) from (1) and dividing by 2, we have
$(1/2) \; [(1+x)^n - (1-x)^n] = \sum_{i \; odd}\binom{n}{i} x^n = f(x)$ .... (3)

Let $x = 1+y$ ; then
$f(1+y) = \sum_{i \; odd}\binom{n}{i} (1+y) ^n = \sum_{i \; odd}\binom{n}{i} \sum_j \binom{i}{j} y^j$

Using the same trick to isolate the even powers of y that we used to find f, but this time adding instead of subtracting, we have
$(1/2) \; [f(1+y) + f(1-y)] = \sum_{i \; odd} \sum_{j \;even} \binom{n}{i} \binom{i}{j} y^j$ .

Let y = 1; then
$(1/2) \; [f(2) + f(0)] = \sum_{i \; odd} \sum_{j \;even} \binom{n}{i} \binom{i}{j}$ .
Substituting from (3),
$(1/4) \; [3^n - (-1)^n] = \sum_{i \; odd} \sum_{j \;even} \binom{n}{i} \binom{i}{j}$ ,
i.e, the total number of ways to select the committee and subcommittee is

$(1/4) \; [3^n - (-1)^n]$ .