[SOLVED] CS Math 340 Tutorial 4 Solutions

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
its not obvious that n+1 n is an integer.
(a) Give a combinatorial proof that kn = (n k + 1) n
2n k 2n k1 (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 k1 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 kn, and also (nk+1) n , and hence the expressions are the equal. k k1
(b) First we substitute n for 2n to get that k2n=(2nk+1) 2n .
Next, let k = n. This gives
k k1 n2n=(n+1) 2n .
n n1 Lastly,weknowthatn= n ,meaning2n =2n . Hence,
k nk n1 n+1 n2n=(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 2n2n= 2n 2n n+1nnn+1n
n 12n= 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 coecient of xn in A(x) as a
child getting n cookies. Our task then is to find the coecient 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 1x (1x)5
generating function can be derived from 1 by first taking 4 derivatives to get 234 5 1x
(1x)5 , then multiplying by x /(234). Taking 4 derivatives gives us the following sequence:
1234,2345,3456,4567,,(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
234 234 234 234
(n4)(n3)(n2)(n1) = (n1)! = n1 . 234 4!(n5)! 4
Hence, the coecient of x12 is 11, which is the number of ways to distribute the
cookies.
A(x) = x2 and (A(x))5 = x10 . Hence, the coecient of xn in part (a) is now
1x (1x)
the coecient of xn+5. So the coecient of xn+5 = n1 , meaning the coecient
12 7+5 6 4
of x , i.e. the coecient 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 coecient of
(1x)5
xn is part (a) is now the coecient of xn+10. Hence, the coecient 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 coecient 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 coecient 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) = Pn0 cnxn.
(b) Prove that Petorians can make always make change for $n, so long as n > 1.
Solution:
(a) Lets 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 coecient 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 1x2
B(x) = 1 1x3
D(x) = 1 1x5
E(x) = 1 1x7
1 (1x2)(1x3)(1x5)(1x7)
C(x) =
(b) We could expand C(x) via partial fractions and show that the coecient of xn is greater than 0 for all n > 1. However, that would be insane, and also the question doesnt 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.