2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

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



Начать новую тему Ответить на тему
 
 Перестановка букв с ограничением
Сообщение14.05.2015, 19:49 


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

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

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

Верно?

 Профиль  
                  
 
 Re: Перестановка букв с ограничением
Сообщение14.05.2015, 20:12 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Перестановка букв с ограничением
Сообщение15.05.2015, 07:02 


07/04/15
244
grizzly
Спасибо

 Профиль  
                  
 
 Re: Перестановка букв с ограничением
Сообщение23.12.2017, 15:27 
Аватара пользователя


01/12/17
89
Мельбурн
Насчет второй части (с умножением на $\binom{8}{4}$) все вроде бы в порядке.

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

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

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

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

 Профиль  
                  
 
 Re: Перестановка букв с ограничением
Сообщение23.12.2017, 16:10 
Заслуженный участник
Аватара пользователя


09/09/14
6328
pcyanide в сообщении #1277963 писал(а):
Не можете пояснить логику?
Логика простая. Есть 8 непятёрок. Следовательно, 9 мест, на которые мы можем поставить 5. Количество пятёрок у нас 5. Вот и получается, что нам нужно выбрать 5 мест из 9, чтобы поставить на них пятёрки.

 Профиль  
                  
 
 Re: Перестановка букв с ограничением
Сообщение23.12.2017, 18:57 
Аватара пользователя


01/12/17
89
Мельбурн
grizzly в сообщении #1277970 писал(а):
Логика простая. Есть 8 непятёрок. Следовательно, 9 мест, на которые мы можем поставить 5. Количество пятёрок у нас 5. Вот и получается, что нам нужно выбрать 5 мест из 9, чтобы поставить на них пятёрки.


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

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

 Профиль  
                  
 
 Re: Перестановка букв с ограничением
Сообщение23.12.2017, 19:04 
Заслуженный участник
Аватара пользователя


09/09/14
6328
pcyanide в сообщении #1278032 писал(а):
Однако, откуда берется $\binom{9}{5}$?
Ещё раз: 9 -- это количество мест между перегородками (включая первое и последнее место). Всего возможных перегородок 8, с этим Вы согласились. Перегородки могут стоять рядом, без проблем. А пятёрки обязаны стоять между перегородками.

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

 Профиль  
                  
 
 Re: Перестановка букв с ограничением
Сообщение23.12.2017, 19:07 
Аватара пользователя


01/12/17
89
Мельбурн
grizzly в сообщении #1278037 писал(а):
Всего возможных перегородок 8



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

 Профиль  
                  
 
 Re: Перестановка букв с ограничением
Сообщение23.12.2017, 19:32 
Заслуженный участник
Аватара пользователя


09/09/14
6328
pcyanide в сообщении #1278041 писал(а):
Число перегородок как раз меньше, так как некоторые непятерки обязаны стоять рядом, чтобы общее количество чисел было 13.
Вы не дочитали тот абзац до конца.

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

 Профиль  
                  
 
 Re: Перестановка букв с ограничением
Сообщение24.12.2017, 01:31 
Аватара пользователя


01/12/17
89
Мельбурн
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}$.

 Профиль  
                  
 
 Re: Перестановка букв с ограничением
Сообщение24.12.2017, 02:03 
Заслуженный участник
Аватара пользователя


09/09/14
6328
pcyanide в сообщении #1278183 писал(а):
Самое удивительное (конечно не для Вас, а для меня
Ничего, бывает :) Это просто заскок какой-то. Давайте ещё раз -- следите за руками:

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

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

-- 24.12.2017, 02:21 --

Изображение

 Профиль  
                  
 
 Re: Перестановка букв с ограничением
Сообщение24.12.2017, 03:13 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Перестановка букв с ограничением
Сообщение24.12.2017, 10:49 
Заслуженный участник
Аватара пользователя


09/09/14
6328
pcyanide в сообщении #1278203 писал(а):
Так, действительно, проще.
Всё верно.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group