Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Math 475

Exam 2, Fall 2023

1. Let X and Y denote nonempty finite sets such that |X| = 2|Y|. Using inclusion/exclusion, find a formula for the number of surjective functions from X to Y . Express your answer in terms of y = |Y|.

2. Consider the set S = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Find the number of equivalence relations on S that have exactly 5 equivalence classes. Give the exact numerical answer, not just a formula. Justify your answer.

3. (i) (5 points) Find the number of ways to put 7 nonattacking rooks on the 7 by 7 chessboard below, with forbidden positions as shown. Express the answer as a specific integer, not just the formula. (ii) (5 points) Explain why your answer is correct.

4. Find the number of integer solutions to x + y + z = 13 such that

0 ≤ x ≤ 7,            −2 ≤ y ≤ 2,               1 ≤ z ≤ 6.

5. Let n denote a positive integer, and consider an n by n chessboard. A cricket starts at the top left square and ends up at the bottom right square, after 2n − 2 hops. Each hop takes the cricket from a given square to an adjacent square to the east or south. The cricket hops at random, and each path of length 2n−2 from the top left square to the bottom right square is equally likely. Let Pn denote the probability that the cricket stays on or above the main diagonal throughout its trip.

(i) (3 points) Find P1, P2, P3.

(ii) (3 points) Express Pn in closed form.

(iii) (4 points) Prove that your answer to (ii) is correct for all n.

6. For an integer n ≥ 0 let hn denote the number of nonnegative integer solutions to

2e1 + 3e2 + · · · + nen−1 = n.

We interpret h0 = 1. Find the (ordinary) generating function G(x) for the sequence 

(i) (5 points) Find h1, h2, h3, h4, h5.

(ii) (5 points) Express G(x) as a product.

7. For a variable x, express (x + 1)(x + 2)(x + 3)(x + 4) in terms of

1,      x,      x(x − 1),      x(x − 1)(x − 2),      x(x − 1)(x − 2)(x − 3).

8. Consider the multiset

M = {∞ · a,∞ · b, ∞ · c, ∞ · d, ∞ · e}.

For n ≥ 0 let hn denote the number of n-combinations of M.

(i) (5 points) Find the (ordinary) generating function for the sequence  (in closed form, no infinite sum).

(ii) (5 points) Find the exponential generating function for the sequence  (in closed form, no infinite sum).

9. Consider the sequence  such that

(i) (3 points) Find h0, h1, h2, h3, h4.

(ii) (2 points) Find hn in closed form (no sum involved).

(iii) (5 points) Prove that your answer to (ii) is correct.

10. (i) (5 points) Find the number of circular 9-permutations of the multiset

{∞ · a,∞ · b, ∞ · c}

(give the exact integer value, not just a formula).

(ii) (5 points) Prove that your answer is correct.