Math 386: Combinatorics: Additional Problems

Fall 2024
Tom Zaslavsky

To the main class page | the schedule page | the announcements page | my home page.

Additional problems will be labeled A1, A2, etc., in the assignments.

  1. For each n ≥ 0, prove that the binomial coefficients C(n,k) are increasing and then decreasing for 0 ≤ k ≤ n, i.e.,
            C(n, 0) < C(n, 1) < ··· < C(n, floor(n/2))
            = C(n, ceil(n/2)) > C(n, ceil(n/2)−1) > ··· > C(n, n−1) > C(n, n).
    Deduce that the largest binomial coefficient is C(n, n/2) if n is even and the largest ones are C(n, floor(n/2)) and C(n, ceil(n/2)) if n is odd.
  2. Here are two permutations of [7]: π = (3,1,5,4,7,2,6) and τ = (134)(627)(5). Calculate their two products: π τ and τ π. In decreasing strictness of requirement, I ask: Are they equal? Do they have the same list of cycle lengths? Do they have the same number of cycles?
  3. What is the order (see Ch. 3, # 9) of each permutation π, τ, π τ, and τ π?
  4. What is the inverse of each permutation π, τ in the previous problems? Give the 1-line form for π−1 and the cycle form for τ −1.
  5. Evaluate these binomial coefficients. Assume k is a non-negative integer.
    1. C(0, k)
    2. C(−1, k)
    3. C(−2, k)
  6. Suppose we have a set of m "letters" (i.e., symbols) from which we want to make a "word" (string of letters) of length n. Here we let a word freely repeat letters. How many such words are there, for n = 1, 2, 3, 4? Do you see a pattern? Can you prove it for all n ≥ 0?
  7. In Ch. 3 # 5, find the representation for N = 5, 6, 7. (In case it wasn't clear: you have to figure out the value of k for each N.) (See the correction to the hint.)
  8. N little vases all in a row, and more ...
    1. How many ways are there to arrange m red vases, n blue vases, and p yellow vases in a row?
    2. If you have m vases of each of k colors, how many ways are there to arrange them in a row?
    3. How many ways can you put a deck of cards in order if you must have each suit all together?
  9. How many distinct (positive) divisors are there of the number
    1. 2952111?
    2. 294263?
    3. any positive integer n? (It might be a bit more complicated than a simple formula.)
  10. You have n plates, all different. How many ways are there to set n places at a round table with one plate at each place? Combinatorics thinks the table can be rotated, so no place is distinguished by its location. (I have a table like that.)
    1. n = 3.
    2. Any n > 1.
  11. How many ways are there to seat 5 men and 5 women at a round table if no two men, and no two women, can sit next to each other?
  12. How many sets of k integers from 1 to 22 are there, if no two consecutive integers are allowed?
    1. k = 2, 3.
    2. Any k.
  13. Use the recurrences in Proposition (5.3.2) to compute all the Stirling numbers S(n, k) and s(n, k) for 0 ≤ k ≤ n ≤ 5. (You can use the numbers in some later problems.)
  14. Use Stirling numbers to find the numbers of (a) permutations with 4 cycles and (b) partitions with 4 parts, of the set {1, 2, ..., n}.
  15. Use Stirling numbers to express the falling factorial (x)5 as a polynomial in the usual way (in terms of powers of x).
  16. Use Stirling numbers to express x5 in terms of falling factorials (i.e., as a sum of falling factorials with numerical coefficients).
  17. A city with Manhattan-style streets is like the set of integer points in the graph of R2 where to get from point (0,0) to point (x,y) you can only take a horizontal step from (i,j) to (i+1,j) (or backwards) or a vertical step from (i,j) to (i+1,j) (or backwards). (The same rule applies for any starting point, not only (0,0).) For this question, assume x, y ≥ 0.
    1. What is the smallest number of steps to get from (0,0) to (x,y)?
    2. How many different shortest routes are there from (0,0) to (x,y)?
    3. What are all the possible lengths of routes from (0,0) to (x,y)?
    4. (Hard; optional) How many shortest routes are there that never cross the line x = y?
  18. A problem about the proof of the Marriage Theorem (in Cameron) with sets
      A1 = {1,2,3},   A2 = {1,2},   A3 = {2,4},   A4 = {2,3}.
    1. Is {1,2,3,4} critical?
    2. Find a nonempty proper subset J of {1,2,3,4} that is critical.
    3. Find an SDR X of the sets Aj for j ∈ J.
    4. Find the sets Ai* for i ∉ J.
    5. Find an SDR Y of the sets Ai* for i ∉ J.
    6. Use X and Y to find an SDR of all four sets A1, ..., A4.
  19. (Hint: Use linear algebra, but remember you are not working in the real numbers.)
    1. Arithmetic — Solve the following linear systems.
      1. y = 3x+2 and y = 2x−1, using arithmetic in the field GF(5).
      2. y = ωx and y = x + 1, using arithmetic in the field GF(4) = {0, 1, ω, ω+1} with ω2 + ω + 1 = 0.
      3. x + ωy − 1 = 0 and ωx - y = ω, using arithmetic in GF(4).
    2. Geometry — Find the point of intersection of the affine lines.
      1. y = 3x+2 and y = 2x−1 in the affine plane with coordinates in GF(5).
      2. y = ωx and y = x + 1 in the affine plane with coordinates in GF(4).
      3. x + ωy − 1 = 0 and ωx - y = ω in the affine plane with coordinates in GF(4).
    3. More geometry — Find the slope and x- and y-intercepts of the affine line. What is the infinite point on that line in the corresponding projective plane?
      1. y = 3x+2 in the affine plane with coordinates in GF(5).
      2. y = ωx in the affine plane with coordinates in GF(4).
      3. ωx - y = ω in the affine plane with coordinates in GF(4).
  20. Prove that there is a unique projective plane of order 2, using the definition and properties on page 131. By "unique", I mean any two such planes can be changed into each other by relabeling the points. Hint: You can't assume your plane has coordinates in GF(2) until you know there is no essentially different plane.
  21. For which of the numbers n, 14 ≤ n ≤ 19, can we say (a) there definitely is a projective plane of order n, (b) there definitely is not, (c) we just can't say? All the information you need is in Cameron's §9.5 and our recent classes.
  22. For which of the numbers n, 20 ≤ n ≤ 30, can we say (a) there definitely is a projective plane of order n, (b) there definitely is not, (c) we just can't say?

To the main class page | the schedule page | the announcements page | my home page.