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

vk173500291

5 декабря 2019 г. в 12:48

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

sova

6 декабря 2019 г. в 10:43

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

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

(m–2)·(n–2) клеток, на которые можно поставить третью ладью

...
(m–(k–1))·(n–(k–1)) клеток, на которые можно поставить k–ую ладью

По правилу умножения эти выборы надо умножить и разделить на перестановку из 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!) – О т в е т