Results 1 to 6 of 6

Math Help - generating functions

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    45

    generating functions

    Count the ways that two 50 length binary strings can be formed so that in total they include 10 appearances of the digit one (1) and 90 appearances of the digit zero (0) and in the second string all the digits 0 must be in the beggining and all the digits 1 (if there are any) must be in the end.

    I think that for the digit ones it's :

    1+x+x^2+...+x^10

    and for the digit zero is:

    1+x+x^2+...+x^90.

    I can't get how I will form this limitation:in the second string all the digits 0 must be in the beggining and all the digits 1 (if there are any) must be in the end.


    Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,861
    Thanks
    742
    Hello, milagros!

    This seemed like a very complicated problem at first . . .


    Count the ways that two 50-length binary strings can be formed
    so that in total they contain ten 1's and ninety 0's.
    and in the second string. all the 0's must precede all the 1's (if any).
    It was much simpler than I thought . . .


    Consider the first group.
    It contains 50 digits: some 0's, some 1's.

    Suppose the first group has seven 1's and forty-three 0's.
    The first group can be any of: . {50\choose7} possible strings.

    But the second group is already determined!
    It will have three 1's and forty-seven 0's
    . . \text{and it }must\text{ look lile this: }\;\underbrace{000\hdots0}_{\text{47 digits}}111


    So we are concerned with the number of possible first groups.

    . . \begin{array}{cccc}<br />
