 |
|
Модераторы: Poseidon |
 
|
|
[комбинаторика] задача про бусы 
| SoWa |
|
|||
 Харекришна  Профиль Группа: Комодератор Сообщений: 2422 Регистрация: 18.10.2004 Репутация: 3 Всего: 74 |
Задача: Сколькими способами можно разрезать ожерелье из 30 бусин на 8 частей. Резать только между бусинами. Ожерелье изначально в виде кольца.
-------------------- Всем добра  |
|||
|
||||
Загрузка ...
| JAPH |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 312 Регистрация: 8.1.2007 Где: Ленобласть Репутация: 12 Всего: 23 |
30 соединений между бусами. На 8 частей - 8 разрезов. Итого C из 30 по 8.
-------------------- Что непонятно - спрашиваем |
|||
|
||||
| SoWa |
|
|||
|
Харекришна Профиль Группа: Комодератор Сообщений: 2422 Регистрация: 18.10.2004 Репутация: 3 Всего: 74 |
хех. Если бы так просто.
Что есть соетания. Это количество способов выбрать из Эн элементного множества Эм элементные подмножества. Бусины все разные, и все связаны. примерно вот ожерелье: -а-б-в-г-д-е-ё-ж-з-и-й-к-л-м-н-о-п-р-с-т-у-ф-х-ц-ч-ш-щ-ъ-ы-ь- Вот это в кружок. А по сочетаниям наберу подмножество п-е-ь не то. -------------------- Всем добра |
|||
|
||||
| JAPH |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 312 Регистрация: 8.1.2007 Где: Ленобласть Репутация: 12 Всего: 23 |
Это сообщение отредактировал(а) JAPH - 4.1.2008, 21:24 -------------------- Что непонятно - спрашиваем |
|||
|
||||
| SoWa |
|
|||
|
Харекришна Профиль Группа: Комодератор Сообщений: 2422 Регистрация: 18.10.2004 Репутация: 3 Всего: 74 |
Ничего не понял. какие соединения выбрали, какие получили?..
-------------------- Всем добра |
|||
|
||||
| JAPH |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 312 Регистрация: 8.1.2007 Где: Ленобласть Репутация: 12 Всего: 23 |
Насколько я представляю себе процесс, некто хочет разрезать ожерелье на 8 кусочков. Для этого придётся сделать 8 разрезов. Все разрезы можно делать только между бусинами, которые соединены чем-то-там. Соединений тридцать. Так что надо выбрать 8 из 30 соединений, которые будем разрезать.
Другое дело, если бусы одинаковые. Тогда такое решение точно неправильно. Аналогия с разложениями и разбиениями натуральных чисел на слагаемые. -------------------- Что непонятно - спрашиваем |
|||
|
||||
| SoWa |
|
|||
|
Харекришна Профиль Группа: Комодератор Сообщений: 2422 Регистрация: 18.10.2004 Репутация: 3 Всего: 74 |
Я предполагал так:
вырежем первый кусочек длиной 23 бусины. Способов это сделать 30. Оставшийся кусок длины 7 надо порезать на 7 кусков. Способ один. Вырежем первый кусочек длины 22 бусины. Останется кусочек 8 бусин разрезать на 7 частей. Далее перемножим 30 на количество вариантов разрезать оставшийся кусочек. А сколько их? -------------------- Всем добра |
|||
|
||||
| JAPH |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 312 Регистрация: 8.1.2007 Где: Ленобласть Репутация: 12 Всего: 23 |
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 |
|
|||
|
Харекришна Профиль Группа: Комодератор Сообщений: 2422 Регистрация: 18.10.2004 Репутация: 3 Всего: 74 |
Можно об этом поподробнее. Почему C(6,9)? Я думаю 7, так как на 7 частей. И почему в конце С(6,28) 28 взяться неоткуда. Это сообщение отредактировал(а) SoWa - 5.1.2008, 19:56 -------------------- Всем добра |
|||
|
||||
| JAPH |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 312 Регистрация: 8.1.2007 Где: Ленобласть Репутация: 12 Всего: 23 |
Если сначала вырезать кусочек длины 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 |
|
|||
|
Харекришна Профиль Группа: Комодератор Сообщений: 2422 Регистрация: 18.10.2004 Репутация: 3 Всего: 74 |
Можешь сказать, почему? Мне надо все знать подробно, чтоб сдать -------------------- Всем добра |
|||
|
||||
| JAPH |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 312 Регистрация: 8.1.2007 Где: Ленобласть Репутация: 12 Всего: 23 |
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 |
|
||||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 17 Всего: 454 |
С(30,8) = 30! / (8! * (30 - 8)!) = 5852925 способов. -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
||||
|
|||||
| SoWa |
|
|||
|
Харекришна Профиль Группа: Комодератор Сообщений: 2422 Регистрация: 18.10.2004 Репутация: 3 Всего: 74 |
JAPH получил результат 8*С(8,30)
Akina - просто С(8,30) И как быть. Почему Сочетания я понял, за это спасибо -------------------- Всем добра |
|||
|
||||
| JAPH |
|
||||||
|
Опытный Профиль Группа: Участник Сообщений: 312 Регистрация: 8.1.2007 Где: Ленобласть Репутация: 12 Всего: 23 |
-------------------- Что непонятно - спрашиваем |
||||||
|
|||||||
|
|
| Правила форума "Центр помощи" | |
|
|
ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Более подробно с правилами данного раздела Вы можете ознакомится в этой теме. Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman |
| 1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Центр помощи | Следующая тема » |
[ Время генерации скрипта: 0.0821 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |