Question

Скількома способами можна розставити в ряд 2n нулів та n одиниць так, щоб дві одиниці не стояли поруч?

Answer 1

Расставим в ряд n единиц и n+1 нулей каким-то образом. Докажем, что количество таких расстановок равно количеству требуемых расстановок. Действительно, если мы добавим после каждой единицы (кроме последней) нуль, то будет выполняться требуемое условие, а если мы удалим из требуемой расстановки по нулю после каждой единицы (это можно сделать, так как ни после какой единицы не стоит единица, следовательно, после всех единиц (кроме последней) стоит нуль), получим расстановку, из которой начинали. Таким образом, получается биекция.

Способов расставить в ряд n единиц и n+1 нулей будет (2n+1)! / (n! * (n+1)!), так как всего элементов 2n+1, при этом n и n+1 идентичных соответственно.

Ответ: (2n+1)! / (n! * (n+1)!).

Answer 2

Давайте розглянемо проблему.

Ми маємо 2n нулів та n одиниць. Ми хочемо розташувати їх в ряд так, щоб дві одиниці не стояли поруч. Один з способів розв'язання - це використовувати принципи обмеження. Почнемо з розгляду кількості способів, які ми маємо заборонити.

Якщо ми розташовуємо дві одиниці поруч, ми видаляємо одну одиницю з ряду. Тепер у нас є n+1 одиниць та 2n нулів. Очевидно, можна знайти (n+2) місця для розташування одиниць, де кожне місце позначає позицію між двома нулями. Таким чином, ми маємо (n+2) можливих способів розташування двох одиниць поруч.

Зараз, якщо ми візьмемо ці (n+2) можливості та вставимо їх між (n+1) одиницею, то ми отримаємо (n+1) місце для розташування одиниць. Тобто, ми можемо заборонити розташування двох одиниць поруч шляхом розташування їх між одиницями з попереднього кроку.

Отже, загальна кількість способів розташування 2n нулів та n одиниць без умови, що дві одиниці не можуть стояти поруч, дорівнює кількості способів розташування (n+1) одиниць між (n+1) нулем. Це можна побачити як комбінацію:

C(n+1, n+1) = (n+1)! / [(n+1)! * 1!] = 1.

Отже, існує лише 1 спосіб розташування 2n нулів та n одиниць в ряд так, щоб дві одиниці не стояли поруч.