\text{no 1's} & \text{fifty 0's} && {50\choose0} \\ \\[-3mm]<br />
\text{one 1} & \text{forty-nine 0's} && {50\choose1} \\ \\[-3mm]<br />
\text{two 1's} & \text{forty-eight 0's} && {50\choose2} \\ \\[-3mm]<br />
\text{three 1's} & \text{forty-seven 0's} && {50\choose3} \\<br />
\vdots & \vdots && \vdots \\<br />
\text{nine 1's} & \text{forty-one 0's} && {50\choose9} \\ \\[-3mm]<br />
\text{ten 1's} & \text{forty 0'1} && {50\choose10}<br />
\end{array}


    The answer is: . \sum^{10}_{n=0}{50\choose n}


    You can crank it out . . . I'll wait in the car.
    .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by milagros View Post
    Count the ways that two 50 length binary strings can be formed so that in total they include 10 appearances of the digit one (1) and 90 appearances of the digit zero (0) and in the second string all the digits 0 must be in the beggining and all the digits 1 (if there are any) must be in the end.

    I think that for the digit ones it's :

    1+x+x^2+...+x^10

    and for the digit zero is:

    1+x+x^2+...+x^90.

    I can't get how I will form this limitation:in the second string all the digits 0 must be in the beggining and all the digits 1 (if there are any) must be in the end.


    Thank you.
    Hi Milagros,

    Soroban has given you an excellent solution already, but here is a generating function approach since that seems to be what you are looking for.

    First, let
    a_r = the number of ways to form a binary string of length 50 with exactly r ones, and let
    f(x) = \sum a^r x^r.
    We know
    a_r = \binom{50}{r},
    so by the binomial theorem,
    f(x) = (1 + x)^{50}.

    Now let
    b_r = the number of ways to form a binary string of length 50 with exactly r ones, all at the end. There is only one such string, so
    b_r = 1
    and
    g(x) = \sum b_r x^r = 1 + x + x^2 + \dots + x^{50} = \frac{1-x^{51}}{1-x}

    Now the number of ways to form a binary string of length 50 and another string of length 50 with all the one's at the end, containing a total of r ones, is
    \sum a_r b_{50-r}
    which has the generating function f(x) \cdot g(x).

    So the answer to the original question is the coefficient of x^{10}
    in
    \frac{(1+x)^{50} \cdot (1-x^{51})}{1-x}
    which I think probably reduces, in the end, to the same answer given by Soroban (but I haven't checked it).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Oct 2009
    Posts
    45
    Quote Originally Posted by Soroban View Post
    Hello, milagros!

    This seemed like a very complicated problem at first . . .


    It was much simpler than I thought . . .


    Consider the first group.
    It contains 50 digits: some 0's, some 1's.

    Suppose the first group has seven 1's and forty-three 0's.
    The first group can be any of: . {50\choose7} possible strings.

    But the second group is already determined!
    It will have three 1's and forty-seven 0's
    . . \text{and it }must\text{ look lile this: }\;\underbrace{000\hdots0}_{\text{47 digits}}111


    So we are concerned with the number of possible first groups.

    . . \begin{array}{cccc}<br />
\text{no 1's} & \text{fifty 0's} && {50\choose0} \\ \\[-3mm]<br />
\text{one 1} & \text{forty-nine 0's} && {50\choose1} \\ \\[-3mm]<br />
\text{two 1's} & \text{forty-eight 0's} && {50\choose2} \\ \\[-3mm]<br />
\text{three 1's} & \text{forty-seven 0's} && {50\choose3} \\<br />
\vdots & \vdots && \vdots \\<br />
\text{nine 1's} & \text{forty-one 0's} && {50\choose9} \\ \\[-3mm]<br />
\text{ten 1's} & \text{forty 0'1} && {50\choose10}<br />
\end{array}


    The answer is: . \sum^{10}_{n=0}{50\choose n}


    You can crank it out . . . I'll wait in the car.
    .

    Thank you very very much got it with this way. Its more simple you are right.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2009
    Posts
    45
    Quote Originally Posted by awkward View Post
    Hi Milagros,

    Soroban has given you an excellent solution already, but here is a generating function approach since that seems to be what you are looking for.

    First, let
    a_r = the number of ways to form a binary string of length 50 with exactly r ones, and let
    f(x) = \sum a^r x^r.
    We know
    a_r = \binom{50}{r},
    so by the binomial theorem,
    f(x) = (1 + x)^{50}.

    Now let
    b_r = the number of ways to form a binary string of length 50 with exactly r ones, all at the end. There is only one such string, so
    b_r = 1
    and
    g(x) = \sum b_r x^r = 1 + x + x^2 + \dots + x^{50} = \frac{1-x^{51}}{1-x}

    Now the number of ways to form a binary string of length 50 and another string of length 50 with all the one's at the end, containing a total of r ones, is
    \sum a_r b_{50-r}
    which has the generating function f(x) \cdot g(x).

    So the answer to the original question is the coefficient of x^{10}
    in
    \frac{(1+x)^{50} \cdot (1-x^{51})}{1-x}
    which I think probably reduces, in the end, to the same answer given by Soroban (but I haven't checked it).

    Thank you also. I really want it with generating functions.
    You' re so kind. Thanks again.
    Last edited by milagros; October 24th 2009 at 01:24 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    Correction

    Quote Originally Posted by awkward View Post
    Hi Milagros,

    Soroban has given you an excellent solution already, but here is a generating function approach since that seems to be what you are looking for.

    First, let
    a_r = the number of ways to form a binary string of length 50 with exactly r ones, and let
    f(x) = \sum a^r x^r.
    We know
    a_r = \binom{50}{r},
    so by the binomial theorem,
    f(x) = (1 + x)^{50}.

    Now let
    b_r = the number of ways to form a binary string of length 50 with exactly r ones, all at the end. There is only one such string, so
    b_r = 1
    and
    g(x) = \sum b_r x^r = 1 + x + x^2 + \dots + x^{50} = \frac{1-x^{51}}{1-x}

    Now the number of ways to form a binary string of length 50 and another string of length 50 with all the one's at the end, containing a total of r ones, is
    \sum a_r b_{50-r} ---See correction below
    which has the generating function f(x) \cdot g(x).

    So the answer to the original question is the coefficient of x^{10}
    in
    \frac{(1+x)^{50} \cdot (1-x^{51})}{1-x}
    which I think probably reduces, in the end, to the same answer given by Soroban (but I haven't checked it).
    I didn't get that formula for the number of ways to form binary string of length 50 and another string of length 50 with all the one's at the end, containing a total of r ones quite right. It should be

    \sum_i a_i b_{r-i},

    but the generating function is still correct.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Generating functions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 8th 2011, 05:30 AM
  2. generating functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 1st 2010, 02:15 AM
  3. generating functions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 5th 2009, 06:57 PM
  4. Generating Functions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 25th 2008, 05:43 PM
  5. Generating functions...need some help here
    Posted in the Calculus Forum
    Replies: 4
    Last Post: January 31st 2008, 05:32 PM

Search Tags


/mathhelpforum @mathhelpforum