generating functions

Printable View

Oct 22nd 2009, 11:19 PM
milagros

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.
Oct 23rd 2009, 01:43 PM
Soroban

Hello, milagros!

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

Quote:

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} \text{no 1's} & \text{fifty 0's} && {50\choose0} \\ \\[-3mm] \text{one 1} & \text{forty-nine 0's} && {50\choose1} \\ \\[-3mm] \text{two 1's} & \text{forty-eight 0's} && {50\choose2} \\ \\[-3mm] \text{three 1's} & \text{forty-seven 0's} && {50\choose3} \\ \vdots & \vdots && \vdots \\ \text{nine 1's} & \text{forty-one 0's} && {50\choose9} \\ \\[-3mm] \text{ten 1's} & \text{forty 0'1} && {50\choose10} \end{array}$

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

You can crank it out . . . I'll wait in the car.
.
Oct 23rd 2009, 02:53 PM
awkward

Quote:

Originally Posted by milagros

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).
Oct 23rd 2009, 10:09 PM
milagros

Quote:

Originally Posted by Soroban

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} \text{no 1's} & \text{fifty 0's} && {50\choose0} \\ \\[-3mm] \text{one 1} & \text{forty-nine 0's} && {50\choose1} \\ \\[-3mm] \text{two 1's} & \text{forty-eight 0's} && {50\choose2} \\ \\[-3mm] \text{three 1's} & \text{forty-seven 0's} && {50\choose3} \\ \vdots & \vdots && \vdots \\ \text{nine 1's} & \text{forty-one 0's} && {50\choose9} \\ \\[-3mm] \text{ten 1's} & \text{forty 0'1} && {50\choose10} \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.
Oct 23rd 2009, 10:48 PM
milagros

Quote:

Originally Posted by awkward

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.
Oct 24th 2009, 07:01 AM
awkward

Correction

Quote:

Originally Posted by awkward

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.