Подскажите раздел комбинаторики

[kthxbye]

Имеем некоторое количество коробок (число известно). В каждой коробке лежит по три фигуры: пирамидка, куб и шар. Каждая фигура окрашена в определенный цвет (число цветов известно). Содержимое каждой коробки известно, т.е. можно подсчитать сколько раз каждая фигура определенного цвета сочетается с оставшимися фигурами определенного цвета. Мы выбираем $n$ коробок так, что, вытащив после каждого выбора все предметы на стол, у нас не встречались одинаковые фигуры с одинаковыми цветами (одинаковые фигуры с разными цветами и разные фигуры с одинаковыми цветами соот.-но можно). Как подсчитать количество таких выборов при разных $n$? Какой раздел комбинаторики рассматривает подобные вопросы?

[arseniiv]

[Удалил предыдущую версию поста.]

Иначе говоря, у вас есть множество троек $F\subset C^3$ цветов из $C$, и вас интересует количество подмножеств $F'\in F$, не содержащих троек, какие-либо соответствующие (первые, вторые, третьи) компоненты которых совпадают. Так?

-- Чт июл 27, 2017 22:06:22 --

Можно попробовать рассмотреть вообще всё $C^3$, а после повыкидывать подмножества, которые не входят в $F$.

[Vince Diesel]

Формулы включения-исключения не хватит?

[kthxbye]

arseniiv, не совсем не понял вашу формулировку. Приведу наглядный пример:



Здесь условие несколько дополнено, т.е. цветов всего 7, но не обязательно, чтобы каждая фигура была окрашена в каждый цвет как минимум один раз (в нашем случае у пирамидки всего 6 различных, у куба 5, у шара 7). Случай $n=1$ тривиален. Для $n=2$ надо уже рассматривать каждый вариант отдельно, например для первого набора это $10-1-(3-1)-(4-1)-(1-1)=4$. Но может быть и так, что элементы в коробках, которые надо исключить, совпадают (4 и 8 коробка, и кубик, и шар одинаковых цветов).

Можно как-то упростить эти рутинные вычисления? Каждый цвет можно обозначить уникальной цифрой/числом, получаем две матрицы с числами, применяем определенное правило и.. вжух - мгновенно получаем количество выборок! Есть что-нибудь такое? Где искать?

Vince Diesel, не уверен, но утверждать не могу.

[Vince Diesel]

Что-то сомнительно, что есть хорошая формула, ибо все зависит от содержимого всех коробок. Вторая матрица непонятно, чем помочь может. Это практическая задача? Насколько могут быть велики количество коробок и $n$?

[arseniiv]

kthxbye в сообщении #1236554 писал(а):

совсем не понял вашу формулировку

Ну вот посмотрите на вашу таблицу. Порядок коробок нам не нужен, так что она задаёт некоторое множество троек значений (цвет пирамидки, цвет кубика, цвет шара). То есть множество троек цветов. То есть некоторое подмножество $F\subset C^3$, где $C$ — множество цветов. Нельзя одновременно опустошать две коробки, в которых есть одинаковые вместе с цветом фигуры — это значит, что для троек $(a_1,b_1,c_1), (a_2,b_2,c_2)$, представляющих эти коробки как указано выше, выполняется $a_1 = a_2$ (пирамидки одинакового цвета), $b_1 = b_2$ (кубики) или $c_1 = c_2$ (шары). Чтобы две коробки были «совместимы», надо $a_1\ne a_2\wedge b_1\ne b_2\wedge c_1\ne c_2$, и чтобы целое множество $F'\subset F$ коробок было совместимо, надо, чтобы все пары его элементов были совместимы. Это я и написал.

Присоединяюсь к Vince Diesel, что назначение второй таблицы совершенно неясно. И она всё равно вычисляется по первой.

kthxbye в сообщении #1236554 писал(а):

и.. вжух - мгновенно получаем количество выборок!

Ну программу переборную напишите тогда. Это вполне вжух, если коробок мало, но если их много, наверняка ничто не поможет.

-- Сб июл 29, 2017 18:51:29 --

kthxbye в сообщении #1236554 писал(а):

Каждый цвет можно обозначить уникальной цифрой/числом

Вообще, кстати, мнение, что стоит только заменить элементы предметной области числами, и всё сразу решится — ошибочное. В данном случае, например, природа элементов множества $C$ вообще не важна — и даже, кстати, конечность этого множества совершенно не обязательна, пока число коробок конечно.