Количество подсемейств конечного множетсва. Комбинаторика

[Норберт]

Пусть
$\mathfrak{I}_k=\{I \subset \{1,...,n\} : 1 \leqslant\ |I| \leqslant k-1\}$
$\mathfrak{J}_{k,s}=\{\mathfrak{I} \subset \mathfrak{I}_k : |\mathfrak{I}|=s\}$
Нужно найти мощность множества
$\{\mathfrak{J} \in \mathfrak{J}_{k,s} : |\bigcap\limits_{I \in \mathfrak{J}} I|=m\}$

[Circiter]

Ужас... Игла в яйце, яйцо в утке, утка в зайце...

Пока посчитал только, что

$$|\mathfrak{J}_k|=\sum_{i=1}^{k-1}{n \choose i},$$

а мощность $\mathfrak{J}_{k,s}$ равна вроде-бы

$$|\mathfrak{J}_{k,s}|={|\mathfrak{J}_k| \choose s}.$$

Сейчас может ещё чего придумаю... Кстати, возможно получится упростить выражение для $|\mathfrak{J}_k|$ используя тот факт, что $|\mathfrak{J}_{n+1}|=2^n$...

-- Пн сен 07, 2009 20:15:40 --

Кажется, запутался... Поправьте если не прав, но вроде бы исходную задачу можно переформулировать примерно так: сколько раз выполнятся равенство числу $m$ мощности пересечений $s$ штук не более чем $k-1$ элементных подмножеств отрезка $[1;n]\subset\mathbb{N}$. Я правильно понял? Просто никак не могу переварить то подвыражение с символом пересечения...

[maxal]

Норберт в сообщении #241180 писал(а):

Пусть
$\mathfrak{I}_k=\{I \subset \{1,...,n\} : 1 \leqslant\ |I| \leqslant k-1\}$
$\mathfrak{J}_{k,s}=\{\mathfrak{I} \subset \mathfrak{I}_k : |\mathfrak{I}|=s\}$
Нужно найти мощность множества
$\{\mathfrak{J} \in \mathfrak{J}_{k,s} : |\bigcap\limits_{I \in \mathfrak{J}} I|=m\}$

Ответом является $\frac{1}{s!}{n\choose m}$ умноженное на количество матриц размера $s\times (n-m)$ с элементами из $\{0,1\}$, где сумма элементов каждой строки не превосходит $k-1-m$, а в каждом столбце присутствует хотя бы один $0$.

[Норберт]

To Circiter. Вы все поняли правильно.
To maxal. Нехочу вас обидеть, но этот ответ, по-моему, ничем не лучше исходной записи. Как мне посчитать количество таких матриц. Хотя бы рекуррентная формула, я в комбинаторике $\varnothing$.

[maxal]

Норберт в сообщении #241296 писал(а):

To maxal. Нехочу вас обидеть, но этот ответ, по-моему, ничем не лучше исходной записи. Как мне посчитать количество таких матриц. Хотя бы рекуррентная формула, я в комбинаторике $\varnothing$.

Это хорошо, что вы понимаете как получается указанная мной переформулировка. Она хороша там, что позволет легко получить ответ - нужно лишь применить принцип включений-исключений и найти количество 01-матриц, не удовлетворяющих ни одному из свойств $P_i = $ "в $i$-м столбце нет нулевых элементов".

[Норберт]

Прикол весь в том что поставленная задача как раз возникла из задачи упрощения сумм в формуле включений исключений. А ваш метод к сожалению все возвращает на круги своя.
И более того, даже если пойти вашим путем то нужно использовать другое свойство:
$P_{i,j}$ = "в $i$-м столбце нет ненулевых элементов или в $j$-м столюце сумма элементов больше $k-1-m$"

[maxal]

Норберт в сообщении #241476 писал(а):

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

А кто сказал, что такое упрощение возможно?

Норберт в сообщении #241476 писал(а):

И более того, даже если пойти вашим путем то нужно использовать другое свойство:
$P_{i,j}$ = "в $i$-м столбце нет ненулевых элементов или в $j$-м столюце сумма элементов больше $k-1-m$"

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

