Math 340 Tutorial 5
1. Given the sequence of coefficients, find the corresponding exponential generating func- tion:
(a) 0,0,0,1,1,1,1,1,… (b) 1,0,1,0,1,0,1,0,…
(c) −1,0,1,2,3,4,5,6,… (d) 0!,1!,2!,3!,4!,5!,…
(e) 22,23,24,25,26,27,…
Solution:
(a) With this sequence, we have the following power series:
Hence,
E(x)= 1×3 + 1×4 + 1×5 +… 3! 4! 5!
x x2 E(x)=e −1−x− 2.
(b) We have
E(x)=1+ 1×2 + 1×4 + 1×6 +… 2! 4! 6!
This is not as simple as just saying E(x) = ex2 , since
ex2 =1+x2+1×4+1×6+1×8+…
2! 3! 4!
We need to be a little more clever. First, notice the two power series:
ex =1+x+ 1×2 + 1×3 + 1×4 +… 2! 3! 4!
e−x =1−x+ 1×2 − 1×3 + 1×4 −…. 2! 3! 4!
If we add these together we get
Therefore,
ex + e−x = 2 + 2 x2 + 2 x4 + 2 x6 + 2 x8. 2! 4! 6! 8!
ex + e−x
E(x) = 2 = cosh(x)
(c) We have
E(x)=0+ 1x+ 2×2 + 3×3 + 4×4 +… 1! 2! 3! 4!
So the coefficient for xn is n which is just 1 . Hence, n! (n−1)!
E(x)=x+x2 + 1×3 + 1×4 +… 2! 3!
1213 =x 1+x+2!x +3!x +…
= xex.
(d) We have
E(x) = 0! + 1!x + 2!x2 + 3!x3 + 4!x4 + . . . 0! 1! 2! 3! 4!
=1+x+x2 +x3 +x4 +…
=1. 1−x
(e) We have
24 25 26 E(x)=22 +23x+ 2!x2 + 3!x3 + 4!x4 +…
22 23 24 =22 1+2x+ 2!x2 + 3!x3 + 4!x4 +…
212314 =2 1+(2x)+2!(2x) +3!(2x) +4!(2x) +…
= 4e2x
2. Given the exponential generating function, find the corresponding sequence of coeffi- cients:
(a) e−x (b) ex3
(c) αeβx
(d) c1er1x + c2er2x
(e) (1+x)+ex
(f) 1 +e2x 1−x
Solution:
(a) See 1b.
(b) Let’s first write the power series:
ex3 =1+(x3)+ 1(x3)2 + 1(x3)3 + 1(x3)4 +… 2! 3! 4!
=1+x3 + 1×6 + 1×9 + 1×12 +… 2! 3! 4!
So the coefficient of x3n is 1 . However, we want the coefficient as a3n , so we need
n!
to write 1 as a3n . To do this, we simply solve 1 = a3n
(3n)!
for a3n, which gives us
n! (3n)!
n! (3n)!
a3n = (3n)!. n!
Of course, a3n+1 = a3n+2 = 0, so our sequence is
1,0,0,3!,0,0, 6!,0,0, 9!,0,0,… 2! 3!
(c) Our power series is
αeβx =α 1+βx+ 2!x2 + 3!x3 + 4!x4 +…
So the sequence of coefficients is
α,αβ,αβ2,αβ3,αβ4,…
β2 β3 β4
(d) We can find our answer immediately using the previous result. The sequence is (c1 +c2),(c1r1 +c2r2),c1r12 +c2r2,c1r13 +c2r23,c1r14 +c2r24,…
(e) We have
1+x+ex =1+x+1+x+ 1×2 + 1×3 + 1×4 +… 2! 3! 4!
so the sequence is
2,2,1,1,1,1,1,…
(f) Recall from 1d that 1 corresponds to the sequence 0!, 1!, 2!, 3!, 4!, . . . . We also 1−x
know that e2x corresponds to 20, 21, 22, 23, 24, . . . . So we simply add these together to get our sequence of coefficients:
0!+20,1!+21,2!+22,3!+23,4!+24,…
3. 8.4 question 49 in Rosen: A coding system encodes messages using strings of octal (base 8) digits. A codeword is considered valid if and only if it contains an even number of 7s.
(a) Find a linear inhomogeneous recurrence relation for the number of valid codewords of length n. What are the initial conditions?
(b) Solve this recurrence relation using exponential generating functions.
(c) Determine the number of valid codewords of length n using the product rule for exponential generating functions (i.e. without using your recurrence from part a).
Solution:
(a) Let an be the number of valid codes of length n. We can break this into cases based on the first digit of our code.
Case 1: If the first digit is not a 7, then the number of ways to fill the remaining code is an−1. Since there are 7 options for the first digit in this case, this gives the term 7an−1.
Case 2: If the first digit is 7, then the remaining n − 1 digits must be a code with an odd number of 7s. The number of codes of length n−1 with an odd number of 7s is 8n−1 − an−1 since 8n−1 is the total number of codes and an−1 is the number of codes with an even number of 7s.
Hence,
an = 7an−1 + 8n−1 − an−1 = 6an−1 + 8n−1.
We only need one initial condition since the recurrence only depends on one previous term. There is 1 way to make a code with no digits, hence, a0 = 1.
(b) We will solve this using normal generating functions since it will be a bit eas- ier than with exponential generating functions. We use the same technique as outlined in tutorial 3:
a1x = 6a0x + 80x a2x2 = 6a1x2 + 81×2 a3x3 = 6a2x3 + 82×3 a4x4 = 6a3x4 + 83×4 a5x5 = 6a4x5 + 84×5
.
Adding these equations together, we get
A(x) − a0 = 6xA(x) + B(x)
where B(x) corresponds to the sequence 0, 1, 8, 82, 83, 84, . . . . To get this sequence, we replace x by 8x, then multiply by x to shift over one. Hence,
So we have
B(x)= x . 1−8x
A(x)−a0 = 6xA(x)+ x 1−8x
A(x)=a0+ x
1−6x (1−8x)(1−6x)
1 1 1 1 1 A(x)=1−6x+ 2 1−8x− 2 1−6x
111 A(x)=2 1−6x+1−8x .
The corresponding sequence is
160 +80,161 +81,162 +82,163 +83,… 2222
Hence, the number of valid codes of length n is 6n+8n . 2
(b) continued:
(c) Let E0(x),E1(x),…,E7(x) be the corresponding EGF for the digits 0,1,…,7 respectively. Then
E0(x) = E1(x) = ··· = E6(x) = ex,
since there are no restrictions on these digits. On the other hand,
E7(x)=1+ 1×2 + 1×4 + 1×6 +…, 2! 4! 6!
since the number of 7s must be even. We know from 1b that
ex + e−x E7(x) = 2
Now multiplying the EGFs together gives:
.
E0(x)E1(x)…E7(x)=(ex)7ex +e−x 2
= e7x ex + e−x 2
= 1e8x +e6x. 2
And so an = 1 (8n + 6n). 2
4. How many strings in {0, 1, 2, 3}n have an even number of zeros, at least one digit that is a 1, and at most two digits that are 3?
Solution: Let E0(x), E1(x), E2(x), E3(x) be the EGFs for each individual digit. Then E0(x)=1+ 1×2 + 1×4 + 1×6 +···= ex +e−x
E1(x)=0+x+ 1×2 + 1×3 + 1×4 +···=ex −1 2! 3! 4!
E2(x) = ex E3(x)=1+x+ 1×2.
2! 4! 6! 2
2! Now we multiply these together:
E0(x)E1(x)E2(x)E3(x)= =
x x2
ex+e−x x
2 (e −1)(e ) 1+x+ 2
ex 4
ex +e−x(ex −1)2+2x+x2. Expanding this is a bit annoying. We end up with 12 terms:
12e3x +2xe3x +x2e3x −2e2x −2xe2x −x2e2x +2ex +2xex +x2ex −2−2x−x2 4
The terms correspond to the following sequences:
2·30,2·31,2·32,2·33,…,2·3n … 0,2·1·31,2·2·32,2·3·33,…,2·n·3n … 0,0,2·1·32,3·2·33,4·3·34,…,n(n−1)·3n,…
−2·20,−2·21,−2·22,−2·23,…,−2·2n … 0,−2·1·21,−2·2·22,−2·3·23,…,−2·n·2n … 0,0,−2·1·22,−3·2·23,−4·3·24,…,−n(n−1)·2n,… 2,2,2,2,…
0,2·1,2·2,2·3,…,2·n… 0,0,2·1,3·2,4·3,…,n(n−1),…
−2,−2,−2,0,0,0,0,0,…
So the general term, i.e. the number of valid strings of length n, is:
1((2+2n+n(n−1))3n −(2+2n+n(n−1))2n +(2+2n+n(n−1))) 4
Simplifying gives us
(n+1)(n+2)(3n −2n +1). 4
4 continued:
5. More binomial identities
(a) Show that n n(−1)k = 0.
k=0 k
(b) Show that m n(−1)k = n−1(−1)m.
k=0 k m Hint: bijective counting
Solution:
(a) Noticethat(−1)k =1ifkisevenand(−1)k =−1ifkisodd. Sowecanrewrite this identity as
n n k= k.
0≤k≤n 0≤k≤n k even k odd
Notice that the left hand side counts the number of n-bit strings with an odd number of 1s, and the right hand side counts the number of n-bit strings with an even number of 1s. So, to prove that these two terms are equal, we just need to find a bijection between n-bit strings with an even number of 1s and those with an odd number of 1s. Let En be the set with an even number of 1s and On be the set with an odd number of 1s. Now let f be a function on n bit strings which flips the first digit. For example, if n = 4 then f(1001) = 0001. Then this is certainly a valid function from En to On since the number of 1s always changes by 1. Furthermore, f−1 = f is a valid function from On to En. Hence, f and f−1 define a bijection between En and On, meaning |En| = |On|.
(b) This problem is fairly similar to part (a). Let En,m be the set consisting of all subsets of [n] = {1, .., n} with an even element subsets and at most m elements, and let On,m be the set consisting of all subsets of [n] with an odd number of elements and at most m elements.
In this language, note that the identity we are trying to prove is |En,m| − |On,m| = (−1)mn − 1
m
To see that this is the case we consider the symmetric difference A∪{n} 1∈/A
f(A)=A△{n}= A\{n} 1∈A
and note that f(A) is an involution that maps En,n to On,n, and so is a bijection between these sets (so far this is the same as what’s going on in part (a), just with different notation).
Now, we case on whether m is even or odd.
Case 1: m is odd. In this case f is a bijection between En,m and On,m \ [n−1],
m
where [n−1] = {A ⊂ [n − 1] : |A| = m}. This is because the only cardinality m
m subsets in f(En,m) must have come from members of [n−1], but every other m−1
element of On,m gets mapped to. Therefore, we see that |En,m| = |On,m| − n−1, m
which is what we desired.
Case 2: m is even. By exactly the same logic as in case 1 we see that f is
a bijection between En,m \ [n−1] and On,m, and so we know that in this case m
|En,m| − n−1 = On,m, finishing the proof. m
6. How many subsets A ⊆ {1, …, 50} have a∈A a ≥ 638? Hint: use a bijection.
Solution: At first this problem might seems impossible, but we should investigate the number 638 for a clue. Notice that 50 k = 50·51 = 1275. So if we pick a set A such
k=1 2
that a∈A a ≥ 638, then b∈Ac b ≤ 1275−638 = 637. So if the sum of elements in A is
at least 638, then the sum of elements in Ac is at most 637. So let f be a function which takes any A ⊆ [50] to Ac. Then f defines a function from subsets whose elements sum to ≥ 638 to subsets whose elements sum to ≤ 637. Furthermore, f−1 = f, meaning f defines a bijection. Therefore, exactly half of the subsets of [50] are such that the elements sum to ≥ 638. So the solution is
|P([50])| = 249 2