комбинаторика

nmn · Сообщение **nmn** » 25 апр 2009, 11:33

есть набор чисел от 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 не входиткак?

Rimescald · Сообщение **Rimescald** » 25 апр 2009, 20:26

Да это же сочетания.

$C_n^m=\frac {n!} {m!(n-m)!}$

YURI · Сообщение **YURI** » 26 апр 2009, 08:55

Rimescald писал(а):Source of the post
Да это же сочетания.

$C_n^m=\frac {n!} {m!(n-m)!}$

нет не они. Ответ $$m^n$$

.

jarik · Сообщение **jarik** » 26 апр 2009, 08:57

nmn писал(а):Source of the post нужно получить все упорядоченные перестановки c повторениями на m позициях

nmn писал(а):Source of the post 1,2,7.... входит ; 2,1,7, 2,7,1 не входит

Вот это что то не доходит, это как?

Rimescald · Сообщение **Rimescald** » 26 апр 2009, 09:02

YURI писал(а):Source of the post
Rimescald писал(а):Source of the post
Да это же сочетания.

$C_n^m=\frac {n!} {m!(n-m)!}$

нет не они. Ответ .

Тогда это будет задача разбрасывания n-шаров по m-лункам. И комбинации вроде 2,1,7 и 2,7,1 непременно войдут.

Посмотрите условие еще раз. m=3 и у нас сочетания по три дальше описываются автором.

kobras · Сообщение **kobras** » 26 апр 2009, 13:42

Ну насколько я понял если елементы повторяються то последовательность типа 1 1 1 подходит?
Тогда можна думать так. Пусть обозначим через $B_{m}^{n}$ то что ищем. Если мы на первую позицию ставим 1, то в следующех позициях мы снова можем использовать все числа от 1 до n, если ставим двойку то можем использовать числа от 2 к n и так далее. Тойсть получаем формулу:
$B_{m}^{n}=\sum_{i=1}^{n}{B_{m-1}^{i}}$ , распишем сумму:
$B_{m}^{n}=\sum_{i=1}^{n}{B_{m-1}^{i}}=\sum_{i=1}^{n-1}{B_{m-1}^{i}}+B_{m-1}^{n}=B_{m}^{n-1}+B_{m-1}^{n}$
дальше думаю как свести это к замкнутому выражению.

Hottabych · Сообщение **Hottabych** » 26 апр 2009, 13:47

YURI писал(а):Source of the post
нет не они. Ответ .

A Вы не перепутали. Может все таки $$n^m$$

?

Rimescald · Сообщение **Rimescald** » 26 апр 2009, 13:57

Перечитал условие, да, действительно речь не o том.
Верный ответ:
$$m^n$$

Ho тогда у меня возникает вопрос: a что, если мы размещаем по m позициям не числа, a просто, скажем, шарики. И нам не важно, какой шарик в какой лунке находится, a важно только в какой лунке сколько шариков. Как тогда будет выглядеть формула?

YURI · Сообщение **YURI** » 26 апр 2009, 15:31

Rimescald писал(а):Source of the post
Перечитал условие, да, действительно речь не o том.
Верный ответ:

Ho тогда у меня возникает вопрос: a что, если мы размещаем по m позициям не числа, a просто, скажем, шарики. И нам не важно, какой шарик в какой лунке находится, a важно только в какой лунке сколько шариков. Как тогда будет выглядеть формула?

Да, моя формула неверна (прочитал условие

). Автору нужны только перестановки, где числа не убывают (слева направо).

kobras · Сообщение **kobras** » 26 апр 2009, 19:36

Hottabych писал(а):Source of the post
YURI писал(а):Source of the post
нет не они. Ответ .

A Вы не перепутали. Может все таки ?

A можете мне обяснить эти формулы?
K примеру m=2 n=2. И по одной и по другой формуле будет 4. Я нашел только 3: (1 1), (1 2), (2 2). Или я не правильно условия понял?

PS Кстати все таки получилось вывести формулу: $B_{n}^{m}=\frac {(m+n-1)!}{m!(n-1)!}$

yourdomain.com