组合数学 (Spring 2013)/Problem Set 2: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
Created page with "== Problem 1== Solve the following recurrences: * <math>a_n=3a_{n-1}-2a_{n-2}</math>, given that <math>a_0=2</math> and <math>a_1=3</math>. * <math>b_n=\frac{1}{2}(b_{n-1}+b_{n-2…"
 
imported>Etone
No edit summary
Line 7: Line 7:
<math>n</math> persons are to be allocated to <math>q</math> distinct rooms. Find the number of ways that this can be done if only <math>m</math> of the <math>q</math> rooms have exactly <math>k</math> persons each, where <math>1\le m\le q</math> and <math>mk\le n</math>.
<math>n</math> persons are to be allocated to <math>q</math> distinct rooms. Find the number of ways that this can be done if only <math>m</math> of the <math>q</math> rooms have exactly <math>k</math> persons each, where <math>1\le m\le q</math> and <math>mk\le n</math>.


= Problem 3=
== Problem 3==
Prove the following identity:  
Prove the following identity:  
*<math>\sum_{k=1}^n k{n\choose k}= n2^{n-1}</math>.
*<math>\sum_{k=1}^n k{n\choose k}= n2^{n-1}</math>.

Revision as of 10:15, 17 April 2013

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.