| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [комбинаторика] задача про бусы |
| Автор: SoWa 4.1.2008, 20:51 |
| Задача: Сколькими способами можно разрезать ожерелье из 30 бусин на 8 частей. Резать только между бусинами. Ожерелье изначально в виде кольца. |
| Автор: JAPH 4.1.2008, 20:55 |
| 30 соединений между бусами. На 8 частей - 8 разрезов. Итого C из 30 по 8. |
| Автор: SoWa 4.1.2008, 21:14 |
| хех. Если бы так просто. Что есть соетания. Это количество способов выбрать из Эн элементного множества Эм элементные подмножества. Бусины все разные, и все связаны. примерно вот ожерелье: -а-б-в-г-д-е-ё-ж-з-и-й-к-л-м-н-о-п-р-с-т-у-ф-х-ц-ч-ш-щ-ъ-ы-ь- Вот это в кружок. А по сочетаниям наберу подмножество п-е-ь не то. |
| Автор: JAPH 4.1.2008, 21:23 | ||
|
| Автор: SoWa 4.1.2008, 23:40 |
| Ничего не понял. какие соединения выбрали, какие получили?.. |
| Автор: JAPH 5.1.2008, 00:12 |
| Насколько я представляю себе процесс, некто хочет разрезать ожерелье на 8 кусочков. Для этого придётся сделать 8 разрезов. Все разрезы можно делать только между бусинами, которые соединены чем-то-там. Соединений тридцать. Так что надо выбрать 8 из 30 соединений, которые будем разрезать. Другое дело, если бусы одинаковые. Тогда такое решение точно неправильно. Аналогия с разложениями и разбиениями натуральных чисел на слагаемые. |
| Автор: SoWa 5.1.2008, 14:03 |
| Я предполагал так: вырежем первый кусочек длиной 23 бусины. Способов это сделать 30. Оставшийся кусок длины 7 надо порезать на 7 кусков. Способ один. Вырежем первый кусочек длины 22 бусины. Останется кусочек 8 бусин разрезать на 7 частей. Далее перемножим 30 на количество вариантов разрезать оставшийся кусочек. А сколько их? |
| Автор: JAPH 5.1.2008, 17:43 |
| 8 бусин на 7 частей - 7 способов: 2+1+1+1+1+1+1,1+2+1+1+1+1+1,...,1+1+1+1+1+1+2. ну, хорошо, 30 + 30*C(6,7) + 30 * C(6,8) + ... + 30 * C(6,28)=30*C(7,8) + 30 *C(6,8) + 30 * C(6,9) + ... + 30*C(6,28) = 30*C(7,29) = 30 * 29! / (7! 22!) = 30! / 7! 22! = 8 * C(8,30). Каждый способ разрезания учитывается восьмикратно. Ведь вырезать можно в разном порядке. Можно сначала 23 бусины, а потом порезать оставшиеся 1+1+1+1+1+1+1, а можно сначала 1 бусину, потом порезав 23+1+1+1+1+1+1 - результат тот же. |
| Автор: SoWa 5.1.2008, 19:27 | ||
Можно об этом поподробнее. Почему C(6,9)? Я думаю 7, так как на 7 частей. И почему в конце С(6,28) 28 взяться неоткуда. |
| Автор: JAPH 5.1.2008, 21:41 |
| Если сначала вырезать кусочек длины k бусин, останется разрезать кусочек длины 30-k бусин на 7 частей. Способов это сделать C(6, 29-k). Минимально допустимое k есть 1 => последнее слагаемое C(6, 28). Почему способов C(6,29-k). Задача аналогична задаче о разложении числа 30-k на 7 слагаемых. А число разложений числа p на q слагаемых есть C(q-1, p-1). |
| Автор: SoWa 5.1.2008, 21:53 | ||
Можешь сказать, почему? Мне надо все знать подробно, чтоб сдать  |
| Автор: JAPH 5.1.2008, 23:25 |
| p=1+1+1+...+1, количество единиц суть p. Надо расставить скобки так, чтоб собрать единицы в группы, образующие p слагаемых. На конкретном примере: p=5, q=3: p=1+1+1+1+1=(1+1+1)+(1)+(1)=(1+1)+(1+1)+(1)=(1+1)+(1)+(1+1)= =(1)+(1+1)+(1+1)=(1)+(1+1+1)+(1)=(1)+(1)+(1+1+1) получится q скобок, соединённых q-1 плюсами. Расстановку скобок можно проводить, отталкиваясь от этих плюсов, т.е. сначала выбрать q-1 плюс, которые будут соединять скобки, а потом нарисовать скобки. Способов выбрать q-1 плюс из p-1 плюсов между единицами - C(q-1,p-1). |
| Автор: Akina 6.1.2008, 00:07 | ||||
С(30,8) = 30! / (8! * (30 - 8)!) = 5852925 способов. |
| Автор: SoWa 6.1.2008, 10:43 |
| JAPH получил результат 8*С(8,30) Akina - просто С(8,30) И как быть. Почему Сочетания я понял, за это спасибо |
| Автор: JAPH 6.1.2008, 13:16 | ||||||
|
| Автор: H5N1 6.1.2008, 13:24 |
| Мде...Простая задачка, а стока шума |
| Автор: SoWa 6.1.2008, 13:49 |
| Ты хто?! Все, плюсы. Спасибо! |
