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

[nikita111]

   Здравствуйте, прошу помочь решить одну задачу. Сразу скажу, что она не из учебника, а возникла при подсчёте числа комбинаций в одной игре. Я переформулировал её как задачу о числе последовательностей, чтобы было проще понять суть задачи. Вот её условие:
   Из цифр от 1 до 5 составляется последовательность длинной 6.При этом в ней не может быть более 4 одинаковых цифр. Сколько существует таких последовательностей, если последовательности образованные перестановкой считать 1 раз(то есть 123412,121234,112234 и т.д. считать одной и той же последовательностью).Также нужно решить эту задачу если взяты цифры от 1 до 9 и длина последовательности 12.
   Я пытался найти решение, но последнее условие не даёт решить задачу, используя известные мне комбинаторные формулы: правило произведения, формулы сочетаний и размещений и т.д.
   Заранее спасибо за помощь!

[Aritaborian]

А тупо машинным перебором? Комп не так уж долго думать будет.

[nikita111]

Aritaborian в сообщении #898503 писал(а):

А тупо машинным перебором? Комп не так уж долго думать будет.

Я думал об этом,но прежде чем писать программу хочу узнать есть-ли у этой задачи математическое решение.

[gris]

Таких дурацких задач много в задачниках по теории вероятностей. Можно слегка переформулировать условие, чтобы убежать от путаницы с перестановками. Например, есть 5 урн с помеченными цифрами шарами. В каждой урне по 4 шара. Найти число способов набрать из урн 6 шаров. Из первой можем набрать от 0 до 4. Ну и так далее. То есть составляем из цифр от 0 до 4 пятизначные чила вида 42000, 41100 такие, что сумма цифр равна 6. Может быть, получится?
То же и с 12-ю картами, пардон за навязчивую аналогию. Хотя у карт же масти, но если учитывать только названия, то ровно то же и виднеется.
То есть определяем число 9-ти значных чисел (с учётом ведущих нулей) из цифр от нуля до четырёх и с их суммой, равной 12.

Если подумать реккурентно, то симпатишный алгоритм получается. Даже для Эксели как раз подойдёт.

[OlgaD]

nikita111 в сообщении #898501 писал(а):

если последовательности образованные перестановкой считать 1 раз(то есть 123412,121234,112234 и т.д. считать одной и той же последовательностью).

Если есть такое условие, почему сразу не условиться, что все повторяющиеся цифры будут стоять, например, на первых местах? Сколько вообще шестизначных чисел с указанным отождествлением существует? А если посчитать то, что нам не нужно: "более 4 повторяющихся цифр", т.е. 5 (20 возможностей) или 6 (последнее вообще просто --- их всего 5)? А потом из общего количества выкинуть эти случаи?

[nikita111]

OlgaD в сообщении #898642 писал(а):

Если есть такое условие, почему сразу не условиться, что все повторяющиеся цифры будут стоять, например, на первых местах? Сколько вообще шестизначных чисел с указанным отождествлением существует? А если посчитать то, что нам не нужно: "более 4 повторяющихся цифр", т.е. 5 (20 возможностей) или 6 (последнее вообще просто --- их всего 5)? А потом из общего количества выкинуть эти случаи?

Интересная мысль.Таким способом можно решить первую часть задачи,но как быть со второй частью(цифры от 1 до 9 и длина последовательности 12)? Там уже не получиться так легко 'выкинуть лишние случаи'.

[arseniiv]

Начать с рекуррентных соотношений в любом случае стоит. Получится из них что-то лучше или нет — другой вопрос.

Пусть мощность алфавита $N$ (число цифр на выбор), и интересующее число мультимножеств из $n$ цифр с не более чем $r$ повторами каждой зовётся $a(N,n,r)$. Теперь надо угадать, какие соотношения дадут пользу. Возьмём, например, алфавит из $N+1$ цифры, предположив, что для менших мы всё знаем. Мы можем добавить к известным последовательностям из $N$ цифр $0..r$ новой цифры и получить последовательности из $N+1$. Если поинтересоваться новыми последовательностями одинаковой длины, получится

$$a(N+1,n,r) = a(N,n,r) + a(N,n-1,r) + \ldots + a(N,n-r,r).$$

Если мы знаем $a(1,n,r)$, этого соотношения хватит на вычисление всех $a$. Ну а $a(1,n,r)$ — это число последовательностей мультимножеств из одной единицы длины $n$, в которых не больше $r$ единиц. Таких существует ровно одна, если $0\leqslant n\leqslant r$, и ноль в противном случае, что можно кратко записать как $a(1,n,r) = [0\leqslant n\leqslant r]$. Всё, уже можно считать:

$$\begin{array}{c|ccccc} n & N=1 & N=2 & N=3 & N=4 & N=5 \\ \hline \vdots & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 2 & 3 & 4 & 5 \\ 2 & 1 & 3 & 6 & 10 & 15 \\ 3 & 1 & 4 & 10 & 20 & 35 \\ 4 & 1 & 5 & 15 & 35 & 70 \\ 5 & 0 & 4 & 18 & 52 & 121 \\ 6 & 0 & 3 & 19 & 68 & \mathbf{185} \end{array}$$

Если заметить, что $a(N+1,n,r) = a(N+1,n-1,r) + a(N,n,r) - a(N,n-r-1,r)$, вычисления даже немного упростятся.

А теперь, имея рекуррентные соотношения, можно поискать производящую функцию (видно, что можно брать её от двух переменных, зафиксировав $r$) и замкнутое выражение для $a$ через неё.

Проверьте кто-нибудь мои цифорки.

-- Сб авг 23, 2014 19:58:47 --

Для производящей функции $A_r(t,u) = \sum_{N,n=0}^\infty a(N,n,r)t^Nu^n$ получим

$$A_r = \frac1{1 - u - t + tu^{r+1}}.$$

[nikita111]

arseniiv в сообщении #898789 писал(а):

Начать с рекуррентных соотношений в любом случае стоит. Получится из них что-то лучше или нет — другой вопрос.

Большое спасибо за подробное решение.К сожалению плохо разбираюсь в производящих функциях,но идею понял. Рекуррентные соотношения действительно сильно помогли

(Оффтоп)

Ещё вопрос не совсем в тему:на этом форуме есть кнопка "Поблагодарить автора"? Я что-то не нашёл её.

[Aritaborian]

(Оффтоп)

nikita111 в сообщении #900150 писал(а):

на этом форуме есть кнопка "Поблагодарить автора"?

Нет такой кнопки. Тут введение лишних наворотов, как правило, не приветствуется. Ни мэйнтейнером сайта, ни большинством участников.

[arseniiv]

(Оффтоп)

nikita111 в сообщении #900150 писал(а):

Ещё вопрос не совсем в тему:на этом форуме есть кнопка "Поблагодарить автора"? Я что-то не нашёл её.

Есть кнопка «Пожаловаться на сообщение». Правда, не знаю, оценят ли модераторы метафору такого её использования.

Найденные производящие функции, конечно, просто переносят проблему из одной области в другую (где она другими методами может решиться, а может и нет, и вот тут как раз случай не очень, вроде). Рекуррентное нахождение чисел можно ещё немного оптимизировать, заметив, что $a(N,n,r)$ при $n\leqslant r$ совпадают с… (или нельзя оптимизировать, но что-то, вроде, даст всё-таки).