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

MAT 344

2022 S

Problem Set 4

Inclusion-Exclusion, Generating Functions, Recurrences

Learning Objectives

These problems relate to the course learning outcomes:

• Select and justify appropriate tools to analyze a counting problem,

• Analyze a counting problem by proving an exact or approximate enumeration, or a method to compute one efficiently; and

•  Construct counting problems which show the usefulness or limitations of combinato- rial tools.

1. Give combinatorial proofs of these identities, where dk  denotes the number of derange- ments of [k]:

(a)

◆ =  ✓i(m)◆ ( − 1)i ✓n r(−) i◆ .

Hint: consider certain subsets of [n] containing [m].

(b)

n! =  ✓ ◆k(n) dk

2. Let an  be the sequence with a0  = 0 and

an+1  = 2(n +1)an +(n +1)!

Find and prove a closed formula for an , depending only on n.

3. Let fn  be the number of strings of length n using the letters A,B,C,D, such that there are an even number of As; 1, 2, 3 or 4 Bs; either 2 or 5 Cs; and at least 1 D . So f0  = f1  = f2  = f3  = 0, while f4  = 12 and f5  = 60. Find a generating function for fn , and explain how you got it.

4. In English, the word“bu↵alo”can be used as a verb, a common noun, or a place name.  This leads to a linguistic puzzle where “Bu↵alo bu↵alo bu↵alo ... bu↵alo.”with n “bu↵alo”s can be interpreted as a meaningful sentence. However, these sentences may  not have a unique interpretation. Let bn  denote the number of ways to interpret the  sentence, and take b0  = b1  = 1. The sequence satisfies the recurrence

n−2

bn  = b0 bn−2 + b1 bn−3 + b2 bn−4 + ··· + bn−2 b0  =X bk bn−2 −k .

k=0