Math 340 Tutorial 4 Solutions
1. The number of Dyck paths on an n ⇥ n grid is Cn = 1 2n . Without knowing this, 1 2n n+1 n
it’s not obvious that n+1 n is an integer.
(a) Give a combinatorial proof that k n = (n k + 1) n
2n k 2n k 1 (b) Use(a)toshowthat(n+1) n+1 =n n .
(c) Use (b) to derive a formula for 1 2n , and conclude that Cn is an integer. n+1 n
Solution:
(a) Suppose we are choosing a team of size k, chosen from a group of size n, where
one member of the team is distinguished as the captain. Then we could choose
the team in n ways, then choose the captain in k ways. Or, we could first choose k n
all members of the team who are not the captain in k 1 ways. Then, from the remaining n k + 1 people, we choose the captain of the team. Therefore, the number of ways to choose a team and a captain is k n , and also (n k+1) n , and hence the expressions are the equal. k k 1
(b) First we substitute n for 2n to get that k✓2n◆=(2n k+1)✓ 2n ◆.
Next, let k = n. This gives
k k 1 n✓2n◆=(n+1)✓ 2n ◆.
n n 1 Lastly,weknowthat n = n ,meaning 2n = 2n . Hence,
k n k n 1 n+1 n✓2n◆=(n+1)✓ 2n ◆.
n n+1 (c) Rearranging the expression in part (b) gives
n ✓2n◆=✓2n◆. n+1 n n+1
Next, we subtract 2n from both sides: n
n ✓2n◆ ✓2n◆=✓ 2n ◆ ✓2n◆ n+1nnn+1n
✓ n 1◆✓2n◆=✓ 2n ◆ ✓2n◆ n+1nn+1n
✓ 1 ◆✓2n◆=✓ 2n ◆ ✓2n◆ n+1nn+1n
1 ✓2n◆=✓2n◆ ✓ 2n ◆. n+1 n n n+1
Therefore, Cn =
1 2n is an integer. n+1 n
Question 1 continued:
2. Suppose we are tasked with distributing 12 identical cookies among 5 children. Use generating functions to count how many ways we can do this if:
(a) Each child gets at least 1 cookie. (b) Each child gets at least 2 cookies. (c) Each child gets at least 3 cookies. (d) Each child gets at most 3 cookies.
Solution:
(a) Let A(x) = x+x2 +x3 +…. Then we interpret the coe cient of xn in A(x) as a
child getting n cookies. Our task then is to find the coe cient of x12 in (A(x))5.
The closed form of A(x) is x . Hence, the closed form of (A(x))5 is x5 . This 1 x (1 x)5
generating function can be derived from 1 by first taking 4 derivatives to get 2⇤3⇤4 5 1 x
(1 x)5 , then multiplying by x /(2⇤3⇤4). Taking 4 derivatives gives us the following sequence:
1⇤2⇤3⇤4,2⇤3⇤4⇤5,3⇤4⇤5⇤6,4⇤5⇤6⇤7,…,(n+1)(n+2)(n+3)(n+4),…
Then, multiplying by x5/(2 ⇤ 3 ⇤ 4) gives
0, 0, 0, 0, 0, 1 ⇤ 2 ⇤ 3 ⇤ 4 , 2 ⇤ 3 ⇤ 4 ⇤ 5 , 3 ⇤ 4 ⇤ 5 ⇤ 6 , . . . , (n 4)(n 3)(n 2)(n 1) , . . .
Notice that
4
(b) This is essentially the same problem except now A(x) = x2 + x3 + x4 + . . . . So
2⇤3⇤4 2⇤3⇤4 2⇤3⇤4 2⇤3⇤4 ✓ ◆
(n 4)(n 3)(n 2)(n 1) = (n 1)! = n 1 . 2⇤3⇤4 4!(n 5)! 4
Hence, the coe cient of x12 is 11 , which is the number of ways to distribute the
cookies.
A(x) = x2 and (A(x))5 = x10 . Hence, the coe cient of xn in part (a) is now
1 x (1 x)
the coe cient of xn+5. So the coe cient of xn+5 = n 1 , meaning the coe cient
12 7+5 6 4
of x , i.e. the coe cient of x , is 4 , which is the number of ways to distribute
the cookies.
(c) Same process as before. This time we have x15 . So what was the coe cient of
(1 x)5
xn is part (a) is now the coe cient of xn+10. Hence, the coe cient of x12 = x2+10
is 15 = 0. This makes sense as we cannot give each child 3 cookies, since we only have 12.
(d) Now, A(x) = 1 + x + x2 + x3, since a child cannot receive 4 or more cookies. So (A(x))5 = (1 + x + x2 + x3)5. We can calculate the coe cient of x12 by first expanding the expression like so:
(1+x+x2 +x3)(1+x+x2 +x3)(1+x+x2 +x3)(1+x+x2 +x3)(1+x+x2 +x3).
Every term in the expanded expression is found by choosing a term from each expression in brackets. For example, choosing 1, x, x, x2, x3 gives us a term x7 in the expansion (think of the FOIL method). So we need to figure out how many choices result in a term of x12. For example, 1, x3, x3, x3, x3 gives us x12. There are only a few combinations of numbers that work:
0,3,3,3,3 1,2,3,3,3 2,2,2,3,3
There are 5 ways to arrange the first set of numbers, 5 ⇤ 4 ways to arrange the second set of numbers, and 52 = 10 ways to arrange the third set of numbers. All together, this gives 35 terms of x12. Hence, the coe cient of x12 is 35, which is the number of ways to distribute the cookies.
Question 2 continued:
3. In the strange country of Petoria, money is distributed only in $2, $3, $5, and $7 coins. Let cn be the number of ways for a resident of Petoria to make change for $n.
(a) Give the closed form of the generating function C(x) = Pn 0 cnxn.
(b) Prove that Petorian’s can make always make change for $n, so long as n > 1.
Solution:
(a) Let’s first define the generation functions:
A(x)=1+x2 +x4 +x6 +… B(x)=1+x3 +x6 +x9 +… D(x)=1+x5 +x10 +x15 +… E(x)=1+x7 +x14 +x21 +…
Then the coe cient of xn is A(x) is the number of ways you can make change with $2 coins. Similarly, B(x),D(x) and E(x) correspond to 3,5, and 7 respectively. The closed forms of the generating functions are as follows:
Hence,
A(x) = 1 1 x2
B(x) = 1 1 x3
D(x) = 1 1 x5
E(x) = 1 1 x7
1 (1 x2)(1 x3)(1 x5)(1 x7)
C(x) =
(b) We could expand C(x) via partial fractions and show that the coe cient of xn is greater than 0 for all n > 1. However, that would be insane, and also the question doesn’t specify how to prove the claim. Hence, we will prove this by induction:
Base Case: We can obviously make change for $2 and $3.
Inductive Assumption: Suppose we can make change for $n and $(n + 1) where
n 2.
Inductive Step: We can make change for $(n + 2) via making change for n and adding a $2 coin. Similarly, we can make change for $(n + 3) by making change for n+1 and adding a $2 coin.
Therefore, we can make change for $n if n > 1.
Question 3 continued:
4. Let a(r, n) be the number of ways of choosing r elements from a set of size n, where we are allowed to choose the same element multiple times.
(a) Determine the value of a(r, n) by using a combinatorial argument. (b) Determine the value of a(r, n) using generating functions.