Section 6.2 Calculating Coefficients Of Generating Functions

Download Report

Transcript Section 6.2 Calculating Coefficients Of Generating Functions

Section 6.2
Calculating Coefficients
Of Generating Functions
Aaron Desrochers
Ben Epstein
Colleen Raimondi
Tucker, Section 6.2
1
Calculating Coefficients Of
Generating Functions
• This chapter is about developing algebraic techniques
for calculating the coefficients of generating functions.
• All methods seek to reduce a given generating function
to a simple binomial –type generating function, or a
product of binomial-type generating functions.
Tucker, Section 6.2
2
Polynomial Expansions:
1)
1  x m1
 1  x  x 2  ...  x m
1 x
2)
1
 1  x  x 2  ...
1 x
3)
(1  x)n  1  C(n,1) x  C(n, 2) x2  ...  C(n, r) xr  ...  C(n, n) xn
4) (1  xm )n  1  C(n,1) xm  C(n, 2) x2m  ...  (1)k C(n, k ) xkm  ...  (1) n C(n, n) x nm
5)
1
2
r

1

C
(1

n

1,1)
x

C
(2

n

1,
2)
x

...

C
(
r

n

1,
r
)
x
 ...
n
(1  x)
6) If h(x)=f(x)g(x), where f(x)
h(x)
 a0  a1x  a2 x2  ...and
g(x)
 b0  b1x  b2 x2  ...,
then
 a0b0  (a1b0  a0b1 ) x  (a2b0  a1b1  a0b2 ) x2  ...  (arb0  ar 1b1  ar 2b2  ...  a0br )x r  ...
Tucker, Section 6.2
3
6) If h(x)=f(x)g(x), where f(x)  a0  a1x  a2 x2  ... and g(x)  b0  b1x  b2 x2  ... , then
h(x)  a b  (a b  a b )x  (a b  a b  a b )x2  ...  (a b  a b  a b  ...  a b )xr  ...
0 0
1 0
0 1
2 0
1 1
0 2
r 0
r 1 1
r 2 2
0 r
• The rule for multiplication of generating functions in Eqn. (6) is
simply the standard formula for polynomial multiplication.
Tucker, Section 6.2
4
1)
1  x m1
 1  x  x 2  ...  x m
1 x
•Identity (1) can be verified by polynomial “long division”.
•We restate it, multiplying both sides of Eq.(1) by
As
(1  x)
(1  xm1 )  (1  x)(1  x  x2  ...  xm )
We verify that the product of the right-hand side is
(1  x m1 )
by “long multiplication”
1  x  x 2  ...  x m
1 x
1  x  x 2  ...  x m
 x  x2  x3 ...  x m  x m1
1
 x m 1
Tucker, Section 6.2
5
1)
1  x m1
 1  x  x 2  ...  x m
1 x
2)
1
 1  x  x 2  ...
1 x
• If m is made infinitely large, so that 1  x  x 2  ...  x m
becomes the infinite series 1  x  x2  ...
then the
multiplication process will yield a power series in which the
coefficient of each xk , k  0 is zero.
We conclude that (1  x) ( 1  x  x2  ... )=1
[Numerically, this equation is valid for x  1 ;the
“remainder” term xm1
Goes to zero as m becomes infinite.]
Dividing both sides of this equation by (1 – X) yields identity
(2).
Tucker, Section 6.2
6
3)
(1  x)n  1  C(n,1) x  C(n, 2) x2  ...  C(n, r) xr  ...  C(n, n) xn
Expansion (3), the binomial expansion was explained at the start
of section 6.1. Expansion (4) is obtained from (3) by expanding
(1  y)m , where y   xm
 n
 n
m
(1  ( x )]  1    ( x )    ( x m ) 2 
1 
 2
n
 n
m k
   ( x )     ( x m ) n
k
 n
m
n
Tucker, Section 6.2
7
5)
1
2
r

1

C
(1

n

1,1)
x

C
(2

n

1,
2)
x

...

C
(
r

n

1,
r
)
x
 ...
n
(1  x)
n
For identity 5, ( 1 – x)-n =
1
= ( 1 + x + x2 + … ) n
1-x
1
Since
1-x
= ( 1 + x + x2 + … )
(eq. 2)
2)
1
 1  x  x 2  ...
