1.5 There are 2⁹⁹ binary strings of length 99. Half of these, 2⁹⁸, have an odd number of 1′s. The reason is that, regardless of the first 98 bits, the last bit may be chosen to make the total number of 1′s even or odd.

1.7 There are nⁿ such functions.

1.17 There are 2ⁿ² different binary relations on an n-set.

1.20 Since the tenth row of Pascal’s triangle is 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, we have (a + b)¹⁰ = a¹⁰ + 10a⁹b + 45a⁸b² + 120a⁷b³+210a⁶b⁴ + 252a⁵b⁵ + 210a⁴b⁶ + 120a³b⁷ + 45a²b⁸ + 10ab⁹ + b¹⁰.

1.21 By the binomial theorem, the coefficient is = 184,756.

1.25 By the multinomial theorem, (a + b + c)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴ + 4a³c 12a²bc + 12ab²c + 4b³c + 6a²c² + 12abc² + 6b²c² + 4ac³ + 4bc³ + c⁴.

1.26 By the multinomial theorem, the coefficient is = 22,170,720.

1.27 By simplifying, we see that

1.30 (a) The number of paths is = 3,268,760.

(b) The number of paths is = 10,361,546,974,682,663,760.

1.32 The identity to prove is equivalent to

1.45 Clearly, S₀(n) = n. The formula for S₁ (n) can be obtained by noting that 2S₁(n) = (n + 1)n and hence S₁ (n) = n(n + 1)/2. To find S₂(n) and S₃(n), we use the following technique. The sum Σⁿ_i=1[(i + 1)^k+1 – i^k+1] is a telescoping series. Hence

1.46 A k-dimensional face of an n-dimensional hypercube is a subset of the 2ⁿ vertices of the cube isomorphic to a k-dimensional hypercube. There are choices for the coordinates on which to base the face. The other coordinates can be 0 or 1.

1.47 The total number of pizzas is

1.49 (a) The number of such functions is .

(b) The number of such functions is .

1.50 We have = 1, = = 15, = 25, = 10, = 1, and B(5) = 52.

1.52 The formula = 2ⁿ⁻¹ – 1 holds since any subset of {1, 2, 3,…,n – 1}, except the set itself, together with n, constitutes a part in a partition of {1, 2, 3,…,n} into two subsets. The formula = for n ≥ 2 holds since in a partition of {1, 2, 3,…,n} into n – 1 parts, the element n is in any one of n – 1 parts and there are choices for which part it is in.

1.53 There are 10³⁰/4 + 1 choices for z, namely, all the integers from 0 to 10³⁰/4. Among these choices, the average value of 4z is 10³⁰/2. Hence, on average, x+2y = 10³⁰/2. There are 10³⁰/4 + 1 values of y that satisfy this equation, namely, the integers from 0 to 10³⁰/2. Once z and y are chosen, the value of x is determined. Therefore, the total number of nonnegative integer solutions is

1.56 (a) Let S be the set of functions from {1, 2, 3,…,m} to {1, 2, 3,…,n}. Then S has cardinality n^m. We wish to find the cardinality of the subset of S consisting of all onto functions. For 1 ≤ i ≤ n, let A_i be the collection of functions whose range does not contain i. Then the intersection of j of the A_i has cardinality (n – j)^m, the number of unrestricted functions from {1, 2, 3,…,m} to the n – j nonexcluded elements of {1, 2, 3,…,n}. Applying the inclusion–exclusion principle, we obtain

(b) From (a), we obtain

1.60 We take successive differences:

1.61 We can think of a pair of linked sets (A, B) as an onto function from S to the set {A, B, A ∩ B} or to the set . So the total number of pairs of linked sets is T(n, 3) + T(n, 4).

1.65 The Fibonacci numbers are sums of “shallow triangles” of Pascal’s triangle:

1.68 The number 210 occurs six times in Pascal’s triangle:

1.74 A particular solution to the recurrence relation is a_n = -n –3. Hence, the general solution is of the form

1.86 We have , as this counts the ways of choosing two elements to be in the same cycle.

1.88 In a partition of n + 1 elements, the (n + 1)st element is together with n – k other elements for some k with 0 ≤ k ≤ n. There are choices for these n – k elements. Hence

1.89 From the recurrence relation for Stirling numbers of the second kind,

1.90 Upon the substitutions k → –n + 1 and n → –k + 1, the recurrence relation (1.32) becomes the recurrence relation (1.33).

1.91 The relation follows by subtracting 1 from each part in the partition of n into k parts.

1.107 Obviously, F_m|F_m. Applying the identity

1.108 Since gcd(a, b) | a, it follows from the previous exercise that F_gcd(a,b) | F_a. Likewise, F_gcd(a,b) | F_b. Hence F_gcd(a,b) | gcd(F_a, F_b).

2.1 The sum is

2.4 The generating function is x(x((1 – x)⁻¹)’)’ = x(x + 1)(1 – x)⁻³.

2.12 A recurrence formula is a₀ = 1, a₁ = –3, and a_n = –3a_n−1 – a_n–2 for n ≥ 2. Notice that a_n = (–1)ⁿF_2n+2.

2.14 The identity follows upon summing f(x), with x replaced by ω^j_x and weighted by ω^−jp for 0 ≤ j ≤ q – 1, using the relation 1 + ω + ω² + · · · + ω^{q – 1} = 0.

2.17 We can find a simple formula for t(n) where n has any given remainder upon division by 12. Thus

2.19 First, we prove that the period of {t(n) mod m} is at most 12m. If n is even, we may write n = 12m + 2r and we have

2.21 We will prove the result by induction on n. The claim is true for n = 0 since C₀ = 1 and 0 = 2¹ – 1. Assume that the claim holds for all Catalan numbers up to C_n. Now consider C_n+1. If n + 1 is even, then