-- Tue Sep 08, 2009 06:58:57 --

Чтобы не ходить вокруг да около - у меня получается такая формула:

$$\frac{1}{s!}{n\choose m} \sum_{j=0}^{n-m} (-1)^j {n-m\choose j} \left( \sum_{i=0}^{k-1-m-j} {n-m-j\choose i}\right)^s.$$

[Норберт]

Большое спасибо за окончатльную формулу! Если у вас хватит терпения, пожалуйста напишите доказательство.

[maxal]

Набросок доказательства по сути расписан в обсуждении выше.

[Норберт]

Хорошо, буду разбираться. Еще раз большое спасибо!

[Норберт]

Все таки я не понимаю как из условия что в матрице нет ненулевых столбцов следует что сумма элементов в строках не превышает $k-m$.
Пусть $n=5$ $m=1$ $k=3$ $s=3$. Рассмотрим матрицу размера $s \times (n - m)$
$ \left( \begin{array}{cccc} 1 & 1 & 1 & 0 \\ 1& 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{array} \right)$
В ней все столбцы имеют нулевой элемент, но сумма элементов больше чем $k-1-m$.
Мне кажется что в этой формуле ошибка. Еще один аргумент этот тот факт что в ней не согласуются пределы суммирования. Т.к. $ 0 \le j \le n-m$ , $0 \le i \le k -1 - m- j$ то при $j=n-m$ получим $0 \le i \le k-1-n$. По условию $k-1 < n$, т.е. $0 \le i \le k-1-n < 0$ ???

[maxal]

Норберт в сообщении #242111 писал(а):

Все таки я не понимаю как из условия что в матрице нет ненулевых столбцов следует что сумма элементов в строках не превышает $k-m$.

Не следует. Это два независимых требования. Подсчет же матриц идет так: про требование наличия нулевых элементов в столбцах забывается, и подсчитываются матрицы только со вторым требованием (о суммах в строках). А первое требование привносится в подсчёт с помощью принципа включений-исключений.

-- Thu Sep 10, 2009 12:39:54 --

maxal в сообщении #242123 писал(а):

Мне кажется что в этой формуле ошибка. Еще один аргумент этот тот факт что в ней не согласуются пределы суммирования. Т.к. $ 0 \le j \le n-m$ , $0 \le i \le k -1 - m- j$ то при $j=n-m$ получим $0 \le i \le k-1-n$. По условию $k-1 < n$, т.е. $0 \le i \le k-1-n \le 0$ ???

Я нигде не использовал неравенство $k-1 < n$. Но оно ничему не вредит - просто некоторые биномиальные коэффициенты в сумме будут равны 0.

[Норберт]

Но тогда как понимать суммы с такими верхними пределами?
Если суммы вида $\sum\limits_{i=0}^{-2}F(i)$ полагать равными нулю (как это обычно и делают), то эта форумула не работает.
Пусть $n=2$ $k=2$ $s=2$ тогда
$\mathfrak{J}_k=\{\{1\},\{2\}\}$
$\mathfrak{J}_{k,s}=\{\{\{1\},\{2\}\}\}$
тогда
$\{\mathfrak{J} \in \mathfrak{J}_{k,s} : |\bigcap\mathfrak{J}|=1\}=\varnothing$
т.е.
$|\{\mathfrak{J} \in \mathfrak{J}_{k,s} : |\bigcap\mathfrak{J}|=1\}|=0$
Что же дает формула...
$\frac{1}{s!}{n\choose m}\sum\limits_{j=0}^{n-m}(-1)^j{n-m \choose j}\left(\sum\limits_{i=0}^{k-1-m-j}{n-m-j \choose i}\right)^s=\frac{1}{2!}{2\choose 1}\sum\limits_{j=0}^{2-1}(-1)^j{2-1 \choose j}\left(\sum\limits_{i=0}^{2-1-1-j}{2-1-j \choose i}\right)^2=\frac{1}{2} 2 \sum\limits_{j=0}^{1}(-1)^j{1 \choose j}\left(\sum\limits_{i=0}^{-j}{1-j \choose i}\right)^2=(-1)^0{1 \choose 0}\left(\sum\limits_{i=0}^{-0}{1-0 \choose i}\right)^2+(-1)^1{1 \choose 1}\left(\sum\limits_{i=0}^{-1}{1-1 \choose i}\right)^2={1 \choose 0}\left(\sum\limits_{i=0}^{-0}{1-0 \choose i}\right)^2+(-1)^1{1 \choose 1}\left(\sum\limits_{i=0}^{-1}{1-1 \choose i}\right)^2=1({1 \choose 0})^2+(-1)(\sum\limits_{i=0}^{-1}{1-1 \choose i})^2=1-0=1$
Выходит что формула не работает?