1 x
r
Let us determine the coefficient x in equation (7) by counting the number of
formal products whose sum of exponents is r, if ei represents the exponent of the
e
e
e
xe n
ith term in a formal product , the the number of formal products x 1 x 2 x 3
whose exponents sum to r is the same as the number of integer solutions to the
equation
e e e   e  r e  0
1
2
3
n
i
In example 5, section 5.4 we showed that the number of nonnegative integer
solutions to this equation is C(r + n –1,r ) , so the coefficient x r in eqn (7) is C(r
+ n –1,r ) . This verifies expansion (5).
Tucker, Section 6.2
8
1)
3)
5)
1  x m1
 1  x  x 2  ...  x m
1 x
(1  x)n  1  C(n,1) x  C(n, 2) x2  ...  C(n, r) xr  ...  C(n, n) xn
1
 1  C (1  n  1,1) x  C (2  n  1, 2) x 2  ...  C (r  n  1, r ) x r  ...
n
(1  x)
6) If h(x)=f(x)g(x), where f(x)  a
0
h(x)
 a1x  a2 x2  ...
and g(x)  b
0
 b1x  b2 x2  ...
, then
 a0b0  (a1b0  a0b1 ) x  (a2b0  a1b1  a0b2 ) x2  ...  (arb0  ar 1b1  ar 2b2  ...  a0br )x r  ...
With formulas (1) and (6) we can determine the coefficients of a variety of
generating functions: first, perform algebraic manipulations to reduce a given
generating function to one of the forms (1  x)m ,(1  xm )n , or (1  x) n or
a product of two such expansions, then use expansions (3) and (5) and the
product rule (6) to obtain any desired coefficient.
Tucker, Section 6.2
9
Example 1
Find the coefficient of
x16 in ( x2  x3  x4  )5
x16 in x10 (1  x)5 [i.e, the x6 termin (1  x) 5 is
multiplied by x10 tobecomethe x16 termin x10 (1  x)5 ]
2
To simplify the expression, we extract x from each polynomial factor and the apply
identity (2).
( x 2  x3  x 4 
)5  [ x 2 (1  x  x 2 
 x10 (1  x  x 2 
1
10
x
(1  x)5
Thus the coefficient of
)]5
)5
x16 in ( x2  x3  x4  )5is the coefficient of
x16 in x10 (1-x) –5 [i.e., the x6 term in (1-x) –5 is multiplied by to become
the x16 term in x10 (1-x) –5 ]
Tucker, Section 6.2
10
Example 1 continued
5)
1
2
r

1

C
(1

n

1,1)
x

C
(2

n

1,
2)
x

...

C
(
r

n

1,
r
)
x
 ...
n
(1  x)
From expansion (5) we see that the coefficient of
x6in (1  x)5 isC(6  5 1,6)
More generally, the coefficient of xr in
x r in x10 (1  x)5 equals the coefficient of x r 10 in
(1  x)5 , namely, C ((r  10)  5  1, (r  10)).
Tucker, Section 6.2
11
Example 2
6) If h(x)=f(x)g(x), where f(x)  a
0
h(x)
 a1x  a2 x2  ...
and g(x)  b
0
 b1x  b2 x2  ...
, then
 a0b0  (a1b0  a0b1 ) x  (a2b0  a1b1  a0b2 ) x2  ...  (arb0  ar 1b1  ar 2b2  ...  a0br )x r  ...
Use generating functions to find the number of ways to collect $15 from 20
distinct people if each of the first 19 people can give a dollar (or nothing) and
the twentieth person can giver either $1 or $5 (or nothing).
The generating function for the number of ways to collect r dollars
from these people is (1+x)19(1+x+x 5). We want the coefficient of x15. The first
part of this generating function has the binomial expansion
(1+x)19 = 1 +
19
1
( )
x+
19
2
( )
x2+ … +
19 r
x+…+
r
( )
19
19
( )x
19
If we let f(x) be this first polynomial and let g(x) = 1+x+x5, then we can use Eq. (6)
to calculate the coefficient of x15 in h(x) = f(x)g(x). Let ar be the coefficient of xr in
f(x) in f(x) and br the coefficient of xr in g(x). We know that
ar =
19
r and that b0 = b1 = b5 = 1 (other bis are zero).
( )
Tucker, Section 6.2
12
Example 2 continued
6) If h(x)=f(x)g(x), where f(x)  a
0
h(x)
 a1x  a2 x2  ...
