Задача по комбинаторике

post2225441

Есть 14 наборов вообще говоря не упорядоченных, но, если надо будет, то частичный порядок можно ввести. Каждому набору сопоставляется любое из чисел: 0,1,2,3,4,5,6,7. Необходимо посчитать количество вариантов, при которых среди сопоставленных этим 14-ти наборам чисел присутствует хотя бы один раз каждое из чисел: 0,1,2,3,4,5,6,7.
Первый вариант, который приходит в голову не верен: (C_14^8) * 8! * (8^6). Так как в нем будет много повторяющихся комбинаций. Может как-нибудь их количество можно посчитать и вычесть из (C_14^8) * 8! * (8^6)? Или вообще использовать другую формулу? Возможно надо использовать числа Стирлинга 2-го рода?

Vitaminka

формулу включения исключений надо вспоминать

888julia888

Может так?
способов расставить 8 цифр на 14 позиций с повторами: 8^14
нам не годятся те из них, где в 14 позициях встречаются 7 и менее цифр. подсчитаем их число: 7 цифр на 14 позиций с повторами: 7^14, при этом эти 7 цифр из 8 можно выбрать 8-ю способами.
Получается: (8^14) - 8 * (7^14).

elektronik

А как же те, что меньше 7?
Там многова-то слагаемых получается...

888julia888

^14 - это все те, где 7 или менее разных цифр на 14 позициях (при размещении с повторениями семи разных цифр по 14 нумерованным позициям) !

post2225441

ты не прав. это тут непричем

post2225441

ты тоже не прав
идея хорошая, НО!
во-первых, твой вариант много меньше нуля
во-вторых, а почему он < 0? да потому что ты вычитаешь очень много комбинаций по несколько раз (это там где ты умножаешь на 8-мь)

888julia888

Да, правда (

post2225441

ещё у кого-нибудь варианты будут?

post2225441

кстати, забыл сказать
если точное число определить не можете, то попробуйте хотя бы найти оценку снизу
я нашел оценку снизу = 10^8
если кто найдет более высокую оценку, буду очень благодарен

888julia888

вроде придумал рекуррентное соотношение f(n) = n^14 - sum(i=1... n-1C_n^i * f(i где f(n) при n=8 - то что нужно в условии задачи. "Прямую" формулу придумать не могу, на компе можно посчитать - 8^14 в long влезет скорее всего, ну или приближенно для double

post2225441

да, формула верна
только вот как строго доказать правильность? интуитивно-то понятно вроде.
по индукции что ли?
но всё равно спасибо
сейчас посчитаю сколько там получается

halithh

Здесь действительно нужна формула включений-исключений, причем
(8^14) - 8 * (7^14).
- ее первые два слагаемых. Ошибка заключена в следующем: если среди 14 позиций встречается ровно 6 различных чисел, то каждая такая комбинация в приведенной формуле вычитается по 2 раза вместо 1.
Если начинать сначала, то рассуждения такие: обозачим через A множество всех цепочек длины 14, и пусть A_i - множество всех цепочек, не содержащих число i. Тогда нужно найти | П(A\A_i) |, где П - пересечение. Раскрыв скобки, получаем | П(A\A_i) | = | A | - |A_0| -...-|A_7| + | A_0ПA1| + | A_0ПA_2| + ... + | A_6ПA_7| - | A_0ПA_1ПA_2 | -..- | A_5ПA_6ПA_7| +... Тк мощность пересечения нескольких A_i завистит только от числа пересекаемых множеств (а не от конкретных индексов то формула упрощается: | П(A\A_i) | = | A | - |A_0|*C_8^1 + | A_0ПA1|*C_8^2 - | A_0ПA_1ПA_2|*C_8^3 + ...+ | A_0П..ПA_7|*С_8^8 = \sum_i ( (-1)^i*(8-i)^14*C_8^i )

post2225441

да действительно, способ тоже верный
умка сорри, ты был прав
посчитал результаты в обоих вариантах(pаrovoz u и они оказались равны друг другу , что доказывает правильность обоих способов
получается около 800 миллиардов !
что составляет пятую часть от всех наборов !
Ну вобщем, задача исчерпана. Всем спасибо!
Оставить комментарий
Имя или ник:
Комментарий: