Пересечение подмножеств пустое

[Guliashik]

Есть множество $A = \{1, 2, ...., n\}$. Чему равно количество способов выбрать $k$ подмножеств множества $A$, таких что $A_1 \bigcap A_2 \bigcap ... \bigcap A_k = \varnothing _$.
Мои мысли таковы:
Пусть ответ равен $X$, а $Y$ есть количество способов выбрать $k$ подмножеств $A$, таких что $A_1 \bigcap A_2 \bigcap ... \bigcap A_k \ne \varnothing$. Тогда $X = {2^n \choose k} - Y$.
В свою очередь $Y$, разбивается на такие варианты: пересечение состоит из одного элемента, двух и т.д.
Дальше мыслей нет. Направьте на верный путь, пожалуйста.

[patzer2097]

Guliashik в сообщении #832914 писал(а):

В свою очередь $Y$, разбивается на такие варианты: пересечение состоит из одного элемента, двух и т.д. Дальше мыслей нет.

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

[iifat]

Guliashik в сообщении #832914 писал(а):

Дальше мыслей нет

Да и не надо, имхо. Обозначим $P(n,k)$ число искомых разбиений; сколько будет разбиений, таких что $A_1 \bigcap A_2 \bigcap ... \bigcap A_k = B$?

[Guliashik]

iifat, если я вас верно понял.
Пусть $z$ мощность пересечения $A_1 \bigcap ... \bigcap A_k$. Тогда, количество подмножеств $A$, таких что, в каждом из них есть определённое подмножество мощности $z$ равняется $\sum \limits ^{n}_{p=1} {n \choose {p - z}}$. Обозначим эту сумму $W(z)$. Тогда для определённого пересечения, количество способов выбрать $k$ подмножеств из $A$, есть ${W(z) \choose k}$. Но чувствую подобные рассуждения приводят к принципу включений и исключений.

[iifat]

Я, собственно, имел в виду, что если из каждого множества (включая универсум) вычесть общее пересечение, останется как раз наше разбиение. Остаётся просуммировать и, как уж получится, упростить. И включений-исключений не нужно. Получится всё равно нечто многоэтажное, думаю, но тут уж судьба.

-- 05.03.2014, 22:03 --

Как вариант: посчитать при малых $n$ (тут зависит от того, допускается ли $\varnothing$ среди элементов разбиения) и посмотреть, как меняется количество при переходе от $n$ к $n+1$. Навскидку, $P(n+1,k)=(2^n-1)P(n,k)$