组合数学 (Fall 2015)/Problem Set 1: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
Created page with "<font color="red" size=5>每道题目的解答都要有完整的解题过程。中英文不限。</font> == Problem 1 == #有<math>k</math>种不同的明信片,每种明信…"
 
imported>Etone
No edit summary
Line 9: Line 9:


== Problem 2 ==
== Problem 2 ==
Find the number of ways to select <math>2n</math> balls from <math>n</math> identical blue balls, <math>n</math> identical red balls and <math>n</math> identical green balls.
== Problem 3 ==
* Give a combinatorial proof for the following identity:
* Give a combinatorial proof for the following identity:
:<math>
:<math>
Line 16: Line 19:
*Give a closed form for <math>\sum_{k=1}^n k^2{n\choose k}</math> and prove it.
*Give a closed form for <math>\sum_{k=1}^n k^2{n\choose k}</math> and prove it.


==Problem 3==
==Problem 4==
A <math>2\times n</math> rectangle is to be paved with <math>1\times 2</math> identical blocks and <math>2\times 2</math> identical blocks. Let <math>f(n)</math> denote the number of ways that can be done. Find a recurrence relation for <math>f(n)</math>, solve the recurrence relation.
A <math>2\times n</math> rectangle is to be paved with <math>1\times 2</math> identical blocks and <math>2\times 2</math> identical blocks. Let <math>f(n)</math> denote the number of ways that can be done. Find a recurrence relation for <math>f(n)</math>, solve the recurrence relation.

Revision as of 02:11, 21 September 2015

每道题目的解答都要有完整的解题过程。中英文不限。

Problem 1

  1. [math]\displaystyle{ k }[/math]种不同的明信片,每种明信片有无限多张,寄给[math]\displaystyle{ n }[/math]个人,每人一张,有多少种方法?
  2. [math]\displaystyle{ k }[/math]种不同的明信片,每种明信片有无限多张,寄给[math]\displaystyle{ n }[/math]个人,每人一张,每个人必须收到不同种类的明信片,有多少种方法?
  3. [math]\displaystyle{ k }[/math]种不同的明信片,每种明信片有无限多张,寄给[math]\displaystyle{ n }[/math]个人,每人收到[math]\displaystyle{ r }[/math]张不同的明信片(但不同的人可以收到相同的明信片),有多少种方法?
  4. 只有一种明信片,共有[math]\displaystyle{ m }[/math]张,寄给[math]\displaystyle{ n }[/math]个人,全部寄完,每个人可以收多张明信片或者不收明信片,有多少种方法?
  5. [math]\displaystyle{ k }[/math]种不同的明信片,其中第[math]\displaystyle{ i }[/math]种明信片有[math]\displaystyle{ m_i }[/math]张,寄给[math]\displaystyle{ n }[/math]个人,全部寄完,每个人可以收多张明信片或者不收明信片,有多少种方法?

Problem 2

Find the number of ways to select [math]\displaystyle{ 2n }[/math] balls from [math]\displaystyle{ n }[/math] identical blue balls, [math]\displaystyle{ n }[/math] identical red balls and [math]\displaystyle{ n }[/math] identical green balls.

Problem 3

  • Give a combinatorial proof for the following identity:
[math]\displaystyle{ \sum_{k=1}^n k{n\choose k}=n\cdot 2^{n-1}. }[/math]
  • Give a closed form for [math]\displaystyle{ \sum_{k=1}^n k^2{n\choose k} }[/math] and prove it.

Problem 4

A [math]\displaystyle{ 2\times n }[/math] rectangle is to be paved with [math]\displaystyle{ 1\times 2 }[/math] identical blocks and [math]\displaystyle{ 2\times 2 }[/math] identical blocks. Let [math]\displaystyle{ f(n) }[/math] denote the number of ways that can be done. Find a recurrence relation for [math]\displaystyle{ f(n) }[/math], solve the recurrence relation.