Припустімо, що на мирній конференції існує m марсіанських & землян. Для того, щоб марсіани залишалися спокійними на конференції, ми повинні переконатися, що жодні два марсіани не сидітимуть разом, так, щоб між будь-якими двома марсіанами був хоча б один землянин?

Відповідь:

а) # (n! (n + 1)!) / ((n-m + 1)!) #

б) # (n! (n-1)!) / ((n-m)!) #

Пояснення:

На додаток до деяких додаткових міркувань, ми будемо використовувати три загальні методи підрахунку.

По-перше, ми скористаємося тим, що якщо є # n # способів зробити одну річ і # m # способи зробити інше, тоді припускаючи, що завдання незалежні (що ви можете зробити для одного, не покладайтеся на те, що ви робили в іншому), є # nm # способів зробити обидва. Наприклад, якщо у мене є п'ять сорочок і три пари штанів, то є #3*5=15# вбрання я можу зробити.

По-друге, ми будемо використовувати це число способів впорядкування # k # об'єктів #k! #. Це тому, що є # k # способи вибору першого об'єкта, а потім # k-1 # способи вибору другого, і так далі, і так далі. Таким чином, загальна кількість шляхів є #k (k-1) (k-2) … (2) (1) = k! #

Нарешті, ми будемо використовувати це число способів вибору # k # об'єктів з набору # n # об'єктів # ((n), (k)) = (n!) / (k! (n-k)!) # (вимовляється як n вибрати k). Описано, як отримати цю формулу.

а) Якщо ми спочатку не враховуємо розколи, є #m! # способів замовити марсіани і #n! # способи замовлення землян. Нарешті, ми повинні побачити, де розміщені марсіани. Оскільки кожен марсіан повинен бути розміщений або на кінці, або між двома землянами, є # n + 1 # місця, де вони можуть сидіти (один ліворуч від кожного землянина, а потім ще один на крайньому правому краю). Як є # m # Марсіани, це означає, що є # ((n + 1), (m)) = ((n + 1)!) / (m! (n + 1-m)!) # можливі способи їх розміщення. Таким чином, загальна можлива кількість сидінь

#n! m! ((n + 1)!) / (m! (n + 1-m)!) = (n! (n + 1)!) / ((n-m + 1)!) #

б) Ця проблема подібна до вищезазначеної. Щоб спростити справу, підберемо землянина і називаємо його президентом. Тому що неважливо, як обертається коло, замість того, щоб посилатися на домовленості, засновані на абсолютному впорядкуванні, ми розглянемо домовленості на основі їхнього відношення до президента.

Як і вище, якщо ми починаємо з президента і продовжуємо за годинниковою стрілкою по колу, можна розрахувати кількість способів замовлення інших учасників. Як є # m # Марсіани і # n-1 # що залишилися землян, є #m! # способів замовити марсіани і # (n-1)! # способи замовлення залишилися землян.

Далі нам знову потрібно позиціонувати марсіан. На цей раз у нас немає додаткового місця в кінці, таким чином, є тільки # n # місця, де вони можуть сидіти. Тоді є # ((n), (m)) = (n!) / (m! (n-m)!) # способи їх розміщення. Таким чином, загальна можлива кількість сидінь

# (n-1)! m! (n!) / (m! (n-m)!) = (n! (n-1)!) / ((n-m)!) #