[maxal]

Действительно формула не работает, но причина кроется в том, что на матрицы нужно наложить еще одно условие - все строки в них должны быть различны (так как они соответствуют различным подмножествам). Соответственно, формула видоизменяется так: вместо $\frac{1}{s!} (\ldots)^s$ должно стоять $\binom{\ldots}{s}.$ Итоговая формула такая:

$${n\choose m} \sum_{j=0}^{n-m} (-1)^j {n-m\choose j} \binom{\sum\limits_{i=0}^{k-1-m-j} {n-m-j\choose i}}{s}.$$

-- Thu Sep 10, 2009 15:58:02 --

Вот некоторые численные значения:

? f(n,k,m,s) = binomial(n,m)*sum(j=0,n-m,(-1)^j*binomial(n-m,j)*binomial(sum(i=0,k-1-m-j,binomial(n-m-j,i)),s));
? for(s=1,3,forvec(v=[[1,3],[1,3],[1,3]], print("[n,k,m,s] = ",[v[3],v[2]+1,v[1],s]," : ",f(v[3],v[2]+1,v[1],s)),1))
[n,k,m,s] = [1, 2, 1, 1] : 1
[n,k,m,s] = [2, 2, 1, 1] : 2
[n,k,m,s] = [3, 2, 1, 1] : 3
[n,k,m,s] = [2, 3, 1, 1] : 2
[n,k,m,s] = [3, 3, 1, 1] : 3
[n,k,m,s] = [3, 4, 1, 1] : 3
[n,k,m,s] = [2, 3, 2, 1] : 1
[n,k,m,s] = [3, 3, 2, 1] : 3
[n,k,m,s] = [3, 4, 2, 1] : 3
[n,k,m,s] = [3, 4, 3, 1] : 1
[n,k,m,s] = [1, 2, 1, 2] : 0
[n,k,m,s] = [2, 2, 1, 2] : 0
[n,k,m,s] = [3, 2, 1, 2] : 0
[n,k,m,s] = [2, 3, 1, 2] : 2
[n,k,m,s] = [3, 3, 1, 2] : 9
[n,k,m,s] = [3, 4, 1, 2] : 12
[n,k,m,s] = [2, 3, 2, 2] : 0
[n,k,m,s] = [3, 3, 2, 2] : 0
[n,k,m,s] = [3, 4, 2, 2] : 3
[n,k,m,s] = [3, 4, 3, 2] : 0
[n,k,m,s] = [1, 2, 1, 3] : 0
[n,k,m,s] = [2, 2, 1, 3] : 0
[n,k,m,s] = [3, 2, 1, 3] : 0
[n,k,m,s] = [2, 3, 1, 3] : 0
[n,k,m,s] = [3, 3, 1, 3] : 3
[n,k,m,s] = [3, 4, 1, 3] : 12
[n,k,m,s] = [2, 3, 2, 3] : 0
[n,k,m,s] = [3, 3, 2, 3] : 0
[n,k,m,s] = [3, 4, 2, 3] : 0
[n,k,m,s] = [3, 4, 3, 3] : 0

[Норберт]

Да, похоже это то что нужно!
Сударь, Вы безбожно круты! Низкий Вам поклон.