Задача...

From

Max Alekseyev (2:5015/60)

To

Denis Yarkin

Date

2002-07-29T14:33:42Z

Area

RU.ALGORITHMS

████ OS/2        Hi, Denis !

Replying to a message of Max Alekseyev to Denis Yarkin:

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

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

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

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

 MA> Итак, ответ

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

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

Поправка: правильные пределы суммирования k = max{(N-M),0} .. min{[N/2],M}.

А вообще, в таких суммах удобнее не указывать значения пределов суммирования и считать, что суммирование ведется по всем индексам, для которых слагаемые имеют смысл и не равны нулю.

Regards,      °°
        Max    ~

--- FleetStreet 1.27.3.8
 * Origin:  (2:5015/60)