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)!).