组合数学 (Fall 2015)/Problem Set 1

From TCS Wiki
Revision as of 02:13, 21 September 2015 by imported>Etone
Jump to navigation Jump to search

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

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

  • 一个长度为[math]\displaystyle{ n }[/math]的“山峦”是如下由[math]\displaystyle{ n }[/math]个"/"和[math]\displaystyle{ n }[/math]个"\"组成的,从坐标[math]\displaystyle{ (0,0) }[/math][math]\displaystyle{ (0,2n) }[/math]的折线,但任何时候都不允许低于[math]\displaystyle{ x }[/math]轴。例如下图:
   /\
  /  \/\/\    /\/\
 /        \/\/    \/\/\
 ----------------------
长度为[math]\displaystyle{ n }[/math]的“山峦”有多少?
  • 一个长度为[math]\displaystyle{ n }[/math]的“地貌”是由[math]\displaystyle{ n }[/math]个"/"和[math]\displaystyle{ n }[/math]个"\"组成的,从坐标[math]\displaystyle{ (0,0) }[/math][math]\displaystyle{ (0,2n) }[/math]的折线,允许低于[math]\displaystyle{ x }[/math]轴。长度为[math]\displaystyle{ n }[/math]的“地貌”有多少?

Problem 5

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.

Problem 6

  • [math]\displaystyle{ s_n }[/math]表示长度为[math]\displaystyle{ n }[/math],没有2个连续的1的二进制串的数量,即
    [math]\displaystyle{ s_n=|\{x\in\{0,1\}^n\mid \forall 1\le i\le n-1, x_ix_{i+1}\neq 11\}| }[/math]
[math]\displaystyle{ s_n }[/math]
  • [math]\displaystyle{ t_n }[/math]表示长度为[math]\displaystyle{ n }[/math],没有3个连续的1的二进制串的数量,即
    [math]\displaystyle{ t_n=|\{x\in\{0,1\}^n\mid \forall 1\le i\le n-2, x_ix_{i+1}x_{i+2}\neq 111\}| }[/math]
    1. 给出计算[math]\displaystyle{ t_n }[/math]的递归式,并给出足够的初始值。
    2. 计算[math]\displaystyle{ t_n }[/math]的生成函数[math]\displaystyle{ T(x)=\sum_{n\ge 0}t_n x^n }[/math],给出生成函数[math]\displaystyle{ T(x) }[/math]的闭合形式。

注意:只需解生成函数的闭合形式,无需展开。