Комбинаторика, задачки..

[Elizaveta]

Нужна помощь, с комбинаторикой на Вы, пытаюсь разбираться и решать, но очень сомневаюсь в правильности этих попыток.. А вот одна задачка никак не получается:
"Сколькими способами можно упорядочить множество {1,2,...,n} так, чтобы между числами 1,2,3 стояло ровно одно другое число?"
Спрашивала у преподователя, порядок следования самих 1,2,3 не важен, т.е. может быть например 3,7,1,2..

И еще одну задачу преподователь решить не смог, сказал решайте вручную считая варианты, потом с одногруппником решили проще, но все равно без формул комбинаторики, вот интересно, есть все-таки "научное" ее решение..
"Есть 7 экземпляров первой вниги, 8 - второй, 9 третьей. Сколькими способами можно разделить их между двумя людьми так, чтобы каждый получил 12 книг?"

Заранее, спасибо..

[VAL]

Elizaveta писал(а):

"Сколькими способами можно упорядочить множество {1,2,...,n} так, чтобы между числами 1,2,3 стояло ровно одно другое число?"
Спрашивала у преподователя, порядок следования самих 1,2,3 не важен, т.е. может быть например 3,7,1,2..

Выберем элемент, который будет "разбавлять" 1, 2, 3. Это можно сделать n-3 -я способами. Расставим 1, 2, 3 и выбранный элемент разрешенными способами. Их 12. А теперь, полагая нашу конструкцию из 4-х элементов за один объект, произвольно расставим n-3 элемента (один из них наш сборный).

Цитата:

И еще одну задачу преподователь решить не смог, сказал решайте вручную считая варианты, потом с одногруппником решили проще, но все равно без формул комбинаторики, вот интересно, есть все-таки "научное" ее решение..
"Есть 7 экземпляров первой вниги, 8 - второй, 9 третьей. Сколькими способами можно разделить их между двумя людьми так, чтобы каждый получил 12 книг?"

Рапсскажите сначала Ваше простое

[Elizaveta]

VAL спасибо большое за первую задачу, вроде бы все понятно

А вторую мы решили так.. Приняли что кол-во 1 книг - Х, 2 книг - Y, 3 - Z.
Найдем комбинации книг для первого человека, у второго получится автоматом.
Сумма X+Y больше либо равно 3, так как меньше быть не может, Z ведь не больше 9 книг. Также X+Y не больше 12, это думаю понятно почему)
Вот и получилось неравество 3<=X+Y<=12.. Потом составили такую таблицу
X / каким может быть Y/ кол-во варинатов Y
0 - 3-8 - 6
1 - 2-8 - 7
2 - 1-8 - 8
3 - 0-8 - 9
4 - 0-8 - 9
5 - 0-7 - 8
6 - 0-6 - 7
7 - 0-5 - 6
Z становится тоже автоматом.. Т.е. общее кол-во вариантов = 60..
Вроде бы правильно О_о

[VAL]

Elizaveta писал(а):

А вторую мы решили так.. Приняли что кол-во 1 книг - Х, 2 книг - Y, 3 - Z.
Найдем комбинации книг для первого человека, у второго получится автоматом.
Сумма X+Y больше либо равно 3, так как меньше быть не может, Z ведь не больше 9 книг. Также X+Y не больше 12, это думаю понятно почему)
Вот и получилось неравество 3<=X+Y<=12.. Потом составили такую таблицу
X / каким может быть Y/ кол-во варинатов Y
0 - 3-8 - 6
1 - 2-8 - 7
2 - 1-8 - 8
3 - 0-8 - 9
4 - 0-8 - 9
5 - 0-7 - 8
6 - 0-6 - 7
7 - 0-5 - 6
Z становится тоже автоматом.. Т.е. общее кол-во вариантов = 60..
Вроде бы правильно О_о

Все правильно!
Кроме, наезда на преподавателя
Он предлагал вам решить перебором, а вы решили проще - перебором
Можно сначала найти количество сочетаний с повторениями из 3-х по 12 (это 91), а затем устранить лишние сочетания. Но это все равно будет перебор.

Можно ли решить без перебора?
Если заменить числа 7, 8, 9, 12 на 2n-1, 2n, 2n+1, 3n, то легко получить соответствующую формулу. Если же обобщать сильнее: на произвольные сочетания с повторениями и ограничениями на возможное число повторений (разместить k неразличимых предметов, по n пронумерованным ящикам, если i-тый ящик вмещает не более $x_i$ предметов), то здесь хороших общих формул AFAIK не имеется.

[Elizaveta]

Преподователь мне предложил сделать по-другому, просто вертикально расставить сначала первые книги, т.е. столбик от 0 до 7, потом вторые, потом третьи и подбирать..

VAL писал(а):

Можно сначала найти количество сочетаний с повторениями из 3-х по 12 (это 91), а затем устранить лишние сочетания. Но это все равно будет перебор.

Так тоже пробовали, дольше получается..

Цитата:

Можно ли решить без перебора?
Если заменить числа 7, 8, 9, 12 на 2n-1, 2n, 2n+1, 3n, то легко получить соответствующую формулу.

