组合数学 (Spring 2013)/Problem Set 2

Problem 1

Solve the following recurrences:

• [math]\displaystyle{ a_n=3a_{n-1}-2a_{n-2} }[/math], given that [math]\displaystyle{ a_0=2 }[/math] and [math]\displaystyle{ a_1=3 }[/math].
• [math]\displaystyle{ b_n=\frac{1}{2}(b_{n-1}+b_{n-2}) }[/math], given that [math]\displaystyle{ b_0=0 }[/math] and [math]\displaystyle{ b_1=1 }[/math].

Problem 2

[math]\displaystyle{ n }[/math] persons are to be allocated to [math]\displaystyle{ q }[/math] distinct rooms. Find the number of ways that this can be done if only [math]\displaystyle{ m }[/math] of the [math]\displaystyle{ q }[/math] rooms have exactly [math]\displaystyle{ k }[/math] persons each, where [math]\displaystyle{ 1\le m\le q }[/math] and [math]\displaystyle{ mk\le n }[/math].

Problem 3

Prove the following identity:

• [math]\displaystyle{ \sum_{k=1}^n k{n\choose k}= n2^{n-1} }[/math].

(Hint: Use double counting.)

Problem 4

Show that among any group of [math]\displaystyle{ n }[/math] people, where [math]\displaystyle{ n\ge 2 }[/math], there are at least two people who know exactly the same number of people in the group (assuming that "knowing" is a symmetric relation).

Problem 5

Let [math]\displaystyle{ S }[/math] be a subset of [math]\displaystyle{ \{1,2,\ldots,2n\} }[/math] such that [math]\displaystyle{ |S|\gt n }[/math]. Show that there exist [math]\displaystyle{ a,b\in S }[/math] such that [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] are coprime.