Department of Mathematical Sciences
Binghamton University

A1. Evaluate binomial(n,k), simplifying as far as possible, for k = −1, 0, 1, 2, and 3, and for
1. n = x³.
2. n = 1/2.
3. n = −1.
4. n = π (optional).
Do you see any general patterns?

A2. Write from memory a combinatorial proof of Pascal's Formula, Theorem 4.3.

HOMEWORK IIIa (9/21)

Hand in Mon. 9/24:

# A1.

HOMEWORK IV (9/23)

Read for Mon. 9/24: Sects. 4.1-2 (if you didn't already) and Ch. 4, Exercise 19.

Do for discussion on Mon. 9/24:

Ch. 4, ## 3, 6, 10, 14, 17, 40.

## B1, B2.

Hand in Fri. 9/28:

Ch. 4, ## 30, 34, 42.

## B3, B4, B5.

Problem Set B

Northeast lattice paths are defined in Ch. 4, #19.

B1. (= Ch. 4, #32.) How many northeast lattice paths are there from (0,0) to (m,n)? Assume m, n ≥ 0.
Hint: Can you find an efficient way to describe such a path?
Hint: What results do you get with small numbers, such as m = 0, m = 1, m = 2?

B2. How many northeast lattice paths from (0, 0) to (9, 6) do go through the point (3, 4)?

B3. How many northeast lattice paths from (0, 0) to (9, 6) don't go through the point (3, 4)?

B4. Assume 0 ≤ a ≤ m, 0 ≤ b ≤ n. How many northeast lattice paths from (0, 0) to (m, n) do go through the point (a, b)?

B5. Assume 0 ≤ a ≤ m, 0 ≤ b ≤ n. How many northeast lattice paths from (0, 0) to (m, n) don't go through the point (a, b)?

HOMEWORK V (9/29)

Read for Mon., 9/26: Sects. 4.3, 5.1, 5.2.
Do not forget to check the announcements; they have valuable information.

Do for discussion on Tues., 10/2:

Ch. 4, ## 25, 41, 45.

Ch. 5, ## 1, 2, 5, 17, 18, 22, 26.

# C1.

Do for discussion on Wed., 10/3:

Ch. 4, # 54 (and note the mistake) [N.B. This problem has two major errors; see ##D1, D2.].

Ch. 5, ## 23, 28.

# C3.

Hand in Fri., 10/5:

Ch. 4, ## 35, 44, 47.

Ch. 5, ## 20, 27, 35.

## C2, C4.

Problem Set C

C1. Evaluate binomial(n,k) for all integers k, and for
1. n = −1.
2. n = −2.
(As always, simplify formulas as far as possible.)

C2. Use the binomial series and the results of #C1 to get series formulas for
1. (1 − x)⁻¹.
2. (1 − x)⁻².

C3. Find a formula for S(n,n).

C4. How many compositions of 10 (into any number of parts) are there using parts in {1, 3, 5, 6, 7}?

HOMEWORK VI (10/5, 7)

Read for Mon., 10/8: Sect. 5.3.

Do for discussion on Tues., 10/9:

Ch. 4, ## 38, 50.

Ch. 5, ## 4, 7, 10, 19, 35.

# D3.

Do for discussion on Wed., 10/10:

Ch. 4, ## 39, 56.

Ch. 5, ## 8, 12, 15.

# D1.

Hand in Fri., 10/12:

Ch. 4, ## 39(repeat), 46, ~~56(repeat)~~, 57.

Ch. 5, ## 21, 28, 32, 36.

## D2, D4 (replacing 4-56).

Problem Set D

D1. Exercise 54 of Ch. 4 has a mistake (see the announcements page). Solve the corrected problem.

D2. What is the largest number of subsets of [n] such that for any two of the subsets, one contains the other?

D3. Fix the mistake in Exercise 16 of Ch. 5. You may use the solution in the book to help you figure out how the question should have been stated.

D4. Solve Ch. 4, #56, for the special cases where n−k = 0 and 1.

TEST I will be on Tuesday, Oct. 16, and will cover everything up to the test (HW I–VI).

HOMEWORK VII (10/16)

Read for:

Wed., 10/17: Ch. 6 to the end of Sect. 6.1. Also see the announcements page's notes on permutations.

Fri., 10/19: Ch. 6, all.

Do for discussion on Tues., 10/23:

Ch. 6, ## 1-3, 5, 7, 9, 13-14, 26.

Remember to always check the announcements page for typos.

Do for discussion on Wed., 10/24:

Ch. 6, ## 10, 11-12, 17, 27, 47.

## E1(a,b), E2(a,b), E3(a,b).

Hand in Fri., 10/26:

Ch. 6, ## 28, 30, ~~32, 33~~.

## E1(c), E2(c), E3(c).

Problem Set E

E1. Recall the function g: S
→ Perm(n) from Sect. 6.1. For each of the following permutations, find g(p) in one-line and cycle form.
1. p = 3174625
2. p = (256)(4)(13)
3. p = 361524 (corrected later; sorry!)

E2. Recall the function h: Perm(n) → S_n (the inverse of g) from Sect. 6.1. For each permutation in #E1, find h(p) in one-line and cycle form.

E3. Calculate the following entries of the product matrices sS and Ss. (The matrices s, S are the Stirling number matrices from Sect. 6.1. Remember that the row and column numbers begin with 0, not 1.)
1. The (2,4) entry.
2. The (4,2) entry.
3. The (3,5) entry.

HOMEWORK VIII (10/26, 28, 30)

Reread Ch. 6. Pay special attention to the bijections in the combinatorial proofs.

Do for discussion on ~~Tues., 10/30~~ Wed., 10/31:

Ch. 6, ## 15-16, 32, 47.

## F1(a,b,e), F2, F4, F6(a,b), F7(a,c).

Do for discussion on ~~Wed., 11/1~~ Fri., 11/2:

Ch. 6, ## 18, 35-36, 39, 48.

## F4, F7(b,d).

Hand in ~~Fri., 11/3~~ Mon., 11/5:

Ch. 6, ## 33, 38.

## F1(c,d), F3, F5, F6(c,d), F8.

Your work for Ch. 6, ## 15-16, 18, 35, 39, 47. (These solutions will not be graded; the fact that you did the work will be recorded.) Please hand in the work papers separately from the hand-in problems.

Problem Set F

F1. Find the permutation matrix for:
1. The identity permutation of [6], sometimes written 1, also written 123456 and (1)(2)(3)(4)(5)(6).

F2. Using the matrices in #F1:
1. Find the product pq, then find the permutation matrix A_pq.
2. Find the matrix product A_pA_q.
3. Compare the two matrices from (i) and (ii).

F3. The same as #F2, but for the permutations q and r.

F4. Let s = p⁻¹ (p is from #F1).
1. Find the matrix A_s without finding s.
2. Now find the permutation s.
3. Now find the matrix A_s from (ii), without using (i).
4. Finally (of course), compare the results. Are you surprised?

F5. The same as #F4, but for the permutation r from #F1(c).

F6. Find the parity of each permutation in #F1. Also find the number of inversions.

In problems F7–F8, Φ: ODD(2m) → EVEN(2m) is the bijection of Lemma 6.20 (page 122). In class I defined Θ = Φ⁻¹: EVEN(2m) → ODD(2m) as the inverse bijection, which Bona calls the rule for "recovering π" from Φ(π) = σ in EVEN(2m) (upper middle of page 122).

F7. For each permutation p, calculate Φ(p) if p is in ODD(2m), or Θ(p) if p is in EVEN(2m). Also, state the value of m. (The symbol "A" stands for the number 10, to avoid confusion in writing permutations.)
1. p = (136)(25974)(8)(A) (corrected)
2. p = 356291487A
3. p = (43)(2689)(A1)(57)
4. p = (43)(2689)(A157)

F8. For each permutation p, calculate Φ(p) if p is in ODD(2m), or Θ(p) if p is in EVEN(2m), or neither if p is not in either one. Also, state the value of m, if p is in one of those two sets.
1. p = (1)(5293)(4)(678)
2. p = (12)(5934)(68)(7A)
3. p = 8694253A71
4. p = (125934)(68)(7A)

HOMEWORK IX (11/4, 5)

Read Ch. 7 (all except Theorem 7.6).

Do for discussion on Tues., 11/6:

Ch. 7, ## 1-4, 17, 24.

Do for discussion on Wed., 11/7:

Ch. 7, ## 23, 26, 28, and G1.

Hand in Fri., 11/9:

Ch. 7, ## 16, 20, 21, 22, 27, and G2.

Your work for Ch. 7, all discussion problems. (These solutions will not be graded; the fact that you did the work will be recorded.) Please hand in the work papers separately from the hand-in problems.

Problem Set G

G1. Find the number of permutations of [8] in which:
1. No integer is in its natural position.
2. No odd integer is in its natural position.
3. Exactly one integer is in its natural position.
4. At most one integer is in its natural position.

G2. Find the number of permutations of [n] in which:
1. Exactly k integers are in their natural positions.
2. There are exactly k fixed points.

HOMEWORK X (11/11, 15)

Read Sects. 4.3, 8.1.1, 8.1.2.

Do for discussion on Tues., 11/13:

Ch. 4, # 26.

Ch. 8, ## 1, 4, 7, 8, 10, 12.

## H4, H5(a-c).

Do for discussion on Wed., 11/14:

Ch. 8, ## 2, 9, 13. (Change: 16, 22 moved to Friday discussion.)

## H1, H2.

Do for discussion on Fri., 11/16:

Ch. 8, ## 16, 22. (Change: Moved from Wednesday.)

Hand in Fri., 11/16:

Ch. 7, ## 34, 36.

Ch. 8, ## 24, 25, 34, 35.

## H3, H5(d).

Your work for all discussion problems of this week. (These solutions will not be graded; the fact that you did the work will be recorded.) Please hand in the work papers separately from the hand-in problems.

Problem Set H

H1. Find the inverse of the permutation.
1. p = (12345).
2. p = (54321).
3. p = (1,2,3,...,n).
4. p = (n,n-1,...,2,1).
5. p = (13542).
6. p = (14)(326)(5).
How does this help you with Exercise 6.14?

H2. Compare the permutation matrices of the permutation and its inverse, for H1(a,b).

H3. Deduce from Theorem 4.15 the following formula, for all positive integers r :
(1-x)^−r = Sum_n=0^∞ binom(r+n−1, r−1) xⁿ.
This is an important formula; we use it frequently.

H4. Find the power series for the expression 3x/(1-2x)⁴ - (1-4x)^-3:

H5. Find a simple formula for the sequence of which the function is the ordinary generating function.
1. A(x) = 1/(1-3x)³.
2. B(x) = (2-x)⁻³.
3. C(x) = 1/(1+3x)(1-4x).
4. D(x) = (1+5x)⁻¹⁰.

HOMEWORK XI (11/11, 15)

Read Sect. 8.1 (all).

Do for discussion on Mon., 11/19:

Ch. 8, ## 3, 5, 23, 26, 34-36.

# I1.

Problem Set I

I1. Find closed expressions (no summations) for the following power series.
1. ∑_n≥0 3n(n−1) xⁿ.
2. ∑_n≥0 (n+5) xⁿ⁺².

TEST II will be on Tuesday, Nov. 20, and will cover Homework Sets VII–XI.

HOMEWORK XII (11/22)

Read Sect. 8.2. Reread Sect. 8.1.2.1 (Catalan numbers) and the supplementary remark about the binomial series for negative integral powers.

Do for discussion on Tues., 11/27:

Ch. 8, ## 15, 19 (see correction), 20, 27.

Do for discussion on Wed., 11/28:

Ch. 7, # 9.

Ch. 8, ## 3, 6, 14, 21, 29, 32.

Hand in Fri., 11/30:

Ch. 7, # 29.

Ch. 8, ## 28, 30, 33, 37, 40.

# J1.

Problem Set J

J1. How many ways are there to carry out multiplication of an expression a₁a₂...a_n, if you can't change the order of the variables? Remember that multiplication is only defined for two quantities at once, so you have to multiply the n quantities by multiplying two at a time. For instance, there are two ways to multiply three quantities a₁a₂a₃:
(a₁a₂)a₃ and
a₁(a₂a₃).
There are more ways to multiply four quantities:
((a₁a₂)a₃)a₄,
(a₁(a₂a₃))a₄,
(a₁a₂)(a₃a₄),
a₁((a₂a₃)a₄),
and more. We call these "the ways to parenthesize n quantities" because the order in which you do the multiplication is shown by how you put in the parentheses.
The problem is to find a formula for M_n, the number of ways to multiply n quantities. To find the answer, first find a formula for the generating function M(x) of the sequence (M₀, M₁, M₂, ..., M_n, ...). Then compare it to generating function formulas you've seen.
Tip: You should let M₀ = 0 and M₁ = 1.

HOMEWORK XIII (12/2)

Read Sects. 17.1–3. (See corrections.)

Do for discussion on Tues., 12/4:

Ch. 17, ## 1, 6, 7, 18, 26.

Do for discussion on Wed., 12/5:

Ch. 17, ## 2, 3, 5, 8, 16.

Hand in Fri., 12/7:

Ch. 17, ## 24, 29, 38.

# K1, K2.

Problem Set K

K1. Prove that M_n of Problem # J1 equals the Catalan number c_n−1 by finding a bijection between the set of all ways to parenthesize n quantities and the set of all "good sequences" (Sect. 8.1.2.1) of length n − 1.

K2. Consider a (v, k, λ)-design D = (S, B). (As it's a BIBD, the definition implies v > k and λ > 0.)
1. Suppose it has r = λ. What can the design be, if anything? (This will justify the assumption that r − λ > 0 in the proof of Fisher's inequality.)
2. Suppose it has k = λ. What can that design be, if anything?
3. Is it possible to have k < λ? How about r < λ?

HOMEWORK XIV (12/10)

Read Sects. 17.4–5 and the write-up on affine and projective planes and Latin squares.

Do for discussion on Tues., 12/11:

Ch. 17, ## 11, 13, 20, 35.

Do for discussion on Wed., 12/12:

Ch. 17, ## 14.

Hand in Wed., 12/12:

Ch. 17, ## 21, 36.

Go to rules and advice for homework | announcements | course information | syllabus.

Go to the Math Department main page.

Department of Mathematical Sciences Binghamton University

Math 386: Combinatorics Homework Assignments

Fall 2012

HOMEWORK I (9/4)

HOMEWORK II (9/10)

HOMEWORK III (9/10, 13)

Problem Set A