Задача...

From

Max Alekseyev (2:5015/60)

To

Denis Yarkin

Date

2002-07-17T02:18:28Z

Area

RU.ALGORITHMS

████ OS/2        Hi, Denis !

Replying to a message of Denis Yarkin to All:

 DY>     Формулировка:
 DY>         Определить число способов, которыми можно рассадить N учащихся
 DY> за         M столами при N<=2M если за каждым столом могут
 DY> разместиться 2         учащихся.

Пусть целиком занято k столов, тогда оставшиеся N-2k человек сидят по одному за столом. Результат получается из

* выбрать 2k человек                     = С(N,2k)
* выбрать k столов                       = C(M,k)
* рассадить 2k человек за k столов       = (2k)!/2^k
* выбрать N-2k столов из оставшихся      = C(M-k,N-2k)
* рассадить N-2k человек за N-2k столов = (N-2k)!

здесь C(u,v) - число сочетаний из u по v

Итак, ответ

\sum_k C(N,2k) C(M,k) (2k)!/2^k C(M-k,N-2k) (N-2k)! =
= \sum_k N! M! / ((N-2k)! k! (M-N+k)! 2^k)

суммирование ведется по k=0..[N/2]

Regards,      °°
        Max    ~

--- OS/2 Uptime:  0d 0h 43m 17s 517ms
 * Origin: It's okay to call someone stupid; just don't prove it. (2:5015/60)