Как посчитать количество перестановок?

Question

[alex_ak1]

Есть t,u и v (количество единиц, двоек и троек). Из них составляем число длиной (t+u+v цифр).
Какое количество различных чисел можно получить?
Я правильно понимаю, что это число будет равно с( t, t+u+v ) * с( u, u+v )?

Где C(n,m) - количество перестановок n из m

Comments

[Даниил Игоревич]

C - символ сочетаний

[alex_ak1]

Даниил Ораин: Я имел в виде с(n,m) = n! / (n-m)!

[Даниил Игоревич]

alex_ak1: это размещения, их принято обозначать буквой A

Answer 1

[Алексей]

Посмотрите тут - umk.portal.kemsu.ru/uch-mathematics/papers/posobie...
Мне кажется "Число перестановок c повторениями" это ваш случай.

Там же ниже есть пример с шахматными фигурами вместо цифр.

Comments

[alex_ak1]

Спасибо, работает.
А еще не подскажете, как тут избежать деления. В задаче, которую я решаю, запросто могут выползти вычисления вида 1000! / ( 500! * 100! ) к примеру. Если бы был один факториал в знаменателе, то понятно,что просто считаем верхний факториал не от 1, а до знаменатель+1, а тут 2 (а то и 3) факториала.

[Алексей]

Так сходу не скажу, у вас чисто математика или программу пишите?
Если программу, то можно попробовать создать два массива - в первом множители 2...1000, во втором 2..500, 2..100 и попробовать сократить числитель. Перед этим лучше сократить самый большой факториал. В любом случае ответ будет "длинный", не только вычисления.

[alex_ak1]

Алексей: Я уже нагуглил ссылку на факториал 1000 - там страница цифр получилась :)

Answer 2

[Даниил Игоревич]

P = (t + k + v)!/(t! * k! * v!)
Например, возьмём t = 1, k = 1, v = 2:
P = (1 + 1 + 2)!/(1! * 1! * 2!) = 4!/2 = 1 * 2 * 3 * 4/ 2 = 24/2 = 12 способов перестановок -- 12 различных чисел можно получить.
1) 1233
2) 2133
3) 3123
4) 3132
5) 2313
6) 2331
7) 3312
8) 3321
9) 1323
10) 1332
11) 3213
12) 3231

Comments

[alex_ak1]

Спасибо, работает.
А еще не подскажете, как тут избежать деления. В задаче, которую я решаю, запросто могут выползти вычисления вида 1000! / ( 500! * 100! ) к примеру. Если бы был один факториал в знаменателе, то понятно,что просто считаем верхний факториал не от 1, а до знаменатель+1, а тут 2 (а то и 3) факториала.

[Даниил Игоревич]

alex_ak1: не "до знаменатель+1", а от знаменатель+1. Если в числителе 1000!, а в знаменателе 500!, то считаем в числителе от 501. Если очень много, то сокращайте знаменатели с числителем. Кстати, отметьте решения.

[alex_ak1]

Даниил Ораин: Ну да, все верно. Но как сделать несколько факториалов в знаменателе?