комбинаторика: разложить предметы по ящикам, без пропусков

[vadim55]

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

[PAV]

Сначала решите задачу без доп. условия, что в каждом ящике должен быть хотя бы один предмет. Для этого принцип включения-исключения не нужен. Он понадобится, когда будете разбираться с этими доп. условиями.

А сам принцип включения-исключения, собственно, Вы знаете?

[vadim55]

разместить все предметы между ящиками без дополнительного условия

$$ U = D(4,9)*D(4,12) $$

сам принцип включения-исключения:

$$ |A1 \cup A2| = |A1| + |A2| - |A1 \cap A2| $$

как мне двигаться дальше?

[PAV]

Под $D$ что Вы понимаете, уточните, пожалуйста. Чтобы быть уверенным, что Вы не ошиблись.

Также Вам понадобится обобщение принципа включения-исключения на большее число множеств.

А теперь так. Мы посчитали число способов разместить предметы по не более чем четырем ящикам. Из этого нужно вычесть число способов разместить предметы по ящикам 1-2-3 (четвертый пустой), 1-2-4 (третий пустой) и т.д. Но при этом окажется, что мы дважды вычли число способов, при котором и третий, и четвертый путой. Это нужно прибавить. Ну и так далее.

Более формально, обозначим через $A_i$ число способов разместить предметы, при котором $i$-й ящик пустой (может быть не только он). Тогда $|A_1\cup A_2\cup A_3\cup A_4|$ дает число способов, при которых есть хотя бы один пустой ящик. Это число нужно найти, используя принцип включений-исключений, а затем вычесть из общего числа способов.

[vadim55]

по поводу D

$$ D(4,9) = \left( {_{4 - 1}^{4 - 1 + 9} } \right) = \left( {_3^{12} } \right) = \frac{{12*11*10}} {{3*2*1}} $$

Добавлено спустя 12 минут 43 секунды:

то что Вы написали понятно,но не ясно как это делается.
если один ящик пустой то есть

$$ D(3,9)*D(3,12) $$

вариантов размещения

$$ |A1| = D(3,9)*D(3,12) $$

$$ |A2| = D(3,9)*D(3,12) $$

$$ |A3| = D(3,9)*D(3,12) $$

$$ |A4| = D(3,9)*D(3,12) $$

но как мне найти их пересечение?

[PAV]

Нет, это неверно. Пусть у Вас есть два ящика и два предмета. Сколькими способами можно разложить (без каких-либо дополнительных условий)? Перечислите, пожалуйста, все эти способы (их немного).

Добавлено спустя 1 минуту 22 секунды:

vadim55 писал(а):

но как мне найти их пересечение?

А Вы словами опишите, что означает пересечение множества $A_1$ и $A_2$.

[vadim55]

два ящика и два предмета
возможные варианты
{(0,2),(2,0),(1,1)}

пересечение множества когда есть одинаковые члены
(одинаковые варианты размещения)

[PAV]

Да, правильно, я ошибся. Насчет $D$ Вы все правильно сделали.

А насчет второго вопроса подумайте еще. Я не имел в виду сформулировать общее определение пересечения множеств, а что это означает для данной задачи.
Словами объясните, что означает, что вариант размещения принадлежит множеству $A_1$, что означает, что он принадлежит множеству $A_2$, и отсюда - какие варианты принадлежат одновременно и $A_1$, и $A_2$.

[vadim55]

к примеру Вы говорите
разместить предметы по ящикам 1-2-3 (четвертый пустой), 1-2-4 (третий пустой)
пересечением будет например
все предметы в первом а остальные пустые,или одинаковое размещение в первом и втором а 3,4 пустые...

[PAV]

PAV писал(а):

обозначим через $A_i$ число способов разместить предметы, при котором $i$-й ящик пустой

PAV писал(а):

какие варианты принадлежат одновременно и $A_1$, и $A_2$.

[vadim55]

только когда по крайней мере оба пустые(3-й и 4-й)

Добавлено спустя 7 минут 5 секунд:

получается

$$ |A1 \cap A2| = D(2,9)*D(2,12) $$

?

[PAV]

Правильно.

[vadim55]

тогда можно ли записать так

$$ U = D(4,9)*D(4,12) $$

$$ |A1| = D(3,9)*D(3,12) $$

$$ |A2| = D(3,9)*D(3,12) $$

$$ |A3| = D(3,9)*D(3,12) $$

$$ |A4| = D(3,9)*D(3,12) $$

$$ |A1 \cap A2| = D(2,9)*D(2,12) $$

$$ |A1 \cap A3| = D(2,9)*D(2,12) $$

$$ |A1 \cap A4| = D(2,9)*D(2,12) $$

$$ |A2 \cap A3| = D(2,9)*D(2,12) $$

$$ |A2 \cap A4| = D(2,9)*D(2,12) $$

$$ |A3 \cap A4| = D(2,9)*D(2,12) $$

$$ |A1 \cap A2 \cap A3| = $$

$$ |A1 \cap A2 \cap A4|= $$

$$ |A1 \cap A3 \cap A4| = $$

$$ |A2 \cap A3 \cap A4| = 1 $$

и

$$ |A1 \cap A2 \cap A3 \cap A4| = 0 $$

??

[PAV]

Правильно.

[vadim55]

решение

$$ U - |A1| + A2| + |A3| + |A4| - $$

$$ |A1 \cap A2| - |A1 \cap A3| - |A1 \cap A4| - $$

$$ |A2 \cap A3| - |A2 \cap A4| - |A3 \cap A4| + $$

$$ |A1 \cap A2 \cap A3| + |A1 \cap A2 \cap A4| + $$

$$ |A1 \cap A3 \cap A4| + |A2 \cap A3 \cap A4| - $$

$$ |A1 \cap A2 \cap A3 \cap A4| $$