кролики Дирихле

[staric]

Дирихле хочет рассадить дюжину кроликов по 11 клеткам так, чтобы ни один кролик не оказался в клетке один. Сколькими способами он это может сделать, притом что клетки занумерованы, а все кролики для него одинаковы?

[Shadow]

$\displaystyle \sum\limits_{k=1}^6 C_{11}^k\cdot C_{11-k}^{k-1}$

[staric]

Ну, раз все так быстро... тогда ишшо 2 вопроса:
ту же дюжину по
1) 12 клеткам
2) по 24 клеткам (им Тождества №? )

[Shadow]

Давайте сразу по $n$ клеткам:
$\displaystyle \sum\limits_{k=1}^6 C_{n}^k\cdot C_{11-k}^{k-1}$

[staric]

ОК, все быстро и точно.
Сразу же имеет место тождество ($m$ кроликов, $n\ne m$ клеток):

$$\sum_{k=1}^{\lfloor m/2\rfloor} {n\choose k} {m-k-1\choose k-1} = \sum_{k=0}^{\min{(m,n-1)}}(-1)^k {n\choose k}{m+n-2k-1\choose m-k}$$