Results 1 to 2 of 2

Thread: combinatorics - generating functions 2

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    29

    combinatorics - generating functions 2

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    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 $\displaystyle \sum_{i \; odd}\binom{n}{i}$ ways, and then the subcommittee can be selected in $\displaystyle \sum_{j \;even} \binom{i}{j}$ ways; so the total number of ways the committee and subcommittee can be selected is
    $\displaystyle \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,
    $\displaystyle (1+x)^n = \sum_i \binom{n}{i} x^i$ .... (1), and
    $\displaystyle (1-x)^n = \sum_i (-1)^n \binom{n}{i} x^i$ .... (2)
    Subtracting (2) from (1) and dividing by 2, we have
    $\displaystyle (1/2) \; [(1+x)^n - (1-x)^n] = \sum_{i \; odd}\binom{n}{i} x^n = f(x)$ .... (3)

    Let $\displaystyle x = 1+y$; then
    $\displaystyle 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
    $\displaystyle (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
    $\displaystyle (1/2) \; [f(2) + f(0)] = \sum_{i \; odd} \sum_{j \;even} \binom{n}{i} \binom{i}{j}$.
    Substituting from (3),
    $\displaystyle (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

    $\displaystyle (1/4) \; [3^n - (-1)^n] $.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. generating functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 1st 2010, 01:15 AM
  2. Generating Functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 12th 2010, 04:46 PM
  3. Combinatorics question - generating functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 4th 2009, 04:22 PM
  4. Functions and Combinatorics?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 27th 2009, 02:37 PM
  5. Generating functions
    Posted in the Calculus Forum
    Replies: 3
    Last Post: Jan 8th 2009, 10:50 AM

Search Tags


/mathhelpforum @mathhelpforum