1−xN+1
1−x =1+x+x2 +…+xN
1 ∞
1−x= xn n=0
r ∞rn
(1+x) =
n x
n=0
1 ∞ n + r − 1 n
(1−x)r =
n=0
n x
√ ∞ 2n (−1)n+1
1+x=
n 4n(2n−1)xn
n=0
e x = ∞ x n n=0 n!
ex+e−x ∞ x2n
cosh(x) = 2 =
n=0
(2n)!
ex − e−x ∞ x2n+1 sinh(x) = 2 = (2n + 1)!
n=0
Question 1
How many integers 1 ≤ n ≤ 1000 are neither perfect squares, perfect cubes, nor multiples of 7?
Solution: Let X ={n∈N|1≤n≤1000} and
A={n∈X |n is a perfect square} B = {n ∈ X | n is a perfect cube} C ={n∈X |n is a multiple of 7}.
We want to count |X \ (A ∪ B ∪ C)|. By the complement and inclusion-exclusion princi- ples, that’s the same as counting
|X| − |A| − |B| − |C| + |A ∩ B| + |A ∩ C| + |B ∩ C| − |A ∩ B ∩ C| So let’s count each of those sets individually.
|X| = 1000,obviously! √
|A| = ⌊√1000⌋ = 31, because 322 = 1024 is the rst square > 1000 |B| = ⌊ 3 1000⌋ = 10, similarly
|C | = ⌊1000/7⌋ = 142, because 143 × 7 = 1001 is the rst multiple of 7 that’s > 1000
|A ∩ B| = ⌊√6 1000⌋ = 3, because n is a perfect square and cube i it’s a perect sixth power
|A ∩ C| = ⌊√1000/7⌋ = 4, because (7k)2 ≤ 1000 i k ≤ √1000/7
|B ∩ C| = ⌊√3 1000/7⌋ = 1, similarly |A∩B∩C|=0,because 76 >1000.
Plugging those numbers in the expression above, we nd the answer: 825 numbers. Question 2
(a) Find an algebraic proof the following identity.
n−1 n n n2 = kk
k=1
(b) Find a combinatorial proof of the same identity.
Solution:
(a) By the binomial theorem: (x + 1) =
k=0 Dierentiating both sides, we nd: n(x + 1) =
k kx . n−1 n n
k=1 Plugging-in x = 1, we get the expected answer: n2 =
k k .
n nnk
k x .
n−1 n n k−1
k=1
(b) We will show that both sides of the equation count the number of ways to form a committee with a president, from a population with n individuals.
• LHS: We have n ways of choosing the president. Then, for the (n − 1) other individuals, they have the option of being on the committee or not, so 2n−1 options in total. By the product principle, that’s n2n−1 possible committees.
• RHS: We rst choose the size k ∈ {1…n} of the committee. For each k, we must select the k individuals that will form the commitee: that’s n options.
k
Once the people are chosen, we must elect a president among them, and there are k options for that. So there are kn committes of k people. Summing up
n n k for all k, we nd k=1 k k committees.
Question 3
Use the Generating Functions Method to solve the recurrence an = 3an−1 + 4n with initial condition a0 = 1.
Solution: Let
∞
A(x) = anxn. n=0
Then the recurrence relation gives the identity
∞∞ 4x A(x)=a0+anxn.=1+(3an−1+4n)xn =1+3xA(x)+1−4x.
n=1 n=1 Rearranging this to solve for A(x), we get
A(x) = 1 . (1−4x)(1−3x)
Wenowneedtosplitthelastterminto A + B forsomeAandBthatsatisfyA+B=1 1−4x 1−3x
and3A+4B=0. Hence,A=4andB=−3. Pluggingthisingives
Hence,
43∞∞∞ A(x)=1−4x−1−3x=44nxn−33nxn =(4n+1−3n+1)xn
n=0 n=0 n=0
an = 4n+1 − 3n+1 .
Question 4
Use an Exponential Generating Function to count the number of strings of length n over the alphabet {0, 1, 2} with an even number of `0′ and an odd number of `1′.
Solution:
Let G0(x) be the exponential generating function with coecients representing the number of strings of all zeros with an even length. Let G1(x) have coecients representing the
number of strings of all ones such that the number of ones is odd. Similarly, let G2(x) enumerate the number of strings of all twos.
Then G0(x) has even coecients 1 and odd coecients 0, G1(x) has odd coecients 1 and even coecients 0, and G2(x) has all coecients being 1. Hence:
∞ x2n+1 ex − e−x
G0(x) =
G1(x) =
G2(x) =
The solution is attained by multiplying the generating functions together. Doing so gives:
G0(x)G1(x)G2(x) = e3x − ex 4
Hence, the number we seek is an =
(2n + 1)! = 2 ∞x2n ex+e−x
n=0
(2n)! = 2 ∞ x n
n=0
n=0
n! = ex
∞∞ 1 (3x)n (−x)n
=4 n!− n! n=1 n=1
=∞ 3n−(−1)nxn n=1 4 n!
3n − (−1)n 4 .
Question 5
A function f : {0,1…n} → {0,1…n} is called nilpotent if for all x ∈ {0,1…n}, there is a number k0 such that for all k ≥ k0, fk(x) = 0. Here fk denotes the k-th iterate: f k = f ◦ f ◦ · · · ◦ f (k times).
(a) Show that the function f dened by the following table is nilpotent.
(b) Show that if f : {0,1…n} → {0,1…n} is nilpotent, then we can simply take k0 =ninthedenition,i.e. showthatforallxandforallk≥n,fk(x)=0.
Hint: One of the key steps here might be the Pigeonhole Principle…
(c) Apply Joyal’s bijection to the function in part (a) and draw the corresponding vertebrate.
(d) Generalizethisexampletoshowthatthenumberofnilpotentfunctionson{0,1…n} is (n + 1)(n−1).
x
012345
f (x)
040422
Solution:
(a) We can check directly that:
f(0) = 0
f3(1) = f2(4) = f(2) = 0
f(2) = 0
f3(3) = f2(4) = f(2) = 0 f2(4) = f(2) = 0
f2(5) = f(2) = 0
Moreover, since f(0) = 0, an easy induction shows that k < l and fk(x) = 0 implies fl(x) = 0. So by taking k0 = 3, the denition of a nilpotent function is satised by the function f.
(b) Let f be nilpotent, with k0 as in the denition, and let f0(x) = x. It suces to show that for all x, there exists k ∈ {0,1...n} such that fk(x) = 0 (then l ≥ n ≥ k implies fl(x) = 0 by the remark above).
So suppose the contrary. Let x be such that fk(x) ̸= 0 for all k ∈ {0,1...n}. So there are (n + 1) values of k (pigeons) for which fk(x) can only take n possible values (holes), namely, fk(x) ∈ {1...n}. By the Pigeonhole Principle, there are at least two pigeons, a < b, in the same hole, meaning fa(x) = fb(x). There remains to show that this is impossible.
Let p = b−a. Then we can easily show by induction that for all m ∈ N, fa+mp(x) = f(x). In other words, the orbit is p-periodic, or it has a cycle of length p. Take m such that a+mp > k0. Then we conclude fa(x) = fa+mp(x) = 0 by denition of k0. This contradicts the fact that fk(x) ̸= 0 for k ≤ n.
(c) Note that 0 is the only periodic point of that function. So 0 is both the front and the rear end of the spine. We then get the following vertebrate.
2 45
31
(d) A nilpotent can never have any periodic point except for 0 (which is a xed point), because that would lead to the same contradiction as in (b). Hence, the resulting vertebrate will always have 0 as both front and rear end of its spine. So we do not need to memorize the spine: the only dierence between two vertebrates that comes from two dierent nilpotent functions is their tree structure.
0
In other words, Joyal’s bijection restricted to nilpotent function is a bijection between nilpotent functions and labelled trees, with label set {0, 1 . . . n}. That’s (n+1) labels, do by Cayley’s formula, there are (n + 1)(n+1)−2 = (n + 1)n−1 such trees.