2.22 From the recurrence relation C_n = C_n–1, we have

2.27 Clearly, the formula holds for n = 0 and n = 1. Assume that it holds for n. Then

2.31 There are 48,639 such walks. It is easy to generate an 8 × 8 table by starting with 1 at a1 and at each cell adding the left, lower, and lower-left neighbors. This produces the Delannoy numbers. The main diagonal Delannoy numbers are 1, 3, 13, 63, 321, 1683, 8989, 48639.

2.32 A recurrence relation is

2.43 For x X, let N_x (neighborhood) be the intersection of all sets in S that contain x. Since S is closed under unions and complements, it is closed under intersections. Hence N_x S. The sets N_x partition X. Therefore, the number of algebras is equal to the number of partitions of X. (a) If X is labeled, then the number is B(n). (b) If X is unlabeled, then the number is p(n).

2.44 The number of functions is nⁿ. Given any element x {1,…,n}, there are (n–1)ⁿ functions that do not include x in their range. Altogether, there are n(n–1)ⁿ of these elements x (with multiplicity). Hence

2.52 There are 3210 such necklaces.

2.56 From the generating function in Example 2.22, we see that there are 16 circular necklaces with five white beads and five black beads.

2.63 There are 34 nonisomorphic graphs of order 5.

2.69 (a) We will show that the coefficients of · · · in both expressions are equal. Let k = 1α₁ + · · · + mα_m and α_m+1 = · · · = α_k = 0. In the expression on the left, the contribution to · · · comes from the n = k term, which is

2.70 There are two such graphs of order 5 and none of order 6. A self-complementary graph of order n > 1 has n(n – 1)/4 edges. For this to be an integer, n must be of the form 4k or k + 1.

2.74 It is approximately 1.3 × 10¹³³².

3.1 By the pigeonhole principle, there exist m and n, with m < n, such that 17^m 17ⁿ (mod 10⁴). Since gcd(17, 10⁴) = 1, we have 17^n–m 1 (mod 10⁴).

3.3 To show that this result is the best possible, let S = {1,…,100} and take A₁ to be any subset of S with 67 elements. Let the other A_i be cyclic shifts of A₁. In this system of sets, each x S is contained in exactly 67 of the A_i.

3.23 Let G₁ consist of three disjoint copies of K₄ and G₂ be G with one edge added.

3.24 If α(G) and χ(G) were both finite, then the number of vertices in G would be bounded by their product (a finite number). Since the number of vertices is infinite, at least one of α(G) and χ(G) is infinite.

3.25 Given any two vertices x and y of G, the degree conditions imply that x and y have a common neighbor z, and hence there is a path from x to y. Therefore G is connected.

3.26 Suppose that the longest path contained in G had fewer than n vertices. Then, choosing any two consecutive vertices in the path, say, x and y, the degree condition implies that x and y have a common neighbor z. Using z, we can make a longer path. Hence, the longest path in G has n vertices. The same type of argument allows us to close the path to make a cycle of length n.

3.27 The result follows by mathematical induction. Removing an end vertex and its incident edge from the graph amounts to subtracting 1 from both sides of the relation p = q+1. Continue this process until the graph contains only one vertex; the relation certainly holds for this graph.

3.33 Take n disjoint copies of a total order on m elements.

4.2 We can take f(n) = R(n, n). Number the vertices 1, 2,…,f(n), and color the edge {i, j}, where i < j, green if i is directed to j, and red otherwise. Ramsey’s theorem guarantees a monochromatic subgraph K_n. The corresponding directed subgraph is a transitive subtournament.

4.10 Take G = K_{∞, ∞ ∞}. Call the parts of the tripartite graph A, B, and C. Color all edges between A and B green and all other edges red.

4.11 Let the graph be the cycle C₈ together with all four diagonals.

4.13 Given a 3-coloring of K₁₇, let v be any vertex. There are 16 edges incident with v. By the pigeonhole principle, at least six of these edges are the same color, say, green. Suppose that v is incident to vertices x₁, x₂, x₃, x₄, x₅, x₆ by green edges. If any edge {x_i, x_j} is green, then we have a green K₃. If not, then we have a red K₃ or a blue K₃ (since R(3, 3) = 6). To finish the argument, show a 3-coloring of K₁₆ with no monochromatic triangle.

4.15 From the probabilistic method, we obtain the lower bound 3.0038 × 10¹⁶.

4.23 False. Take one part to be the union of {1}, {3, 4}, {7, 8, 9}, {13, 14, 15, 16}, etc.

4.26 An example of a 6-AP of primes is 7, 37, 67, 97, 127, 157.

5.1 The contribution from each component to both sides of the identity is 0 if x_i = y_i and 1 if x_i ≠ y_i.

5.4 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111 The code detects one error.

5.6 Such a code would require that

5.11 The probability that the Hamming code corrects one error is

5.12 Append an eighth component to the Hamming code such that the entry makes the total number of 1′s even. This ensures that the distance of the code is 4.

5.25 The group is GL(3, 2).

6.2 A projective place of order 4 is a 2-(21, 5, 1) design.

6.7 Let the first row of the matrix be [1 1 0 1 0 0 0] and take cyclic shifts.

6.11 If |C_i| = λ for some i, then every other C_j contains C_i, so m ≤ n + 1 – λ ≤ n.

6.20 The result follows from the observation that, for any given α and β modulo n, there exist unique (mod n) i and j such that i + j α and i – j β. For 2i α + β and 2j α – β, this determines unique i and j since n is odd.

6.33 Each lattice point has all n integer coordinates. Its lattice neighbors are those points with the same coordinates save for one change to an integer one greater or one lesser. Hence, each lattice point has 2n neighbors.