and g(x)  b
0
 b1x  b2 x2  ...
, then
 a0b0  (a1b0  a0b1 ) x  (a2b0  a1b1  a0b2 ) x2  ...  (arb0  ar 1b1  ar 2b2  ...  a0br )x r  ...
Then the coefficient of of x15 in h(x) is
a15b0 + a14b1 + a13b2 + … + a0b15
Which reduces to
a15b0 + a14b1 + a10b5
Since b0, b1, b5 are the only nonzero coefficients in g(x). Substituting the
values of the various as and bs in Eq. (6), we have
19
15 x 1 +
( )
19
14
( )
x 1+
19
10 x 1 =
( )
19
15
19
14 +
19
10
( ) ( ) ( ).
+
Tucker, Section 6.2
13
Class Problem
How many ways are there to select 25 toys from seven types of toys with
between two and six of each type?
1  x m1
 1  x  x 2  ...  x m
1 x
1)
3)
4)
2)
1
 1  x  x 2  ...
1 x
(1  x)n  1  C(n,1) x  C(n, 2) x2  ...  C(n, r) xr  ...  C(n, n) xn
(1  xm )n  1  C(n,1) xm  C(n, 2) x2m  ...  (1)k C(n, k ) xkm  ...  (1) n C(n, n) xnm
5)
1
 1  C (1  n  1,1) x  C (2  n  1, 2) x 2  ...  C (r  n  1, r ) x r  ...
n
(1  x)
6) If h(x)=f(x)g(x), where f(x)  a
0
h(x)
 a1x  a2 x2  ...
and g(x)  b
0
 b1x  b2 x2  ...
, then
 a0b0  (a1b0  a0b1 ) x  (a2b0  a1b1  a0b2 ) x2  ...  (arb0  ar 1b1  ar 2b2  ...  a0br )x r  ...
Tucker, Section 6.2
14
Class Problem (continued)
The generating function for ar, the number of ways to select r toys from
seven types with between 2 and 6 of each type, is
(x2 + x3 + x4 + x5 + x6)7
We want the coefficient of x25. We extract x2 from each factor to get
[x2 (1 + x + x2 + x3 + x4 )]7 = x14 (1 + x + x2 + x3 + x4 )7
Now reduce our problem to finding the coefficient of x 25-14 = x11 in
(1 + x + x2 + x3 + x4 )7. Using identity (1), we can rewrite this generating
function as
7
1 - x5 7
1
(1 + x + x2 + x3 + x4 )7 =
= (1 - x5)7
1-x
1-x
(
)
Tucker, Section 6.2
(
)
15
Class Problem (continued)
1  x m1
 1  x  x 2  ...  x m
1 x
1)
Let f(x) = (1 - x5)7 and g(x) = (1 - x5)-7 . By expansions (4) and (5), respectively,
we have
7 5
7 10
7 15
f(x) = (1 - x5)7 = 1 x +
x x +…
1
2
3
( )
g(x) =
( )
1
( )
( 1 - x ) = 1 + (1 + 17 – 1)x +(2 + 27 – 1)x
2
+…
+ r + 7 – 1 xr + …
r
(
)
Tucker, Section 6.2
16
Class Problem (continued)
To find the coefficient of x11, we need to consider only the terms in the product
1
of the two polynomials (1 - x5)7 and 1 - x that yield x11. The only nonzero
(
)
coefficients in f(x) = (1 - x5)7 with subscript < 11 (larger subscripts can be ignored)
are a0, a5, and a10. The products involving these three coefficients that yield x11
terms are:
a0b11
=1 x
(
+
11 + 7 – 1
+ 11
7
(
) ( 1))
a5b6
x
+
(
a10b1
6+7–1
+
6
7
1+7–1
x
(
)
(
).
) 2
1
Tucker, Section 6.2
17