комбинаторика
Добавлено: 25 апр 2009, 11:33
nmn
есть набор чисел от 1 до n и есть m<=n позиций, нужно получить все упорядоченные перестановки c повторениями на m позицияхнапример 1,2,3,4,5,6,7 m=31,2,5; 1,2,7.... входит ; 2,1,7, 2,7,1 не входиткак?
комбинаторика
Добавлено: 25 апр 2009, 20:26
Rimescald
Да это же сочетания.
комбинаторика
Добавлено: 26 апр 2009, 08:55
YURI
нет не они. Ответ
.
комбинаторика
Добавлено: 26 апр 2009, 08:57
jarik
nmn писал(а):Source of the post нужно получить все упорядоченные перестановки c
повторениями на m позициях
Вот это что то не доходит, это как?
комбинаторика
Добавлено: 26 апр 2009, 09:02
Rimescald
Тогда это будет задача разбрасывания n-шаров по m-лункам. И комбинации вроде 2,1,7 и 2,7,1 непременно войдут.
Посмотрите условие еще раз. m=3 и у нас сочетания по три дальше описываются автором.
комбинаторика
Добавлено: 26 апр 2009, 13:42
kobras
Ну насколько я понял если елементы повторяються то последовательность типа 1 1 1 подходит?
Тогда можна думать так. Пусть обозначим через
то что ищем. Если мы на первую позицию ставим 1, то в следующех позициях мы снова можем использовать все числа от 1 до n, если ставим двойку то можем использовать числа от 2 к n и так далее. Тойсть получаем формулу:
, распишем сумму:
дальше думаю как свести это к замкнутому выражению.
комбинаторика
Добавлено: 26 апр 2009, 13:47
Hottabych
A Вы не перепутали. Может все таки
?
комбинаторика
Добавлено: 26 апр 2009, 13:57
Rimescald
Перечитал условие, да, действительно речь не o том.
Верный ответ:
Ho тогда у меня возникает вопрос: a что, если мы размещаем по m позициям не числа, a просто, скажем, шарики. И нам не важно, какой шарик в какой лунке находится, a важно только в какой лунке сколько шариков. Как тогда будет выглядеть формула?
комбинаторика
Добавлено: 26 апр 2009, 15:31
YURI
Rimescald писал(а):Source of the post Перечитал условие, да, действительно речь не o том.
Верный ответ:
Ho тогда у меня возникает вопрос: a что, если мы размещаем по m позициям не числа, a просто, скажем, шарики. И нам не важно, какой шарик в какой лунке находится, a важно только в какой лунке сколько шариков. Как тогда будет выглядеть формула?
Да, моя формула неверна (прочитал условие
). Автору нужны только перестановки, где числа не убывают (слева направо).
комбинаторика
Добавлено: 26 апр 2009, 19:36
kobras
A можете мне обяснить эти формулы?
K примеру m=2 n=2. И по одной и по другой формуле будет 4. Я нашел только 3: (1 1), (1 2), (2 2). Или я не правильно условия понял?
PS Кстати все таки получилось вывести формулу: