Комбинаторика. Число комбинаций 2 подмножеств из заданного?

[Ontos]

У нас есть некоторое множество $N$, состоящее из $n$ элементов. Например, из $5$ элементов, или $50$, или $1000$.
Какой формулой определяется число всех возможных сочетаний $2$ (двух) подмножеств множества $N$? Подмножества не пересекаются (не содержат общих элементов), а их сумма может быть как тождественна $N$, так и меньше него (т.е. могут остаться элементы, не включенные в $2$ подмножества $N$ (но включенные в $N$), но могут и не остатся). Порядок элементов не важен.

Поясню на примере. У нас есть некая куча (количество $= n$) разных игрушек, каждая уникальна (т.е. например, $3$ игрушки в одной корзине и $2$ в другой - это не $1$ комбинация, а целый их набор, т.к. важно, что за игрушки положены).
Сколькими способами можно распределить часть или все игрушки из кучи в $2$ корзины, при чем в каждой корзине должна быть минимум $1$ игрушка?

[svv]

А корзины тоже различимы? Куклу в первую корзину, машинку во вторую — та же самая комбинация, что машинку в первую, куклу во вторую?

[Ontos]

Пока что понятно, что при любой комбинации игрушек в корзине №$1$, в которой в первую корзину положено $m_1$ игрушек, число вариантов для корзины №$2$ равно $(n-m_1)^2-2$ (2 вычитаем (пустое множество и все в $1$ корзине), т.к. обе корзины должны содержать хотя бы $1$ элемент). Например, в куче $10$ игрушек, в первую корзину мы положили $4$ (некий набор из $4$ игрушек, таких наборов всего $210$ (биноминальный коэффициент), то $(10-4)^2-2=62$ варианта (приложимых к каждому из первых $210$ вариантов).

-- 08.12.2017, 22:02 --

svv в сообщении #1273285 писал(а):

А корзины тоже различимы? Куклу в первую корзину, машинку во вторую — та же самая комбинация, что машинку в первую, куклу во вторую?

Да, корзины не различимы в таком контексте. А даже если бы были различимы, это бы просто умножило результат на $2$.

[svv]

Пусть корзины будут различимы, если нет, разделить количество комбинаций на 2 Вы всегда сможете.
Перенумеруем игрушки от $0$ до $n-1$.
Рассмотрим множество $n$-разрядных троичных чисел. У каждого такого числа ровно $n$ разрядов, от нулевого до $n-1$-го. В каждом разряде стоит цифра $0,1$ или $2$.
Придумайте простой способ кодирования распределения игрушек по корзинам троичным числом, и у Вас наступит ясность.

Каждой комбинации соответствует $n$-разрядное троичное число, но не наоборот (некоторые комбинации не разрешены). Но эта проблема небольшая: такие комбинации легко сосчитать.

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);

Односимвольные обозначения тоже оформляются как формулы.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[Ontos]

Благодаря подсказкам svv догадался и нашёл решение: $\dfrac{3^n-2^{n+1}+1}{2}$
$3^n$ - потому что базой подсчёта служит перебор сочеатний из кучи и 2 корзин. $-2^{n+1}$ - вычитаются все сочетания, в которых элементы распределены между кучей и первой корзиной, и кучей и второй корзиной. $+1$ -добавляется единица ввиду дубля в предыдущем вычитании варианта со всеми элементами в куче. $/2$ - т.к. без этого мы получим варианты с различием корзин, что не требуется.
$\begin{tabular}{|l|l|l|}\hline число элементов& количество комбинаций& отношение*\\ \hline 1& 0& \\ \hline 2& 1& \\ \hline 3& 6& 6\\ \hline 4& 25& 4,1(6)\\ \hline 5& 90& 3,6\\ \hline 6& 301& 3,3(4)\\ \hline 7& 966& 3,2093\\ \hline 8& 3 025& 3,1314\\ \hline 9& 9 330& 3,0843\\ \hline 10& 28 501& 3,0548\\ \hline\end{tabular}$
*Отношение текущего числа кобинаций (при $n$) к предыдущему (при $n-1$), Стремится к $3$.