Перестановка букв с ограничением

[2old]

Есть слово $5555544443333$. Какое количество всех перестановок таких, что любые две $5$ не стояли рядом.

Сначала переведем все $5$ в $1$, а остальные в $0$. Тогда для $1$ нужно выбрать $5$ мест из $8-1+2$. Получается $ 9 \choose 5$.
Теперь вспомним, что нолики двух видов. Нужно выбрать нолики $8 \choose 4$, которые нужно "переделать" в тройки.

В итоге имеем ${8}\choose{4}$ $9\choose 5$

Верно?

[grizzly]

Верно, но такие пасы с привлечением новых сущностей :) Не удобнее было оставить пятёрки и непятёрки двух видов? Впрочем, не суть важно.

[2old]

grizzly
Спасибо

[pcyanide]

Насчет второй части (с умножением на $\binom{8}{4}$) все вроде бы в порядке.

А вот насчет первой части, кажется сильно упрощено.

У нас 13 позиций, а пятерок только пять. Если 5 на первом месте, это не означает, что все пятерки должны быть на нечетных позициях. Например, в расположнии 54 45 45 33 53 43 5 две пятерки на нечетных, три на четных.

Откровенно говоря, я не подсчитывал, но мне кажется, если делать «в лоб»: по очереди ставить 5 сначала в 1-ю, позицию, потом во 2-ю т.д., подсчитывая всевозможные расположения остальных пятерок правее начальной, должно получиться больше, чем $\binom{9}{5}$.

Не можете пояснить логику?

[grizzly]

pcyanide в сообщении #1277963 писал(а):

Не можете пояснить логику?

Логика простая. Есть 8 непятёрок. Следовательно, 9 мест, на которые мы можем поставить 5. Количество пятёрок у нас 5. Вот и получается, что нам нужно выбрать 5 мест из 9, чтобы поставить на них пятёрки.

[pcyanide]

grizzly в сообщении #1277970 писал(а):

Логика простая. Есть 8 непятёрок. Следовательно, 9 мест, на которые мы можем поставить 5. Количество пятёрок у нас 5. Вот и получается, что нам нужно выбрать 5 мест из 9, чтобы поставить на них пятёрки.

Что-то у меня заклинило. (Выходной день — мозги отказываются работать.) 8 непятерок — нет возражений. Второе, с чем я не могу не согласиться: положение пятерок однозначно определяет положение непятерок (без учета их внутренних перестановок, число которых $\binom{8}{4}$, так как при заданном расположении непятерок позиции троек определяют позиции четверок).

Таким образом все упирается в подсчет возрастающих последовательностей из пяти чисел, находящихся в промежутке [1,13] причем разница между двумя соседними должна быть больше 1. Если показать, что число таких расположений $\binom{9}{5}$ — нет возражений!

[grizzly]

pcyanide в сообщении #1278032 писал(а):

Однако, откуда берется $\binom{9}{5}$?

Ещё раз: 9 -- это количество мест между перегородками (включая первое и последнее место). Всего возможных перегородок 8, с этим Вы согласились. Перегородки могут стоять рядом, без проблем. А пятёрки обязаны стоять между перегородками.

Иногда на таких задачах действительно заклинивает. Лучше всего -- взять пример с меньшим количеством букв и посчитать в лоб. Например: три пятёрки и три единицы; три пятёрки и четыре единицы. После просчёта этих простеньких примеров в лоб сомнений не должно остаться.

[pcyanide]

grizzly в сообщении #1278037 писал(а):

Всего возможных перегородок 8

Число перегородок как раз меньше, так как некоторые непятерки обязаны стоять рядом, чтобы общее количество чисел было 13.

[grizzly]

pcyanide в сообщении #1278041 писал(а):

Число перегородок как раз меньше, так как некоторые непятерки обязаны стоять рядом, чтобы общее количество чисел было 13.

Вы не дочитали тот абзац до конца.

И чтоб два раза не вставать: следующий тоже прочитайте, пожалуйста.

[pcyanide]

grizzly в сообщении #1278051 писал(а):

Вы не дочитали тот абзац до конца.

Действительно недочитал, уж очень спать хотелось в два часа ночи, извините. Однако Вы либо тоже куда-то торопились,
либо опирались на некий факт, который считали само собой разумеющимся, тогда как дилетантам (наподобие Siempre Su Servidor), приходится переоткрывать.

Вот и буду переоткрывать с утра пораньше со свежим взглядом.

Будем считать пятерки границами промежутков. В каждом из таких промежутков обязана присутствовать одна единица (выполняющая роль непятерки).

Пусть у нас n пятерок. Тогда единиц должно быть не меньше n-1.

Если единиц точно n-1, то получаем ровно 1 положение.

Если единиц n, то свободная единица может идти либо в начало, либо в конец, либо в один из n-1 промежутков между пятерками. Получаем n+1 возможных положений.

Если единиц n+1, имеем две свободные единицы и те же n+1 промежутков, поэтому каждому положению соответствует пара чисел, каждое из которых от 1 до n+1. Чтобы избежать «déjà vu», будем рассматривать только неубывающие последовательности.

Например, для 3 пятерок и 4 единиц имеем:

11: 1151515
12: 1511515
13: 1515115
14: 1515151
22: 5111515
23: 5115115
24: 5115151
33: 5151115
34: 5151151
44: 5151511

Чтобы посчитать количество таких пар, увеличим первое число на 1. Тогда числа станут разными и получим «классические» сочетания, число которых $\binom{n+2}{2}$.

В общем случае получаем $\binom{m+1}{m-n+1}$ положений, где n - количество пятерок, m - количество единиц.

В частности, при n=5, m=8 получаем $\binom{9}{4}$. Самое удивительное (конечно не для Вас, а для меня, поскольку, к своему стыду, я до сих пор не понимаю Вашей логики), что это в точности совпадает с Вашей оценкой $\binom{9}{5}$.

[grizzly]

pcyanide в сообщении #1278183 писал(а):

Самое удивительное (конечно не для Вас, а для меня

Ничего, бывает :) Это просто заскок какой-то. Давайте ещё раз -- следите за руками:

Пусть есть 9 урн, стоящих вряд вплотную друг к другу. Смотрим на стенки этих урны как на перегородки. Первая и последняя стенки одиночные -- их не учитываем. Каждая двойная стенка (таких 8) будет нашей 1. У нас есть шары -- на каждом нарисована цифра 5. Теперь внимание:

-- Если мы разложим 5 шаров в эти урны, то получим допустимое число из нашей задачи, состоящее из цифр 5 (шары) и 1 (двойные перегородки).
-- И наоборот: любому допустимому числу соответствует точно одно расположение шаров в урнах.

Теперь имеем очень простой вопрос: сколькими способами можно разложить 5 шаров в 9 урн (в урну вмещается не более одного шара, конечно -- всюду выше это тоже подразумевается).

-- 24.12.2017, 02:21 --

[pcyanide]

Все действительно элементарно: 8 единиц создают 9 урн (две с краев, и 7 между ними). Пронумеруем эти урны от 1 до 9 и каждому расположению пятерок поставим в соответствие 5 чисел, содержащих номера урн. Вот и получаем $\binom{9}{5}$. Так, действительно, проще.

[grizzly]

pcyanide в сообщении #1278203 писал(а):

Так, действительно, проще.

Всё верно.

По себе знаю, что если есть собственная идея решения (пусть в ней даже на семь вёрст крюк -- мне это ерунда :) разбираться в чужом бывает непросто. В комбинаторике это проявляется сильнее всего.