Advanced Combinatorics Exercises - Questions PDF

Preview

Summary

Advanced Combinatorics Exercises...

Description

MTH742U Advanced Combinatorics Exercises (1) Multinomial coefficients. For non-negative integers n, k, and n1 , n2 , . . . , nk with n1 + n2 + · · · + nk = n, denote by   n n1 , n2 , . . . , nk the number of ways to distribute n elements into k consecutive boxes, such that, for each j with 1 ≤ j ≤ k, the j-th box contains precisely nj elements (these numbers are called multinomial coefficients). Show that   n n! = . n1 , n2 , . . . , nk n1 ! n2 ! · · · nk ! (2) Show: for given integers n, k with 1 ≤ k ≤ n, there is exactly  one partition n = n n1 +· · ·+nk of n maximizing the multinomial coefficient n1 ,...,n , namely the partition k j n k jnk  + r n = (k − r) +1 , k k where 0 ≤ r < k and r ≡ n mod k. Conclude that   n n! max = k−r  n  k n n , . . . , n (n1 ,...,nk )∈N0 1 k ⌊ ⌋ + 1 !r ⌊ ⌋! k

n1 +···+nk =n

k

with r as above.

(3) Let S be a finite set with n ≥ 1 elements. By means of a suitable bijection show that the number of subsets of S of even size equals the number of subsets of odd size. (4) Show that, for 1 ≤ k ≤ n, we have    n−1  X i n . = k−1 k i=k−1 (5) (The Chu-Vandermonde Identity) Using the binomial theorem, show that, for integers k, m, n with 0 ≤ k ≤ m + n, we have X m n  m + n = . i k−i k i≥0

(6) Let k, n, and a1 , . . . , ak be given non-negative integers. How many solutions (x1 , x2 , . . . , xk ) does the linear diophantine equation x1 + · · · + xk = n have with the property that xi ≥ ai for all i = 1, 2, . . . , k? Qn (7) Define the factorials n! for integers n ≥ 0 by 0! = 1 and n! = i=1 i for n ≥ 1. Using the Formula       n j n n−i = (1) i j−i j i 1

2

plus induction on k, show that   n n! , 0 ≤ k ≤ n, = k! (n − k)! k   where nk denotes the number of k-element subsets of an n-element set.  n  n  (8) Again making use of Formula (1), prove that k−1 < k for 1 ≤ k ≤ n2 .  (9) Show: if gcd(n, k) = 1, then kn ≡ 0 mod n.

(10) Let S be an n-set. (a) Choose an ordering S = {x1 , x2 , . . . , xn } of the elements of S, and set   C = ∅, {x1 }, {x1 , x2 }, . . . , {x1 , . . . , xn−1 }, S . Show that C is a maximal chain of B(S).

(b) Let C be a maximal chain of B(S). Show that C arises from an ordering of S in the way described in Part (a). (11) The one-dimensional Littlewood-Offord problem. Given real numbers a1 , a2 , . . . , an with the property that  n ai ≥ 1 for in= 1, 2, . . . , n, and a half-open interval I = [b, b + 1), of the 2 points show that at most ⌊n/2⌋ n X

εi a i ,

ε1 , . . . , εn ∈ {0, 1}

i=1

lie in the interval I .

(12) Let b1 , b2 , . . . , bn be real numbers, such that min1≤ν≤n bν = b > 0, and set B := (b1 , b2 , . . . , bn ). Moreover, let V = (ε1 , ε2 , . . . , εn ) with εν ∈ {1, −1}, and set V B = P n ν=1 εν bν . Show that     n   sup V : x − b ≤ V B < x + b ≤ . (2) [n/2] x∈R

(13) Derangements. By a derangement on the set [n] one means a permutation σ ∈ Sn without fixed points. Let dn be the number of derangements on [n]. Derive a 2-step recurrence relation for the sequence {dn }n≥0 , and use this to compute the exponential P generating function D(x) = n≥0 dn xn /n!, and to obtain an explicit formula for dn . Show also that dn = ndd−1 + (−1)n , n ≥ 1. (3) (2) (14) For n ≥ 0, let In := Fn be the number of solutions of the equation x2 = 1 in Σn . Using induction on n, show that

n1/2 ≤ In /In−1 ≤ 1 + n1/2 ,

n ≥ 1.

Conclude that In /In−1 ∼ n1/2 that is, that

In /In−1 n1/2

(n → ∞);

converges to 1 as n → ∞.

3 (2)

(15) Let In = Fn , as in the previous exercise. Show: if n ≥ 4s − 2, then 2s divides In . (16) Show that the generating function alt (z) := Fm

X

F (m) (An )z n /n!

n≥0

is given by Fmalt(z)

" 1 = exp 2

X

d

!

z /d

d|m

+ exp

!# X d−1 d (−1) z /d .

(4)

d|m

Use this result to obtain explicit formulae for the Frobenius numbers F (m) (An ) of alternating groups. (17) By expanding the generating function X f (x) = an xn = n≥1

x(1 − x)3 1 − 5x + 7x2 − 4x3

for the number an of polyominoes with n squares into partial fractions, or otherwise, compute an asymptotic formula for an . You may use the fact that γ1 = 3.20556943 . . . and γ2,3 = 0.897215 ± 0.665457i are the reciprocal values of the three distinct roots of the polynomial Q(x) = 1 − 5x + 7x2 − 4x3 . Your asymptotic formula for an should be explicit in the quantities γ1 , γ2 , γ3 .

(18) Let V be a finite-dimensional complex vector space, endowed with a positive-definite Hermitean form h, and let P : V → V be a positive linear map. Show that the eigenvalues of P are real and positive. (19) (i) Arguing straight from the definition, show that there is no 3-dimensional Hadamard matrix. (ii) List all normalized Hadamard matrices of dimension 4. (20) Establish the recurrence relation S(n + 1, k) =

n   X n S(µ, k − 1) µ µ=0

for n ≥ 0 and k ≥ 1 by a direct combinatorial argument. (21) By a 2-regular graph we mean an undirected labeled (combinatorial) graph, all of whose vertices have degree 2. Using the exponential formula, compute a generating function for the number of 2-regular graphs on n vertices....