Задача 42287 сколькими способами можно расставить k...

vk173500291

2019-12-05 12:48:51

сколькими способами можно расставить k ладей на шахматной доске размером n*m так, чтобы они не угрожали друг другу т.е так, чтобы никакие две из них не стояли на одной вертикали или горизонтали?

sova

2019-12-06 10:43:56

На шахматной доске mn клеток.
Первую ладью можно поставить на любое из mn мест.

Ладья ходит по горизонтали и вертикали.
Вычеркиваем горизонталь и вертикаль на которых она стоит.
Получаем (m-1)*(n-1) клеток, на которые можно поставить вторую ладью.

(m-[red]2[/red])*(n-[red]2)[/red] клеток, на которые можно поставить [red]третью[/red] ладью

...
(m-([green]k-1[/green]))*(n-([green]k-1[/green])) клеток, на которые можно поставить [green]k-ую[/green] ладью

По правилу умножения эти выборы надо умножить и разделить на перестановку из k
элементов

mn*(m-1)*(n-1)*... (m-(k-1))*(n-(k-1))/k!=

=(m*(m-1)*... (m-k 1))*(n*(n-1)*... (n-k 1))/k!=(m!/(m-k)!)*(n!/(n-k)!) * 1/k!=

=(m!*n!)/((m-k)!*(n-k)!*k!) - О т в е т