* The preview only shows a few pages of manuals at random. You can get the complete content by filling out the form below.
Description
DEPARTMENT OF MATHEMATICS, IIT Guwahati MA221: Discrete Mathematics Summary of Lectures
3
Combinatorics
Pigeonhole Principle: Version 1: If n + 1 pigeons stay in n holes, then there is a hole with at least two pigeons. Version 2: If kn + 1 pigeons stay in n holes, then there is a hole with at least k + 1 pigeons. Version 3: If p1 + p2 + . . . + pn + 1 pigeons stay in n holes, then there is a i such that the i-th hole contains at least pi + 1 pigeons. Example 3.1. If 7 points are chosen inside the unit circle, then show that some two points have distance at most one. [Hint: Perimeter of unit circle is less than 7.] Example 3.2. If more than half of the integers from J2n are selected, then show that some two of the selected integers have the property that one divides that other. Example 3.3. In every collection of n positive integers, not necessarily distinct, there is a sub-collection of these integers whose sum is divisible by n. Solution. Let us denote the n integers by x1 , x2 , . . . , xn . Consider the sums si =
i X
xj , for i = 1, 2, . . . , n.
j=1
If some si is divisible by n, then we are done. Otherwise, let si = qi n + ri , where we must have 1 ≤ ri ≤ n − 1 for i = 1, 2, . . . , n. Since we have n numbers r1 , r2 , . . . , rn chosen from the set
{1, 2, . . . , n − 1} of n − 1 numbers, by Pigeonhole Principle, we find that rk = rl for some k, l such that 1 ≤ k < l ≤ n − 1. Now we have
xk+1 + . . . + xl = sl − sk = (ql − qk )n. So, {xk+1 , . . . , xl } is a sub-collection of these integers whose sum is divisible by n.
Thus, we have seen that there is a sub-collection, of the set {x1 , x2 , . . . , xn } of integers,
whose sum is divisible by n.
Example 3.4. A child watches TV at least 1 hour each day for 7 weeks but never more than 11 hours in any one week. Prove that there is some period of consecutive days in which the child watches exactly 20 hours of TV. (It is assumed that the child watches TV for a whole number of hours each day.) Solution. Let the child watches TV xi hours on the i-th day. Let a1 = x1 and ai = x1 + . . . + xi for i = 2, 3, . . . , 49. The sequence of numbers a1 , a2 , . . . , a49 is strictly increasing, since the child watches TV at least 1 hour each day. Moreover, a49 ≤ 11 × 7 = 77, since the child never watches more than 11 hours of TV in any one week. Hence we have
a1 < a2 < a3 < . . . < a49 .
Now the sequence a1 + 20, a2 + 20, . . . , a49 + 20 is also strictly increasing so that 21 ≤ a1 + 20 < a2 + 20 < a3 + 20 < . . . < a49 + 20 ≤ 97. Thus each of the 98 numbers a1 , a2 , . . . , a49 , a1 + 20, a2 + 20, . . . , a49 + 20 is an integer between 1 and 97. Hence by Pigeonhole Principle, some two of them must be equal. Since no two of the numbers a1 , a2 , . . . , a49 are equal and since no two of the numbers a1 + 20, a2 + 20, . . . , a49 + 20 are equal, there must be an i and j such that ai = aj + 20. Therefore, on days j + 1, j + 2, . . . , i, the child watches exactly 20 hours of TV. Addition Rule of Counting (The Rule of Disjunctive Counting): Suppose a set is partitioned into parts S1 , S2 , . . . , Sn . Then |S| = |S1 | + |S2 | + . . . |Sn |. Multiplication Rule of Counting (The Rule of Sequential Counting): Let S = S1 × S2 × . . . × Sn . Then |S| = |S1 | × |S2 | × . . . × |Sn |. Example 3.5. The number of ways a man, woman, boy and a girl can be selected from 5 men, 6 women, 2 boys and 4 girls is 5 × 6 × 2 × 4 = 240. But the number of ways to select one person
is 5 + 5 + 2 + 4 = 17.
Example 3.6. Determine the number of positive integers that are factors of 34 × 52 × 117 × 138 . [Ans. (4 + 1)(2 + 1)(7 + 1)(8 + 1)]
Example 3.7. How many 3-digit natural numbers can be formed such that all the digits have the same parity. [Ans. (5 × 5 × 5) + (4 × 5 × 5)] Example 3.8. Find the number of 5-digit positive integers that contain the digit 6 exactly once. [Ans. (1 × 9 × 9 × 9 × 9) + 4 × (8 × 9 × 9 × 9 × 1)] Example 3.9. Find the number of 7-digit palindromic positive integers such that no digits appear more than twice. [Ans. 9 × 9 × 8 × 7] Definition 3.1. An r-permutation of an n-set S is an arrangement of r distinct elements of S in a row. An r-permutation may be viewed as a one-one function f : Jr −→ S. P (n, r) denotes the number of r-permutations of an n-set. Theorem 3.1. P (n, r) =
n! . (n−r)!
By convention, P (n, 0) = 1.
Definition 3.2. An r-combination of an n-set S is an r-subset of S. C(n, r) denotes the number of r-combinations of an n-set. Theorem 3.2. C(n, r) =
P (n,r) r!
=
n! . r!(n−r)!
Example 3.10. Find the number of one-one functions from Jm into Jn . [P (n, m) if n ≥ m.] Example 3.11. Find the number of subsets of J2n+1 with at most n elements.
Solution.
Let A = {A : A ⊆ J2n+1 c
c
and |A| ≤ n}. We need to determine |A|. If A ∈ A,
then clearly A ∈ A , and vice versa. Thus A 7−→ Ac is a bijection between A and Ac , and therefore |A| = |Ac |. However, P(J2n+1 ) = A∪Ac , a disjoint union. Hence |A| = 21 .22n+1 = 22n .
Example 3.12. Use the idea of C(n, r) to show that the product of any k consecutive natural numbers is divisible by k!. Solution. Let the k consecutive natural numbers be a, a + 1, a + 2, . . . , a + (k − 1). Then we
have
a(a + 1)(a + 2) . . . (a + k − 1) = C(a + k − 1, k). k!
Since C(a + k − 1, k) is always a non-negative integer, we conclude that
a(a+1)(a+2)...(a+k−1) k!
is
also a non-negative integer. Hence a(a + 1)(a + 2) . . . (a + k − 1) is always divisible by k!. Example 3.13. In how many ways may n girls and n boys be seated in a row of 2n seats, if the two sexes must alternate? [2(n!)2 ] Definition 3.3. A circular permutations is an arrangements of distinct objects around a circle. Example 3.14. Find the number of circular permutations of n distinct objects. [(n − 1)!] Example 3.15. Give a combinatorial proof of 1. C(m + n, 2) − C(m, 2) − C(n, 2) = mn; 2. C(2n, 2) = 2C(n, 2) + n2 ; 3. C(n, r) = C(r, r)C(n − r, 0) + C(r, r − 1)C(n − r, 1) + . . . + C(r, 0)C(n − r, r); 4. C(n, r) = C(n − 1, r) + C(n − 1, r − 1). [Pascal’s Identity] Solution. 1. Let A and B be two disjoint sets of sizes m and n, respectively. Clearly, |A × B| = mn. Now an element (a, b) of A × B uniquely corresponds to a 2-element subset {a, b} of A ∪ B such that a ∈ A and b ∈ B, and vice-versa. Therefore
mn =number of 2-element subsets {a, b} of A ∪ B such that a ∈ A and b ∈ B =[number of 2-element subsets of A ∪ B] − [number of 2-element subsets {a, b} of A ∪ B such that a, b ∈ A] − [number of 2-element subsets {a, b} of A ∪ B such that a, b ∈ B] =C(m + n, 2) − C(m, 2) − C(n, 2). 2. Let X be any set with 2n elements that is partitioned into two sets Y and Z, each containing n elements. The number of subsets of X with two elements is C(2n, 2). Any subset of X has two elements if and only if it belongs to one of the following three classes: (1) the class of all subsets of Y with two elements, (2) the class of all subsets of Z with two elements, and (3) the class of all subsets of X with two elements such that each subset in this class has one element from Y and one element from Z. Classes (1) and (2) have C(n, 2) elements each. An element from Y can be chosen in n ways and an element
from Z can also be chosen in n ways. So, class (3) has n × n = n2 sets. Thus the number of subsets of X with two elements is C(n, 2) + C(n, 2) + n2 . Thus we have seen that C(2n, 2) = 2C(n, 2) + n2 . 3. Consider two disjoint sets A and B such that |A| = r, |B| = n − r, so that |A ∪ B| = n. We can select r elements from A ∪ B in C(n, r) ways. We can also select these r
elements by selecting j elements from A and r − j elements from B, where j can be any
one of the numbers r, r − 1, . . . , 1, 0. That is, we can select r elements from A ∪ B in C(r, r)C(n − r, 0) + C(r, r − 1)C(n − r, 1) + . . . + C(r, 0)C(n − r, r) ways. Therefore C(n, r) = C(r, r)C(n − r, 0) + C(r, r − 1)C(n − r, 1) + . . . + C(r, 0)C(n − r, r). 4.
Example 3.16. Find the number of ways of arranging the letters which appear in (a) ELASTIC (b) ASBESTOS . [7! and P (8, 5)] Example 3.17. Let A and B be two particular students in a group of n students. Find the number of ways of assigning the n students in a row of n single rooms such that A and B are in adjacent rooms. [2(n − 1) × (n − 2)!] Example 3.18. Find the number of ways of seating n women and n men at a round table so that between every two women there is a men. [(n − 1)!n!] Example 3.19. Find the number of ways of seating r out of n people around a round table, and the remaining around another round table. [C(n, r)(r − 1)!(n − r − 1)!] Theorem 3.3. Let S be a multi-set with n elements of which ni are of i-th type for i = 1, 2, . . . , k. Then there are
n1 !n2 !
n! ··· ···
nk !
arrangements of the objects in S.
Theorem 3.4. For i = 1, 2, . . . , k, let the i-th group contains ni identical objects and n ≥
k P
ni .
i=1
Then the number of allocations of the objects in n distinct locations l1 , l2 , . . . , ln , each location n!
receiving at most one, is n1 !n2 !
··· ···
nk !(n−
k P
. ni )!
i=1
n!
Definition 3.4. We use P (n; n1 , . . . , nk ) to denote n1 !n2 !
ized r-permutations, where
k P
··· ···
nk !(n−
k P
, called the generalni )!
i=1
ni = r.
i=1
By convention, P (n; n1 , . . . , nk ) = 0 if some ni = 0 or n <
k P
ni .
i=1
Example 3.20. Find the number of ways of putting n distinct objects into m distinct boxes, if the (left-to-right) order of objects within a box is significant and if empty boxes are permitted. Solution. Let the desired number be f (n, m). Suppose that a distribution of n − 1 of such
objects (there are f (n − 1, m) such distributions) brings i1 objects into box 1, i2 objects into box 2, . . . , im objects into box m. Note that
i1 + i2 + . . . + im = n − 1, ik ≥ 0 for k = 1, 2, . . . , m.
Now the n-th object can go into box k in ik + 1 ways, for a total of (i1 + 1) + (i2 + 1) + . . . + (im + 1) = n − 1 + m arrangements. Therefore f (n, m) = (n − 1 + m)f (n − 1, m). Note that f (1, m) = m. Therefore we have f (n, m) = (n+m−1)(n+m−2) . . . (m+1)f (1, m) = (n+m−1)(n+m−2) . . . m =
(n + m − 1)! . (m − 1)!
Example 3.21. Number of non-negative integer solutions to the equation x1 +x2 +. . .+xm = n is C(n + m − 1, m − 1). Solution.
This is a matter of putting n identical 1s into m distinct boxes (an x1 box, an x2
box, . . . , an xm box), empty boxes being allowed. If we temporarily make the 1s distinct by labeling them 11 , 12 , . . . , 1n , then there are
(n+m−1)! (m−1)!
such arrangements. However, arrangements
that differ only with regard to the labels carried by the 1s give the same solution to the given equation. Hence the desired number is (m + n − 1)! = C(n + m − 1, m − 1). (m − 1)!n! Example 3.22. Determine the number of solutions in positive integers to the equation x + y + z + w = 17. Solution.
We want to count the integral solutions to the equation x + y + z + w = 17 such
that x ≥ 1, y ≥ 1, z ≥ 1, w ≥ 1. Let a = x − 1, b = y − 1, c = z − 1 and d = w − 1 so that a ≥ 0, b ≥ 0, c ≥ 0, d ≥ 0. We have
x + y + z + w = 17 ⇒ a + b + c + d = 13. We know that the number of solutions of the equation a+b+c+d = 13 in non-negative integers is C(16, 3) = 560. Hence the required number of solutions is 560. Circular Permutations with Repetition: Example 3.23. Find the number of circular permutations of {A, B, B, C, C, D, D, E, E}. Solution.
After placing A, the remaining letters can be arranged like a linear permutation.
So, the number is
8! . 2!×2!×2!×2!
To answer this type of question in general, we need to make use of Burnside lemma, and Polya’s Enumeration Theorem, in general. A dedicated course on combinatorics is needed to discuss all these things rigorously. Theorem 3.5 (Burnside Lemma). let G be a finite group that acts on a set X. For each g in G let Xg denote the set of elements in X that are fixed by g, i.e., Xg = {x ∈ X : g(x) = x}.
Then
the number of orbits of X =
1 X |Xg |. |G| g∈G
Note that, for counting circular permutations, we need to take G = Zn = {σ i : i =
01, 1 . . . , n − 1}, where σ(k) = k + 1 modulo n, and X = the set of all initial arrangements of the n objects.
Example 3.24. Find the number of circular permutations of {A, B, B, C, C, D, D, E, E}. Solution. Take G = Z9 . These 9 letters can be arranged in r =
9! 1!×2!×2!×2!×2!
ways initially. For
the identity, clearly, |Xe | = |X| = r. Since there is only one A, no non-identity element of G
can fix A. Therefore Xg = ∅ if g 6= e. Now the total number of required circular permutations
is same as the number of orbits of X under this action of Z9 . Thus, this number is 8! 1 1 X . |Xg | = [r + (9 × 0)] = |G| g∈G 9 2! × 2! × 2! × 2! Example 3.25. Find the number of circular permutations of {B, B, C, C}. Solution.
Take G = Z4 . These 4 letters can be arranged in r =
4! 2!×2!
= 6 ways initially. For
the identity, clearly, |Xe | = |X| = 6. Notice that Xσ = ∅ = Xσ3 , whereas |Xσ2 | = 2. Thus, this number is
1 1 X |Xg | = [6 + 0 + 2 + 0] = 2. |G| g∈G 4
Example 3.26. Find the number of circular permutations of {B, B, C, C, D, D}. Solution.
Take G = Z6 . These 6 letters can be arranged in r =
6! 2!×2!×2!
= 90 ways initially.
For the identity, clearly, |Xe | = |X| = 90. Notice that Xg = ∅ for g = σ, σ 2 , σ 4 , σ 5 . However, |Xσ3 | = 3! = 6. Thus, this number is 1 1 X |Xg | = [90 + 0 + 0 + +6 + 0 + 0] = 16. |G| g∈G 6
Example 3.27. Find the number of circular permutations of {B, B, C, C, D, D, E, E}. Solution.
Take G = Z8 . These 8 letters can be arranged in r =
8! 2!×2!×2!×2!
= 3×4×
5 × 6 × 7 ways initially. For the identity, clearly, |Xe | = |X| = r. Notice that Xg = ∅ for g = σ, σ 2 , σ 3 , σ 5 , σ 6 , σ 7 . However, |Xσ4 | = 4! = 24. Thus, this number is 1 X 1 |Xg | = [r + 24 + (6 × 0)] = 318. |G| g∈G 8
In general, when n is large as well as number of different type of objects is large, applying Burnside Lemma is not so practical. However, in the following case, Burnside Lemma can be used easily. Example 3.28. Let n1 + . . . + nk = n. Suppose there are ni identical objects of Type i, for i = 1, 2, . . . , k. If ni does not divide n for at least one i, then the number of circular permutations of these n objects is (n − 1)! . n1 ! × n2 ! × . . . nk !
Solution.
Take G = Zn . These n objects can be arranged in r =
n! n1 !×n2 !...×nk !
ways initially.
For the identity, clearly, |Xe | = |X| = r. Assume that nk does not divide n. Then no matter
how the Type k objects are placed around the circle, no non-identity element of G can fix these nk objects among themselves. Therefore Xg = ∅ if g 6= e. Thus, the required number is 1 X (n − 1)! 1 . |Xg | = [r + 0] = |G| g∈G n n1 ! × n2 ! × . . . nk !
If each ni divides n, then we can use Polya’s Enumeration Theory, in particular, Polya’s Pattern Inventory Theorem. Inclusion-Exclusion Principle: 1. If A and B are finite sets, then |A ∪ B| = |A| + |B| − |A ∩ B|. 2. If the sets A1 , A2 , . . . , Am are finite, then |
m [
i=1
Ai | = s1 − s2 + . . . + (−1)m−1 sm ,
where sk is the sum of the cardinalities of all the k-tuple intersections of the given m sets. Example 3.29. There is a microcomputer in each of the 32 faculty offices in a department. Fifteen of them have color monitors, 10 of them have laser printers, and 8 of them have modems. Two of them have all these three options. At least how many have none of the three options? Solution.
Let C = the set of faculty offices having a color monitor; L = the set of faculty
offices having a laser printer; and M = the set of faculty offices having a modem. Let r be the number of offices with none of these three options. According to the question, |C| = 15, |L| = 10, |M | = 8, |C ∩ L ∩ M | = 2. Since two of them have all these three options,
we find that |C ∩ L| ≥ 2, |L ∩ M | ≥ 2 and |M ∩ C| ≥ 2. Now using the Principle of Inclusion-
Exclusion, we have
r = 32 − (|C| + |L| + |M |) + [|C ∩ L| + |L ∩ M | + |M ∩ C|] − |C ∩ L ∩ M | ≥ 32 − (15 + 10 + 8) + (2 + 2 + 2) − 2 = 3. Hence at least three faculty offices will have none of the color monitors, laser printers and modems. Example 3.30. Find the number of permutations of J8 in which no even integer is in its natural position. Solution.
For i = 2, 4, 6, 8, let Ai = {σ ∈ S8 : σ(i) = i}. Clearly, |S8 | = 8!, |A2 | = |A4 | =
|A6 | = |A8 | = 7!. Also,
|A2 ∩ A4 | = |A2 ∩ A6 | = |A2 ∩ A8 | = |A4 ∩ A6 | = |A4 ∩ A8 | = |A6 ∩ A8 | = 6!, and |A2 ∩ A4 ∩ A6 | = |A2 ∩ A4 ∩ A8 | = |A2 ∩ A6 ∩ A8 | = |A4 ∩ A6 ∩ A8 | = 5!. Now using Inclusion-Exclusion Principle, we find that the required number is 8! − 4 × 7! + 6 × 6! − 4 × 5! + 4! = 24024.
Set Partition: A collection {A1 , A2 , . . . , Ak } of non-empty sets is called a partition of a set A k S if A = Ai and Ai ∩ Aj = ∅ for i 6= j. i=1
Example 3.31.
1. There are 2n−1 − 1 partitions of Jn , n ≥ 2, into two subsets. 2. Number of allocations of 7 students into 7 different project groups so that each group has one student is 7!, but the number of partitions of a set of 7 students into 7 subsets is 1. 3. In how many ways can we write {{1, 2}, {3, 4}, {5, 6}, {7, 8, 9}, {10, 11, 12}} on a piece of paper with the condition that sets have to be written in a row in increasing size? [3!(2!)3 × 2!(3!)2 ] 4. From a partition with pi subsets of size ni such that n1 < n2 < . . . < nk , the number of arrangements we can make is p1 !(n1 !)p1 × . . . . . . pk !(nk !)pk . Theorem 3.6. The number of partitions of Jn with pi subsets of size ni such that n1 < n2 < . . . < nk and in non-decreasing order of the sizes of the blocks, is p1 !(n1
!)p1
n! . × . . . . . . pk !(nk !)pk
Definition 3.5. S(n, r) := the number of partitions of Jn into r subsets. Theorem 3.7. 1. There are r!S(n, r) onto functions from Jn to Jr , where n ≥ r. 2. r!S(n, r) =
r P
i=0
(−1)i C(r, i)(r − i)n . [Prob. 2.22 in Schaum’s]
3. The number of partitions of Jn into non-empty subsets is S(n, 1) + S(n, 2) . . . + S(n, n). Ordinary Generating Function: The ordinary generating function (OGF) for the sequence ∞ P 2 ar x r . (ar )∞ is the formal power series a + a x + a x + . . . = 0 1 2 r=0 r=0
Example 3.32. If ar = C(n, r) for a fixed n, then its OGF is C(n, 0) + C(n, 1)x + . . . + C(n, n)xn = (1 + x)n . Example 3.33. Find the number of integer solutions of a + b + c = 10, where 2 ≤ a, b, c ≤ 4. [Hint: Coefficient of x10 in (x2 + x3 + x4 )(x2 + x3 + x4 )(x2 + x3 + x4 )]
Example 3.34. Let ar be the number of non-negative integer solutions of 2a+3b+5c = r. Find the OGF for (ar ). [Hint: Coefficient of xr in (1+x2 +x4 +. . .)(1+x3 +x6 +. . .)(1+x5 +x10 +. . .)] Theorem 3.8.
1. Let ar be the coefficient of xr in (1 + x + x2 + . . .)n = (1 − x)−n . Then
ar = C(n + r − 1, r).
2. (1 − xm )n = 1 − C(n, 1)xm + C(n, 2)x2m − . . . + (−1)n xnm .
3. (1 + x + x2 + . . . + xm−1 )n = (1 − xm )n (1 + x + x2 + . . .)n . Example 3.35. Find number of integer solutions of a + b + c + d = 27, where 3 ≤ a, b, c, d ≤ 8. [Hint: Coefficient of x27 in (x3 + x4 + . . . + x8 )4 ]
Theorem 3.9. Let f (x) and g(x) be OGF for (ar ) and (br ), respectively. Then 1. Af (x) + Bg(x) is the OGF for (Aar + Bbr ). 2. (1 − x)f (x) is the OGF for ar − ar−1 . 3. (1 + x + x2 + . . .)f (x) is the OGF for (a0 + a1 + . . . + ar ). 4. f (x)g(x) is the OGF for (a0 br + a1 br−1 + . . . + ar b0 ). 5. xf 0 (x) is the OGF for (rar ). Example 3.36. Find the OGF for ar = 3r + 5r2 . [Hint: Use
1 1−x
x(1+x) x = 1 + x + x2 + . . ., Ans. 3. (1−x) 2 + 5. (1−x)3 ]
Example 3.37. Find the OGF of the sequence defined by an+2 − 3an+1 − 4an = 0 with a0 = 1, a1 = 3.
Solution. Let F (x) =
∞ P
an xn . We have
n=0
F (x) =
∞ X
an x n = a0 + a1 x +
=1 + 3x + 3x
an xn = 1 + 3x +
∞ X
n=2 ∞ X n=1
∞ X
(3an−1 + 4an−2 )xn
n=2
n=2
n=0
=1 + 3x + 3x
∞ X
an−1 xn−1 + 4x2
∞ X
an−2 xn−2
n=2
an xn + 4x2
∞ X
an x n
n=0
2
=1 + 3x + 3x[F (x) − 1] + 4x F (x) Thus (1 − 3x − 4x2 )F (x) = 1 ⇒ F (x) =
1 1 = . 2 1 − 3x − 4x (1 − 4x)(1 + x)
Example 3.38. Find the ordinary generating function for the number hn of solutions of the equation x1 + x2 + . . . + xk = n in non-negative odd integers. Solution. We have g(x) = (x + x3 + x5 + . . .) . . . (x + x3 + x5 + . . .) [k factors] = x(1 + x2 + x4 + . . .) . . . x(1 + x2 + x4 + . . .) x x = ... 2 1−x 1 − x2 k x = . (1 − x2 )k Hence the required ordinary generating function is
xk . (1−x2 )k
Example 3.39. Let an be the number of n-letter sequences that can be formed using the letters A, B, and C such that any nonterminal (other than the last entry) A has to be immediately followed by a B. Find the recurrence relation for (an ) and the required initial conditions. Also, ∞ P find a closed form of the OGF an x n . n=1
The possible types of the sequences are AB ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗, B ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ and
Solution.
C ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗. There are an−2 such sequences of the first type, while there are an−1 such
sequences of each of the other two types. Therefore an = 2an−1 +an−2 . For n = 1, the sequences are A, B and C. For n = 2, the sequences are AB, BA, BB, BC, CA, CB and CC. Thus the required recurrence relation is an = 2an−1 + an−2 for n ≥ 3, Let g(x) =
∞ P
a1 = 3, a2 = 7.
an xn . We have
n=1
g(x) =
∞ X
n
2
an x = a1 x + a2 x +
∞ X
n
2
an x = 3x + 7x +
⇒g(x) = 3x + 7x2 + 2x ⇒g(x) = 3x + 7x2 + 2x 2
∞ X
an−1 xn−1 + x2
∞ X
an−2 xn−2
n=3
n=3
∞ X
(2an−1 + an−2 )xn
n=3
n=3
n=1
∞ X
an x n + x 2
n=2
∞ X
an x n
n=1
⇒g(x) = 3x + 7x + 2x[g(x) − 3x] + x2 g(x) ⇒g(x) =
3x + x2 . 1 − 2x − x2
Partition of a Positive Integer: Let p(r) := number of distinct partitions of r; pn (r) := number of distinct partitions of r into parts at most equal to n; = number of non-negative integer solutions of 1x1 + 2x2 + . . . + nxn = r; qn (r) := number of distinct partitions of r into at most n parts; = number of distributions of r identical objects among n identical places, empty places being permitted. For example, p(5) = 7, p2 (5) = 3, q3 (5) = 5. Theorem 3.10. For all r and n, pn (r) = qn (r). Theorem 3.11. The OGF of {pn (r)} and {qn (r)} is Theorem 3.12. The OGF of {p(r)} is
1 . (1−x)(1−x2 )(1−x3 )...(1−xn )
1 . (1−x)(1−x2 )(1−x3 )......
Exponential Generating Function: The exponential generating function (EGF) for the ∞ P a2 2 ar r ar r sequence (ar )∞ is the formal power series a + a x + x + . . . + x + . . . . . . = x. 0 1 r=0 2! r! r! r=0
Example 3.40. Find the EGF for (ar ), where ar = P (n, r). Theorem 3.13. Suppose there are k types of objects. 1. If there are an unlimited supply of objects in each types, then the number of r-permutations using objects from these k types is the coefficient of
xr r!
in the EGF ekx .
2. If the supply of objects in type i is at most ni , then the number of r-permutations using r
objects from these k types is the coefficient of xr! in the EGF x2 x2 x2 xn 1 xn 2 xn k 1+x+ ······ 1 + x + . 1+x+ + ... + + ... + + ... + 2! n1 ! 2! n2 ! 2! nk ! 3. The coefficient of
xr r!
in (ex − 1)n is n!S(r, n).
Proof. We supply a proof of 3. We have n!S(r, n) = number of onto functions f : Jr −→ S = {s1 , s2 , . . . , sn }.
Each such onto functions can be viewed as a word of length r from elements of S such that n P ki = r. For such each si appears at least once. Thus we need a selection of ki ∈ N such that i=1
a particular choice of k1 , k2 , . . . , kn , we have
number of distinct onto functions =
r! . k1 !k2 ! . . . .kn !
Now X
1 x2 r = coefficient of x in (x + + . . .)n = coefficient of xr in (ex − 1)n k1 !k2 ! . . . .kn ! 2! k1 +...+kn =r X r! xr ⇒n!S(r, n) = = coefficient of in (ex − 1)n . k1 !k2 ! . . . .kn ! r! k +...+k =r n
1
Example 3.41. Find the number of ways of accommodating 9 people in 4 rooms such that no room is left unoccupied. [Hint: 4!S(9, 4) = no. of onto functions from J9 onto J4 = coefficient of
x9 9!
in (ex − 1)4 ]
Example 3.42. Find the number of r-permutations that can be formed using the letters that appear in the word MISSISSIPPI so that the number of times a letter appears in a permutation is at most equal to the number of times the letter appears in the word. [Ans. a1 + a2 + . . . + a11 , where ar = r!× the coefficient of xr in (1 + x)(1 + x +
x2 2!
+
x3 3!
+
x4 2 ) (1 4!
+x+
x2 )] 2!
Theorem 3.14. Let F (x) and Fb(x) be the OGF and EGF of a sequence fn , respectively. Then the following holds: ∞ X n=0
n
fn x =
Z∞ 0
Fb(tx)e dt −t
and
∞ X
xn 1 = fn n! 2π n=0
[Source: Wikipedia. Not to be used in this course.]
Zπ
−π
iθ
F (xe−iθ )ee dθ.
Recurrence Relation: The recurrence relation an = c1 an−1 + c2 an−2 + . . . + cr an−r + f (n)
..... .....
(1)
in which c1 , . . . , cr are constants with cr 6= 0, is called a linear recurrence relation with constant
coefficient, of order r.
If f (n) = 0, then (1) is called homogeneous, otherwise it is called non-homogeneous. If g(n) is a function such that g(n) = an for all n ≥ 0, then g(n) is called a solution of (1).
The equation tr − c1 tr−1 − . . . − cr = 0 is called the characteristic equation of (1) and its
roots are called the characteristic roots of (1).
Theorem 3.15. The general solution of (1) is given by an = h(n) + p(n), where h(n) is a general solution of the homogeneous part of (1), and p(n) is a particular solution of (1). Theorem 3.16. Finite linear combination of solutions of an = c1 an−1 + c2 an−2 + . . . + cr an−r is also a solution to this recurrence relation. Theorem 3.17. If α is a root of the characteristic equation of an = c1 an−1 +c2 an−2 +. . .+cr an−r , then an = αn is a solution to this recurrence relation. Theorem 3.18. If α0 , α1 , . . . , αr−1 are the distinct roots of the characteristic equation of an = c1 an−1 + c2 an−2 + . . . + cr an−r , then every solution of this recurrence relation is of the r−1 P pi αin , for some p0 , p1 , . . . , pr−1 ∈ R. form i=0
Further, if r consecutive initial conditions are given, then the solution is unique
Theorem 3.19. If α is a root, of multiplicity m, of the characteristic equation of an = c1 an−1 + c2 an−2 + . . . + cr an−r , then an = (p0 + p1 n + . . . + pm−1 nm−1 )αn is a solution to this recurrence relation. Theorem 3.20. Let the characteristic roots of (1) be t1 , t2 , . . . , tk of respective multiplicities k P hi (n), where m1 , m2 , . . . , mk . Then the general solution of the homogeneous part is h(n) = i=1
hi (n) = (αi0 + αi1 n + αi2 n2 + . . . + αi,mi −1 nmi −1 )tni .
Theorem 3.21. For each i = 1, 2, . . . , k, consider the recurrence relation an = c1 an−1 +c2 an−2 + . . . + cr an−r + fi (n), under the same set of initial conditions. Let gi (n) be a solution to the k P pi gi (n) is a solution to an = c1 an−1 + c2 an−2 + . . . + cr an−r + i-th recurrence relation. Then i=1
k P
i=1
pi fi (n) under the same set of initial conditions, where p1 , . . . , pk ∈ R.
Theorem 3.22. 1. Let f (n) be a polynomial in n of degree d. Then (a) if 1 is not a characteristic root of (1), then (1) has a particular solution p(n) = A0 + A1 n + A2 n2 + . . . + Ad nd . (b) if 1 is a characteristic root of (1) of multiplicity m, then (1) has a particular solution p(n) = nm (A0 + A1 n + A2 n2 + . . . + Ad nd ).
2. Let f (n) = cbn (an exponential in n). Then (a) if b is not a characteristic root of (1), then (1) has a particular solution p(n) = αbn . (b) if b is a characteristic root of (1) of multiplicity m, then (1) has a particular solution p(n) = αnm bn . Note: If f (n) = g(n) + cbn , where g(n) is a polynomial in n, then apply Part 1 and Part 2 above separately for g(n) and cbn , and add the corresponding particular solutions. Similarly, if f (n) = g(n)bn , where g(n) is a polynomial in n, then apply Part 1 and Part 2 above separately for g(n) and cbn , and multiply the corresponding particular solutions. Example 3.43. Solve the following recurrence relations: √ n √ n 1. an = an−1 + an−2 , a0 = a1 = 1. [an = α 1+2 5 + β 1−2 5 , α =
√ 5+ 5 ,β 10
=
√ 5− 5 ] 10
2. an = 3an−1 + 4an−2 − 12an−3 , a0 = 2, a1 = 5, a2 = 13. [Roots are 2, −2, 3, p = 1, q = 0, r = 1.]
3. an = 3an−1 − 2an−2 + 3(5n ), a0 = 1, a1 = 2. [α = −125, β = 26, γ =
25 .] 4
4. an = 3an−1 − 2an−2 + 3(2n ), a0 = 1, a1 = 2. [α = 12, β = −11, γ = 6.] 5. an = an−1 + 12n2 , a0 = 5. 6. sn = −2sn−1 + n − 4, s0 = − 19 . Solution. 6. The characteristic equation of the associated homogeneous recurrence relation sn = −2sn−1 , of the given recurrence relation, is x + 2 = 0, whose only root is x = −2. Hence a general solution of sn = −2sn−1 is of the form un = c(−2)n , where c is any constant.
Now since the term n − 4 is a linear polynomial in n of degree one, let a particular solution
to the given recurrence relation be vn = an + b, where a and b are constant to be determined. Substituting sn = vn = an + b in the given recurrence relation, we have an + b = −2[a(n − 1) + b] + n − 4 = (−2a + 1)n + (2a − 2b − 4).
Thus comparing the coefficients of n and the constant terms of the above equality, we have a = −2a + 1, b = 2a − 2b − 4. Solving these two equations, we get a =
vn = 13 n −
10 9
is a particular solution of the given recurrence relation.
1 3
and b = − 10 . Thus, 9
Now a general solution to the given recurrence relation will be of the form
sn = un + vn = c(−2)n + 31 n −
10 . 9
Since s0 = − 91 , we have − 91 = c(−2)0 + 31 .0 − n
Hence the required solution is sn (−2) +
1 n 3
10 ⇒ 9 10 − 9.
c = 1.
Example 3.44. Use generating function to solve 1. an = 2an−1 + 1, a0 = 1;
[Ans. g(x) =
2. an = 2an−1 − n3 , a0 = 1. [Ans. g(x) =
3−7x+3x2 3(1−x)2 (1−2x)
=
1 3
h
1 1−x
+
1 (1−x)(1−2x)
1 (1−x)2
+
1 1−2x
i
=
2 1−2x
−
1 , 1−x
an = 2n+1 − 1]
, an = 13 (2 + n + 2n )]
3. an = an−1 + an−2 , n ≥ 2, where a0 = 0, a1 = 1. ∞ P
Solution. (3) Let F (x) =
an xn be the generating function for the sequence an . Then we
n=0
have
F (x) = a0 + a1 x +
∞ X
an x n = x +
∞ X
an−2 xn +
= x + x2
∞ X
an−1 xn
n=2 ∞ X
n=2
n=2
∞ X
an x n + x
n=0
an x n ,
(∵ a0 = 0)
n=0
= x + x2 F (x) + xF (x). Thus F (x) = x + x2 F (x) + xF (x) ⇒
∞ X
an x n =
n=0
x 1 − x − x2
−x −1 + = , where α = (x − α)(x − β) 2 β 1 α − = −√ 5 x−α x−β ∞ 1 X xn xn =√ − . 5 n=0 αn β n
Hence
(1 + β n − αn = an = √ n 5(−1)
√
5)n − (1 − √ 2n 5
√
√
5
−1 − , β= 2
5)n
√
5
.
Fibonacci Numbers: The numbers an defined by an = an−1 + an−2 , a0 = a1 = 1 are called Fibonacci numbers. Sometimes, we denote an by f (n) for convenience. Fibonacci introduced these numbers in 1202 and Edouard Lucas made it popular during last half of 19th century. We have 1. an =
√1 5
√ n+1 1+ 5 2
2. Writing φ(x) =
∞ P
−
√ n+1 1− 5 2
.
an xn gives φ(x) =
n=0
3. The EGF of an is
αeαx −βeβx , α−β
1 , 1−x−x2
where α =
the OGF of an .
√ 1+ 5 ,β 2
=
√ 1− 5 . 2
√ 1+ 5 ,β 2
[Use solution of an from Item 1.]
√ 1− 5 2
√
√
√ 5 , B = − 1−√ 5 . and A = 1+ 2 5 2 √5 √ n+1 n+1 − 1−2 5 Putting these values and comparing coefficient of xn , we get an = √15 1+2 5 .
4. Writing φ(x) =
A 1−αx
+
B , 1−βx
we get α =
=
5. (Combinatorial Definition) Let bn = number of subsets (including the null set) of Jn containing no two consecutive integers. Take J0 = ∅ so that b0 = 1. If a subset A is counted in bn , then there are two cases possible.
Case I: (n ∈ / A). There are bn−1 many such subsets. Case II: (n ∈ A). In this case, A−{n} is a subset of Jn−2 that contain no two consecutive integers. There are bn−2 many such subsets.
So, bn = bn−1 + bn−2 for n ≥ 2 and clearly b1 = 2, b2 = 3. Thus bn = an+1 for n ≥ 0. " # " # 1 1 a a n+1 n 6. If A = , then by induction, An+1 = . 1 0 an an−1 7. (Cassini’s Identity) an−1 an+1 − a2n = (−1)n+1 for all n ≥ 1. [Use induction] 8. Fibonacci numbers can be defined for negative indices. Using an = an+2 − an+1 , we find a−1 = a1 − a0 = 0, a−2 = 1, a−3 = −1 etc. By induction, a−n = (−1)n an−2 for all n ≥ 2.
9. Cassini’s Identity is valid for all integers. 10. φ(x) =
1 (1−x)(1+x)
= 1 + x(1 + x) + x2 (1 + x)2 + . . . + xn−1 (1 + x)n−1 + xn (1 + x)n + . . ..
Comparing coefficient of xn on both sides, where where the right side is observed from the term xn (1 + x)n in reverse order, we get an = 1 + C(n − 1, 1) + C(n − 2, 2) + . . . . 11. We know f (4) = 5. Also f (5(k + 1) − 1) = f (5k + 4) = . . . = 5f (5k) + 3f (5k − 1). By induction, it follows that every 5th Fibonacci numbers are multiple of 5. 12. Assume that f (3k), f (3k + 1) are odd and f (3k + 2) is even. These are true for k = 0. Now f (3(k + 1)) =f (3k + 2) + f (3k + 1) f (3(k + 1) + 1) =f (3k + 1) + 2f (3k + 2) f (3(k + 1) + 2) =f (3k) + f (3k + 1) + 2f (3k + 3). By induction, f (n) is even iff n = 3k + 2 for some k ≥ 0. 13. For n ≥ 1, Consider the identity expansion of
1 1−x−x2
1 1−x−x2
= 1 + (x + x2 ) + (x + x2 )2 + . . .. The coefficient of xn in the
is known to be the Fibonacci number an .
Each summand of the series 1 + (x + x2 ) + (x + x2 )2 + . . . is of the form xa1 (x2 )b1 xa2 (x2 )b2 . . . xak (x2 )bk , where either ai = 0, bi = 1 or ai = 1, bi = 0 for i = 1, 2, . . . , k. If xn = xa1 (x2 )b1 xa2 (x2 )b2 . . . xak (x2 )bk , we get n = a1 + 2b1 + a2 + 2b2 + . . . + ak + 2bk . As ai , bi ∈ {0, 1}, n = a1 + 2b1 + a2 + 2b2 + . . . + ak + 2bk gives a way of adding 1’s and 2’s to get n. Thus each appearance of xn in the series 1 + (x + x2 ) + (x + x2 )2 + . . .
corresponds to a way of adding 1’s and 2’s to get n. Therefore the coefficient of xn in the
series 1 + (x + x2 ) + (x + x2 )2 + . . . is the total number of ways of adding 1’s and 2’s to get n. Hence an is the number of ways of adding 1’s and 2’s to get n. 14. (Zeckendorf’s Theorem) Every positive integer can be expressed as a sum of distinct non-consecutive Fibonacci numbers. [For n ∈ N, there exists m ∈ N such that f (m) ≤ n < f (m + 1). If f (m) = n, then we are done. Otherwise
0 < n − f (m) < f (m + 1) − f (m) = f (m − 1). Since n − f (m) > 0, there exists p ∈ N such that f (p) ≤ n − f (m) < f (p + 1). Now f (p) ≤ n − f (m) < f (m − 1) ⇒ p < m − 1. So, f (p) and f (m) are non-consecutive. Now if f (p) = n − f (m), then we are done. Otherwise, there exists q ≤ p − 2 such that f (q) ≤ n − f (m) − f (p) < f (q + 1). This process continues and ultimately we will reach the desired sum.] 15. The sum in the Zeckendorf’s Theorem is unique. [Suppose, the positive integer N is a sum of distinct non-consecutive Fibonacci numbers that is not produced by Zeckendorf’s Theorem. Let f (m) ≤ N < f (m + 1), that is,
N ≤ f (m+1)−1. Under Zeckendorf’s Theorem, each element of the set {1, 2, 3, . . . , f (m+ 1) − 1} is mapped one-to-one into a non-empty subset of J = {f (1), f (2), . . . , f (m)},
such that it contains no two consecutive Fibonacci numbers. Let, these type of sets be red sets. In addition, N corresponds to a red subset that is not already counted. So, J have at least f (m + 1) − 1 + 1 = f (m + 1) red sets. But according to Item 5 (Combinatorial Definition of f (n)), J have exactly f (m + 1) − 1 red sets, a contradiction.]
16. Zeckendorf’s Theorem lead to the Fibonacci number system. That is, any non-negative integer can be expressed as a sequence of 0’s and 1’s, writing n = (bm bm−1 . . . b2 b1 )F
⇐⇒ n =
m X
bk f (k).
k=1
17. Cassini’s Identity is the basis of a geometrical paradox. [See Figure ??.] Catalan Numbers: In a m × n rectangle, let the intersections be denoted by integer points. A lattice path from
a point A = (x, y) to B = (z, w), x ≤ z, y ≤ w is such that at each step we move either one unit right, denoted R, or one unit up, denoted U .
1. The number of lattice paths from (0, 0) to (m, n) is C(m + n, m). As at each step, the unit increase is either R or U , we need to take m many R steps and n many U steps to reach (m, n) from (0, 0). So, any arrangement of m many R’s and n many U ’s will give such a path uniquely. Hence, the answer is C(m + n, m) or C(m + n, n).
Cassini’s Identity: an−1 an+1 − a2n = (−1)n+1 B
a4 = 5,
C
a5 = 8,
a6 = 13
a4 .a6 − a25 = (−1)6 = 1 ⇒ 5 × 13 − 82 = 1
D A
A
B
D
C
Total Aera: 64 square unit
Total Aera: 65 square unit
Figure 1: A Geometrical Paradox Associated to Cassini’s Identity 2. Using lattice paths we can prove
m P
C(n + l, l) = C(n + m + 1, m).
l=0
Observe that C(n + m + 1, m) is the number of lattice paths from (0, 0) to (m, n + 1) and the left side is the number of lattice paths from (0, 0) to (l, n), where 0 ≤ l ≤ m. Fix l, 0 ≤ l ≤ m and let P be a lattice path from (0, 0) to (l, n). Then, the path P ∪ Q,
where Q = U RR . . . R with R appearing m − l times, gives a lattice path from (0, 0) to (m, n + 1), namely
P
U
Q0
(0, 0) → (l, n) → (l, n + 1) → (m, n + 1). These lattice paths for 0 ≤ l ≤ m are all distinct and hence the result follows. 3. (Definition) The number of lattice paths from (0, 0) to (n, n) so that at no step the number of U ’s exceeds the number of R’s, is called the Catalan number Cn . To show Cn =
C(2n,n) . n+1
Call an arrangement of n many U ’s and n many R’s a ‘bad path’ if the number of U ’s exceeds the number of R’s at least once. For example, the path RRU U U RRU is a bad path. To each such arrangement, we correspond another arrangement of n + 1 many U ’s and n − 1 many R’s in the following way: spot the first place where the number of U ’s exceeds that of R’s in the bad path. Then, from the next letter onwards change R
to U and U to R. For example, the bad path RRU U U RRU corresponds to the path RRU U U U U R. Notice that this is a one-one correspondence. Thus, the number of bad paths is C(2n, n − 1). So, the answer to the question is C(2n, n) − C(2n, n − 1) = 4. C0 = 1 and Cn+1 =
n P
k=0
C(2n,n) . n+1
Ck Cn−k for n ≥ 0. [In particular, C1 = 1, C2 = 2, C3 = 5.]
For each k = 0, 1, 2, . . . , n, let Xk = the set of lattice paths from (0, 0) to (k + 1, k + 1) in which all their internal points lie below y = x. The paths in Xk has a one-one correspondence between lattice paths from (1, 0) to (k + 1, k) that does not go above y = x. By shifting everything one unit back horizontally, we see a one-one correspondence between lattice paths from (0, 0) to (k, k) that does not go above y = x. Thus |Xk | = Ck .
Now, there are Cn−k ways of going from (k + 1, k + 1) to (n + 1, n + 1). Therefore, if Ak = the set of lattice paths from (0, 0) to (n + 1, n + 1) in which the first two points lying on y = x are (0, 0) and (k, k), then by product rule, |Ak | = Ck Cn−k . 5. A rooted binary tree is a tree with one root node, where each node has either zero or two branches descending from it. A node is internal if it has two nodes coming from it. The number rooted binary trees with n internal nodes is Cn . Let Rn be the number of rooted binary trees with n internal nodes. Then clearly, R0 = R1 = 1. Now for n ≥ 0, suppose there is a rooted binary tree with n + 1 internal nodes.
The root node is internal. There are k internal nodes on the left and n − k internal nodes on the right, for some k. Looking at the left and right side gives two rooted binary trees n P Rk Rn−k for n ≥ 0, which is with k and n − k internal nodes, respectively. So Rn+1 = k=0
the same recurrence relation as the Catalan numbers. So Cn = Rn for all n.
6. Consider a polygon with n + 2 vertices, where n ≥ 1. In how many ways can we divide the polygon into triangles using n − 1 non-crossing diagonals?
Let Tn be the number of such triangulations. As a convention, define T0 = 1 and think of a line segment as a polygon of two vertices having no interior. The number T0 is so the number of triangulation of a polygon of two vertices. Consider Tn+1 , which counts triangulations of an (n + 3)-gon. Number the vertices v1 , v2 , . . . , vn+3 . Every edge must belong to precisely one triangle in a particular triangulation. Fix an edge v1 v2 . Let the triangle that contains this edge be v1 v2 vk+3 , where k = 0, 1, . . . , n. Now this triangle splits the polygon into two remaining polygons that must be triangulated. If k = 0, then what is left is an (n + 2)-gon. Number of triangulations like this is T0 Tn . If k = 1, there is a triangle on one side and an (n + 1)-gon on the other side. The number of triangulations for this case is T1 Tn−1 . If k = n, then what is left is an (n + 2)-gon. Number of triangulations like this is Tn T0 . In general, there is a (k + 2)-gon on one side and an (n − k + 2)-gon on the other side.
The number of triangulations for this case is Tk Tn−k . Thus we have,
Tn+1 = T0 Tn + +T1 Tn−1 + . . . + Tn T0 . Also T0 = 1, T1 = 1. So Tn = Cn for all n. [Prob. 1.124 in Schaum’s Outline is an alternative solution.] 7. Cn is the number of different representations of the product A1 , . . . , An+1 of n + 1 square matrices of the same size using n pairs of brackets. By convention C0 = 1. Consider a representation X of the product of n + 1 matrices with n pairs of brackets. First we erase the subscripts, with the understanding that the i-th A from left is Ai . Claim: After the (n − k)-th ‘(’, there are at least k + 2 many A’s.
Proof of the claim: It is true for n = 1, that is when there are only two matrices. Assume it is true for n = 2, 3, . . . , p − 1. Consider a meaningful representation X of the product of p + 1 matrices with p pairs of brackets.
Observe that the last ‘(’ is followed by ‘AA)’, as the product is meaningful. Now, treat this ‘(AA)’ as a single matrix A. Then our original meaningful representation of the product of p+1 matrices changes into a meaningful representation X ∗ of p matrices with p − 1 pairs of brackets. Hence, by induction, in X ∗ , after the p − k = ((p − 1) − (k − 1))-th ‘(’, there are at least
k + 1 = (k − 1) + 2 many matrices. This means, in X, after the (p − k)-th ‘(’, there are at least k + 2 matrices. So the claim is justified.
Drop the right brackets and one A from the right end, to have a sequence of n many ‘(’s and n many A’s, where the number of A’s used till the (n − k)-th ‘(’ is at most
n − (k + 1) = n − k − 1. So, the number of A’s never exceeds the number of ‘(’.
Conversely, given such an arrangement, we can put back the )’s: first add one more A at the right end; find two consecutive letters from the last ‘(’; put a right bracket after them; treat (AA) as a letter; repeat the process. For example, ((A((AAA → ((A((AAAA → ((A((AA)AA → ((A((AA)A)A → ((A((AA)A))A = ((A((AA)A))A). By the description in Item 3, the number of such arrangements is
C(2n,n) . n+1
[Prob. 1.121 in Schaum’s Outline is an alternative solution.] 8. Cn is the number of sequences (u1 , u2 , . . . , u2n ) of n many +1’s and n many −1’s such that for each k = 1, . . . , 2n satisfies u1 + . . . + uk ≥ 0.
Let us call a sequence of n many +1’s and n many −1’s to be acceptable if it satisfies
the above condition, and unacceptable otherwise. We denote the number of acceptable sequences by An and the number of unacceptable sequences by Un . The total number of sequences of n many +1’s and n many −1’s is
(2n)! . n!n!
Consider an unacceptable sequence of n many +1’s and n many −1’s. So there is a
smallest k for which the partial sum u1 + . . . + uk is negative. By minimality of k, there must be an equal number of +1’s and −1’s preceding uk . So we must have k odd, and
k−1 many +1’s and k+1 many −1’s. 2 2 many +1’s and n − k+1 many n − k−1 2 2
uk = −1. So among the terms u1 , u2 , . . . , uk , there are
Among the remaining terms uk+1 , . . . , u2n , there are −1’s.
Now consider the effect of reversing the sign of each of the first k terms and leaving the rest unchanged. Now this new sequence obtained, say (a1 , a2 , . . . , a2n ), will have n + 1 copies of +1 and n − 1 copies of −1. This gives a function f from the set of unacceptable sequences to the set of sequences of n + 1 copies of +1 and n − 1 copies of −1. To see that is a bijection, construct its inverse:
let B = (b1 , b2 , . . . , b2n ) be a sequence of n + 1 copies of +1 and n − 1 copies of −1. Let
k be the first index for which there are more +1’s in b1 + . . . + bk than −1’s. Then the corresponding unacceptable sequence is (−b1 , −b2 , . . . , −bk , bk+1 , . . . , b2n ). Thus Un = the number of n + 1 many +1’s and n − 1 many −1’s An =
(2n)! . (n+1)!(n−1)!
Hence
(2n)! (2n)! 1 − = C(2n, n) = Cn . n!n! (n + 1)!(n − 1)! n+1
[Prob. 1.118 in Schaum’s Outline is an alternative solution.] √
9. The OGF of Cn is 1− 2x1−4x . ∞ P Cn xn . Then we have Let C(x) = n=0
xC(x)2 = ⇒xC(x)2 = ⇒C(x) = Note that lim C(x) = C0 = 1. As that C(x)
x→0 √ = 1− 2x1−4x
Note: (1 + z)1/2
" n ∞ X X
n=0 ∞ X
Ck Cn−k xn+1
k=0
Cn+1 xn+1 = C(x) − 1
n=0
1±
#
√
1 − 4x . 2x
√ 1+ 1−4x 2x
→ ∞ as x → 0 but lim C(x) = 1, we conclude x→0
is the right choice. ∞ P (−1)n−1 C(2n − 2, n − 1)z n for |z| < 1. =1+ n×22n−1 n=1
10. The EGF of Cn is ex (I0 (2x) − I1 (2x)), where In (x) is a modified Bessel function of the first kind. [Proof is beyond the scope of present discussion.]
Note: Current number of combinatorial interpretations of Cn : 207. Stirling Numbers of First Kind: The rising factorial [x]n is defined by [x]0 = 1 and [x]n = x(x + 1) . . . (x + n − 1) for n ≥ 1.
The falling factorial [x]n is defined by [x]0 = 1 and [x]n = x(x − 1) . . . (x − n + 1) for n ≥ 1.
The Stirling numbers of first kind s(n, k) is defined by n
[x] =
∞ X
s(n, k)xk , where s(n, k) = 0 for k > n
..........(1).
k=0
As a convention, we define s(0, 0) = 1. 1. s(n + 1, k) = s(n, k − 1) + ns(n, k). We have [x]n+1 = (x + n)[x]n . Therefore ∞ X k=0
k
s(n + 1, k)x = x
∞ X k=0
k
s(n, k)x + n
∞ X
k
s(n, k)x =
k=0
k=0
2. Replacing x by −x in (1), we have [x]n =
∞ P
∞ X
[s(n, k − 1) + ns(n, k)]xk .
(−1)n−k s(n, k)xk .
k=0
3. s(n, k) is the number of permutations of Jn that is a disjoint product of exactly k cycles. Let Pn,k = the set of permutations of Jn that is a disjoint product of exactly k cycles, and |Pn,k | = d(n, k). Clearly, d(n, n) = 1, d(n, 1) = (n − 1)!. Let f ∈ Pn+1,k . Then either (n + 1) is a cycle of length 1 in f or n + 1 is a part of one of the k cycles of f . Removing n + 1 in the first case give rise to an element in Pn,k−1 .
The second case is obtained by inserting n + 1 in n different places in an element of Pn,k . (Inserting n + 1 in the end of a k cycle is equivalent to inserting at the beginning.) Thus we get d(n, k − 1) + nd(n, k) choices for f . Therefore d(n + 1, k) = d(n, k − 1) + nd(n, k) and d(n, n) = 1, which is identical with s(n, k). Hence d(n, k) = s(n, k) for all n, k.
4. s(n + 1, k + 1) =
n P
[n]n−r s(r, k).
r=0
It is clearly true for n = 0. Assume that it is true for n − 1. Then n−1 X [n − 1]n−r−1 s(r, k) s(n + 1, k + 1) = s(n, k) + ns(n, k + 1) =s(n, k) + n r=0
=s(n, k) +
n−1 X
[n]n−r s(r, k)
r=0
=
n X
[n]n−r s(r, k).
r=0
5. Let f (n, m) be the number of ways of putting n distinct objects into m boxes, where the order of objects within a box is significant. (a) If empty boxes are allowed, then f (n, m) = [m]n . Consider a distribution of n − 1 such objects that counts f (n − 1, m). Such a
distribution brings i1 objects into box 1, i2 objects into box 2, . . . ,im objects into box m, so that i1 + . . . + im = n − 1, ik ≥ 0 (k = 1, . . . , m). In such a distribution, the n-th objects can go into box k in ik + 1 ways, for a total of (i1 + 1) + . . . + (im − 1) = n − 1 + m different ways. Therefore f (n, m) = (n − 1 + m)f (n − 1, m). Hence f (n, m) = [m]n . (b) If empty boxes are not allowed and n ≥ m, then f (n, m) = n!C(n − 1, m − 1). In this case, the first object in each box can be put in P (n, m) ways. The remaining n − m objects can be put, as in the previous case, in [m]n−m ways. So f (n, m) = P (n, m)[m]n−m = n!C(n − 1, m − 1).
6. For m, n ∈ N, the non-negative integral solutions of x1 + x2 + . . . + xm = n is is, C(n + m − 1, m − 1).
[m]n , n!
that
Each solution gives a distribution of n identical objects (1’s) into m boxes. Temporarily considering the objects as non-identical, there are [m]n ways of doing it. Therefore [m]n n!
required number is 7.
n P
k=0
= C(n + m − 1, m − 1).
ks(n, k) = s(n + 1, 2) for n ≥ 1.
It is clearly true for n = 1. Assume that
n−1 P k=0
n X
ks(n, k) =
k=0
n X k=0
=
n X k=0
=
n X k=1
ks(n − 1, k) = s(n, 2). Then
k [s(n − 1, k − 1) + (n − 1)s(n − 1, k)] ks(n − 1, k − 1) + (n − 1) s(n − 1, k − 1) +
n X k=1
n X k=0
ks(n − 1, k)
(k − 1)s(n − 1, k − 1) + (n − 1)
=(n − 1)! + s(n, 2) + (n − 1)s(n, 2)
n X k=0
ks(n − 1, k)
=s(n, 1) + ns(n, 2) = s(n + 1, 2). 8. s(n + 1, k + 1) =
n P
s(n, r)C(r, k).
r=0
For k > n both sides are zero. So, assume k ≤ n. To use induction, we see that if n = 0 then k = 0 and so both sides are equal to 1. n−1 P s(n − 1, r)C(r, k − 1). Then Assume that s(n, k) = r=0
n X
s(n, r)C(r, k)
r=0
= = =
n X
r=0 n X
r=0 n X r=0
=
n X r=0
[s(n − 1, r − 1) + (n − 1)s(n − 1, r)] C(r, k) s(n − 1, r − 1)C(r, k) + (n − 1)
n X r=0
s(n − 1, r)C(r, k)
s(n − 1, r − 1) [C(r − 1, k − 1) + C(r − 1, k)] + (n − 1)s(n, k + 1) s(n − 1, r − 1)C(r − 1, k − 1) +
n X r=0
s(n − 1, r − 1)C(r − 1, k) + (n − 1)s(n, k + 1)
=s(n, k) + s(n, k + 1) + (n − 1)s(n, k + 1) =s(n, k) + ns(n, k + 1) = s(n + 1, k + 1). 9. The EGF of {(−1)n−k s(n, k)}n≥0 is
(log(1+x))k . k!
We have (1 + x)m =
X n≥0
Also (1 + x)m = exp(m log(1 + x)) =
P
X [m]n
xn n! n≥0 X xn X (−1)n−k s(n, k)mk = n! n≥0 k≥0 X xn X = mk (−1)n−k s(n, k). n! n≥0 k≥0
C(m, n)xn =
k
(log(1 + x))k mk! .
k≥0
Therefore, we get by comparing that
P
n
(−1)n−k s(n, k) xn! =
n≥0
10. The EGF of {s(n, k)}n≥0 is
(−1)k [log(1−x)]k . k!
We have (1 − x)−m = exp [−m log(1 − x)] = (1 − x)−m =
∞ P
k=0
(−1)k [log(1−x)]k mk . k!
∞ X m(m + 1) · · · (m + n − 1)
n!
n=0
xn = = =
∞ X [m]n
n!
n=0 "∞ ∞ X X
n=0 k=0 "∞ ∞ X X k=0
Thus we have
∞ P
n=0
n
(log(1+x))k . k!
s(n, k) xn! =
Also
xn s(n, k)mk
#
xn n!
# xn s(n, k) mk . n! n=0
(−1)k [log(1−x)]k . k!
11. The OGF of {(−1)n−k s(n, k)}n≥0 is ????? R∞ P Perhaps (−1)n−k s(n, k)xn = k!1 (log(1 + tx))k e−t dt is useful. Explicit form is not n≥0
0
known (at least to me).
Stirling Numbers of Second Kind: Definition: S(n, r) := the number of partitions of Jn into r subsets, is called Stirling Numbers of Second Kind. By convention: S(0, 0) = 1, S(n, 0) = 0 if n > 0 and S(n, r) = 0 if n < r. 1. r!S(n, r) = number of onto functions from Jn to Jr . 2. r!S(n, r) =
r P
i=0
(−1)i C(r, i)(r − i)n .
3. The number of partitions of Jn into non-empty subsets is S(n, 1) + S(n, 2) . . . + S(n, n). 4. S(n + 1, r) = S(n, r − 1) + rS(n, r). Write an r-partition of Jn+1 and erase n + 1 from it. That is, if {n + 1} is an element of
an r-partition, then the number of such partitions become S(n, r − 1); else n + 1 appears in one of the element of an r-partition of Jn , which gives the number rS(n, r).
5. Let n, r ∈ N and ` = min{n, r}. Then, rn =
` P
C(r, k)k!S(n, k).
k=1
Let A be the set of all functions f : Jn → Jr . Clearly, |A| = nr . We can count |A| in a different way too. Consider f : Jn → Jr . Then f : Jn → Range(f ) is an onto function. Note that |Range(f )| = k for some 1 ≤ k ≤ `. We can choose a k-subset S of Jr in C(r, k)
ways, and for each such choice, we have k!S(n, k) onto functions f : Jn → S. Therefore ` P |A| = C(n, k)k!S(r, k). k=1
6. S(n, k) =
n P
r=0
C(n − 1, r)S(r, k − 1).
To count the number of partitions of Jn in k subsets. The size of the cell that contains n can be 1 up to n − k + 1. For r = 0, . . . , n − k, let us choose r elements from Jn \ {n} in
C(n − 1, r) ways. These r elements, along with n, is the cell of a partition that contains
n. Now partition the remaining n − 1 − r elements in to k − 1 subsets in S(n − 1 − r, k − 1) ways. So, total number of partitions of in to k subsets is n−k X r=0
C(n − 1, r)S(n − 1 − r, k − 1) = =
n−k X
C(n − 1, n − 1 − r)S(n − 1 − r, k − 1)
r=0 n−1 X
r=k−1
=
n X r=0
7. S(n + 1, k + 1) =
n P
C(n − 1, r)S(r, k − 1)
C(n − 1, r)S(r, k − 1).
(k + 1)n−r S(r, k) for non-negative integers n and k.
r=0
Use induction on n to prove it. We know that S(1, k + 1) = 1 or 0 according as k = 0 or k ≥ 1. Thus for n = 0, we have S(n + 1, k + 1) = S(1, k + 1) = S(1, 1) = 1 = S(0, 0) = 0 0 P P (k + 1)0−0 S(0, k) for k ≥ 1. (0 + 1)0−0 S(0, 0) for k = 0. Also, S(1, k + 1) = 0 = r=0
r=0
Thus the identity is true for n = 0. n−1 P (k + 1)n−r−1 S(r, k). Then we have Assume that S(n, k + 1) = r=0
n−1 X (k + 1)n−r−1 S(r, k) S(n + 1, k + 1) = S(n, k) + (k + 1)S(n, k + 1) = S(n, k) + (k + 1) r=0
= S(n, k) +
n−1 X
(k + 1)n−r S(r, k)
r=0
=
n X
(k + 1)n−r S(r, k).
r=0
Hence by induction S(n + 1, k + 1) = n P
k=1
(k + 1)n−r S(r, k) for all non-negative integers n
r=0
and k. 8. xn =
n P
S(n, k)[x]k .
As x[x]k = [x]k+1 + k[x]k , to use induction, we have n
x = x.x
n−1
=x
n−1 X k=1
n−1 X
=
k=1
n−1 X
=
k=1
n X
=
k=1
n X
=
k=1 n X
=
S(n − 1, k)[x]k
S(n − 1, k)[x]k+1 + S(n − 1, k)[x]k+1 +
n−1 X k=1
n X
S(n − 1, k)k[x]k S(n − 1, k)k[x]k , as S(n − 1, n) = 0
k=1 n X
S(n − 1, k − 1)[x]k +
k=1
S(n − 1, k)k[x]k , as S(n − 1, 0) = 0
[S(n − 1, k − 1) + kS(n − 1, k)] [x]k S(n, k)[x]k .
k=1
[Prob. 1.151 in Schaum’s Outline is an alternative solution.] 9.
∞ P
(−1)n−k s(n, k)S(k, m) = δnm , where δnm is the Kronecker delta.
k=0
We have [x]n =
∞ P
(−1)n−k s(n, k)xk and xk =
k=0
S(k, m)[x]m . Therefore
m=0
k=0 ∞ X (−1)n−k s(n, k) [x]n =
∞ P
∞ X
S(k, m)[x]m
m=0
!
=
∞ X
m=0
∞ X
!
(−1)n−k s(n, k)S(k, m) [x]m .
k=0
By linear independence of [x]m for m = 0, 1, . . . , n, we have the desired result. 10. The sequence (S(n, 1), S(n, 2), . . . , S(n, n)) = (S(n, k))nk=1 is unimodal (i.e., it peaks at some level and then it start decreasing). To use induction, for each m = 1, . . . , n, let (S(m, k))nk=1 be unimodal, that is, there is an integer km , which is non-decreasing in m, such that S(m, k) peaks at k = km . We know that S(n + 1, k) = S(n, k − 1) + kS(n, k) and S(n + 1, k − 1) = S(n, k − 2) + (k − 1)S(n, k − 1). Therefore S(n+1, k)−S(n+1, k−1) = [S(n, k−1)−S(n, k−2)]+k[S(n, k)−S(n, k−1)]+S(n, k−1). By induction hypothesis, the RHS is positive for all k ≤ kn . Therefore S(n + 1, 1) < S(n + 1, 2) < . . . < S(n + 1, kn )
...
(1).
For k ≥ kn + 2, we have S(n + 1, k) − S(n + 1, k − 1) =
n X r=0
C(n, r)[S(r, k − 1) − S(r, k − 2)] < 0.
Therefore S(n + 1, kn + 1) > S(n + 1, kn + 2) > . . . > S(n + 1, n + 1)
...
(1).
n+1 Together (1) and (2) establish that (S(n + 1, k))k=1 is unimodal, with either kn+1 = kn
or kn+1 = kn + 1. 11. The OGF of {S(n, k)}n≥0 is
xk . (1−x)(1−2x)...(1−kx)
We have for k ≥ 1 fk (x) =
∞ X
n
S(n, k)x =
n=0
∞ X n=1
∞ X S(n, k)x = [kS(n − 1, k) + S(n − 1, k − 1)]xn n
n=1
=kx
∞ X n=1
S(n − 1, k)x
n−1
+x
=kxfk (x) + xfk−1 (x)
Therefore fk (x) =
x f (x). 1−kx k−1
12. The EGF of {S(n, k)}n≥0 is
Using f0 (x) = 1, we get fk (x) =
1 (ex k!
∞ X n=1
S(n − 1, k − 1)]xn−1
xk . (1−x)(1−2x)...(1−kx)
− 1)k .
We know that k!S(n, k) =the number of onto functions from Jn onto Jk =the number of n-sequences of Jk in each of which every element of Jk appears at least once =an (say). The EGF of an is clearly x +
x2 2!
+
x3 3!
+ ...
k
= (ex − 1)k .
===================================================
