Results 1 to 2 of 2

Math Help - 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 \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] .
    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: March 1st 2010, 01:15 AM
  2. Generating Functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 12th 2010, 04:46 PM
  3. Combinatorics question - generating functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 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: January 8th 2009, 10:50 AM

Search Tags


/mathhelpforum @mathhelpforum