Немного не поняла этот вариант(

[VAL]

Elizaveta писал(а):

VAL писал(а):

Если заменить числа 7, 8, 9, 12 на 2n-1, 2n, 2n+1, 3n, то легко получить соответствующую формулу.

Немного не поняла этот вариант(

Обобщение задачи про книги:
Выбрать 3n книг, имея в распоряжении 2n-1 книг одного вида, 2n книг - другого и 2n+1 - третьего, можно в точности 3n(n+1) способами.

[Elizaveta]

VAL писал(а):

Выбрать 3n книг, имея в распоряжении 2n-1 книг одного вида, 2n книг - другого и 2n+1 - третьего, можно в точности 3n(n+1) способами.

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

[VAL]

Elizaveta писал(а):

VAL писал(а):

Выбрать 3n книг, имея в распоряжении 2n-1 книг одного вида, 2n книг - другого и 2n+1 - третьего, можно в точности 3n(n+1) способами.

Вопрос, бо не поняла, эта формула выведена из уже решенной задачи или по какому то принципу?

Формула получена по тому же принципу, что и ваше решение:

Пусть первая книга взята 0 раз. Тогда вторую можно взять от n-1 до 2n раз. Итого n+2 случаев;
пусть первая книга взята 1 раз. Тогда вторую можно взять от n-2 до 2n раз. Итого n+3 случаев;
. . . . . . . . . . . . . . . . . . . . .
пусть первая книга взята n-1 раз. Тогда вторую можно взять от 0 до 2n раз. Итого 2n+1 случаев.

Пусть первая книга взята n раз. Тогда вторую можно взять от 0 до 2n раз. Итого 2n+1 случаев;
пусть первая книга взята n+1 раз. Тогда вторую можно взять от 0 до 2n-1 раз. Итого 2n случаев;
. . . . . . . . . . . . . . . . . . . . .
пусть первая книга взята 2n-1 раз. Тогда вторую можно взять от 0 до n+1 раз. Итого n+2 случаев.

По формуле суммы арифметической прогрессии (их тут две) получаем 3n(n+1).

[Архипов]

Elizaveta в сообщении #160613 писал(а):

"Есть 7 экземпляров первой вниги, 8 - второй, 9 третьей. Сколькими способами можно разделить их между двумя людьми так, чтобы каждый получил 12 книг?"

Задача не корректна.
1) Способ деления должен быть задан в условии задачи, а количество возможных комбинаций будет зависить от способа деления. Иначе получается путаница со словами.
2) В условии данной задачи, по принципу умолчания, две стопки книг ничем друг от друга не отличаются, то есть у них есть только один признак - общее количество книг в стопке (12). Спрашивается о количестве возможных способов деления 24 экземпляров поровну (по 12) между двумя людьми. Люди, знающие арифметику, делили бы так: посчитали общее количество (7+8+9=24), в уме разделили на 2, получили число 12 (убедились, что условие выполняется), отсчитали 12 книг одному, оставшиеся забрал другой.

" В стопке есть книги: 7 - красного, 8 - синего, 9 - зеленого цвета. Сколько возможных комбинаций из количеств разного цвета (не менее 1 книги любого цвета) книг в одной стопке можно образовать, разложив книги на 2 стопки по 12 книг в каждой?"
Более определенные условия, чем в исходной задаче.

[Elizaveta]

VAL поняла наконец-то, спасибо большое за помощь.


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

Цитата:

" В стопке есть книги: 7 - красного, 8 - синего, 9 - зеленого цвета. Сколько возможных комбинаций из количеств разного цвета (не менее 1 книги любого цвета) книг в одной стопке можно образовать, разложив книги на 2 стопки по 12 книг в каждой?"

Но тогда исчезают такие варианты, как если первому человеку досталось 6 книг первого вида и 6 книг второго, а третьего вообще не досталось..

[Elizaveta]

Решала подобную первой задачу, чего то берут жуткие сомнения, подскажите, пожалуйста, правильно или нет?
"Сколькими способами можно упорядочить множество {1,2,...,n} так, чтобы 1,2,3 не стояли рядом."
Общее кол-во различных сочетаний в множестве n!
Кол-во сочетаний 1,2,3 между собой 3!
Если принять комбинацию 1,2,3 за один объект, всего всех сочетаний в множестве будет (n-2)!.
Т.е, в итоге 2з общего кол-ва вычитаем варианты, когда 1,2,3 рядом:
$n!-(n-2)!*3!
так?

[bot]

Elizaveta в сообщении #162462 писал(а):

Если принять комбинацию 1,2,3 за один объект ...

то скок-скок объектов получится?

Elizaveta в сообщении #162462 писал(а):

... всего всех сочетаний ...

Не сочетаний, а п...

[Elizaveta]

bot писал(а):

то скок-скок объектов получится?

(n-2) конечно, извиняюсь, в тетради так, а набирать задачи после 23 не рекомендуется)
Исправила..

bot писал(а):

Не сочетаний, а п...

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

[plimm]

Народ. Помогите с наипростейшей задачкой.

Имеется 5 видов конвертов без марок и 4 вида марок одного достоинства. Сколькими способами можно выбрать конверт с маркой для посылки письма?

Все , кторые требовались, решил, осталась первая легкая. НЕ понимаю, что требуется от меня в ней.

[Архипов]

plimm в сообщении #162760 писал(а):

Имеется 5 видов конвертов без марок и 4 вида марок одного достоинства. Сколькими способами можно выбрать конверт с маркой для посылки письма?

5 разного цвета конвертов и 4 марки с разными рисунками, сколько вариантов конвертов с маркой можно получить? Берем 4 синих конверта и клеим на них разные марки, берем 4 белых конверта и опять клеим разные марки и т.д...