Задать свой вопрос   *более 50 000 пользователей получили ответ на «Решим всё»

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

Условие

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

предмет не задан 889

Все решения

На шахматной доске 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!) - О т в е т

Написать комментарий

Категория

Меню

Присоединяйся в ВК