2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Комбинаторика
Сообщение22.08.2014, 21:14 
Аватара пользователя
А тупо машинным перебором? Комп не так уж долго думать будет.

 
 
 
 Re: Комбинаторика
Сообщение22.08.2014, 21:27 
Aritaborian в сообщении #898503 писал(а):
А тупо машинным перебором? Комп не так уж долго думать будет.

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

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

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

 
 
 
 Re: Комбинаторика
Сообщение23.08.2014, 08:34 
nikita111 в сообщении #898501 писал(а):
если последовательности образованные перестановкой считать 1 раз(то есть 123412,121234,112234 и т.д. считать одной и той же последовательностью).
Если есть такое условие, почему сразу не условиться, что все повторяющиеся цифры будут стоять, например, на первых местах? Сколько вообще шестизначных чисел с указанным отождествлением существует? А если посчитать то, что нам не нужно: "более 4 повторяющихся цифр", т.е. 5 (20 возможностей) или 6 (последнее вообще просто --- их всего 5)? А потом из общего количества выкинуть эти случаи?

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

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

 
 
 
 Re: Комбинаторика
Сообщение23.08.2014, 16:24 
Начать с рекуррентных соотношений в любом случае стоит. Получится из них что-то лучше или нет — другой вопрос. :lol:

Пусть мощность алфавита $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}}.$$

 
 
 
 Re: Комбинаторика
Сообщение26.08.2014, 12:10 
arseniiv в сообщении #898789 писал(а):
Начать с рекуррентных соотношений в любом случае стоит. Получится из них что-то лучше или нет — другой вопрос. :lol:

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

(Оффтоп)

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

 
 
 
 Re: Комбинаторика
Сообщение26.08.2014, 12:15 
Аватара пользователя

(Оффтоп)

nikita111 в сообщении #900150 писал(а):
на этом форуме есть кнопка "Поблагодарить автора"?
Нет такой кнопки. Тут введение лишних наворотов, как правило, не приветствуется. Ни мэйнтейнером сайта, ни большинством участников.

 
 
 
 Re: Комбинаторика
Сообщение26.08.2014, 14:41 

(Оффтоп)

nikita111 в сообщении #900150 писал(а):
Ещё вопрос не совсем в тему:на этом форуме есть кнопка "Поблагодарить автора"? Я что-то не нашёл её.
Есть кнопка «Пожаловаться на сообщение». Правда, не знаю, оценят ли модераторы метафору такого её использования. :lol:

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

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group