Комбинаторное тождество. Откуда?

[alcoholist]

В процессе работы получил некий результат. Может быть кто-то сталкивался с подобным. Любая инфа приветствуется.

Разобьем множество из $n$ элементов на $m$ групп мощностей $k_1,\ldots k_m$ ($k_i\ge 2$). Причем любые две группы имеют ровно один не более одного общего элемента и каждый элемент сидит не менее чем в двух группах. Верно ли, что без всяких доп. предположений верно, что

$$ \sum_{i=1}^mC_{k_i}^2=C_n^2? $$

-- Пн авг 04, 2014 01:55:07 --

Ох... конечно, в общем случае неверно... Тем интересней. Мне бы найти такие числа $m$ (при данном $n$), при которых такие наборы $k_i$-х существуют.

Например, при $n=4$ число $m$ точно может быть 1, 4 и 6

при $n=5$ число $m$ может принимать значения 1,5,6,8,10

[maxal]

Это не верно уже в простейшем примере. Пусть $n=3$, разбейте множество $\{1,2,3\}$ на два: $\{1,2\}$ и $\{2,3\}$, которые имеют ровно один общий элемент - число 2.
Тогде в левой части вашего равенства стоит 2, а в левой 3.

[alcoholist]

maxal
Ну, я уже оговорился))

У меня такое предположение, что при данном $n$ минимальное $m>1$ равно $n$ ($k_1=\ldots=k_{n-1}=2$, $k_n=n-1$).

[maxal]

alcoholist в сообщении #893224 писал(а):

У меня такое предположение, что при данном $n$ минимальное $m>1$ равно $n$ ($k_1=\ldots=k_{n-1}=2$, $k_n=n-1$).

Это так по крайней мере для блоков равного размера, что образует систему Штейнера $S(2,k,n)$ - см. http://mathworld.wolfram.com/SteinerSystem.html

[alcoholist]

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

[alcoholist]

вот простая серия: $k_1,\ldots, k_s$ таковы, что $\sum k_i=n$, и имеется еще $m-s$ групп, в каждой из которых по два элемента и

$$ m=s+\sum_{1\le i<j\le s}k_ik_j $$

[alcoholist]

Сорри за поднятие темы, но вот это

alcoholist в сообщении #893224 писал(а):

У меня такое предположение, что при данном $n$ минимальное $m>1$ равно $n$ ($k_1=\ldots=k_{n-1}=2$, $k_n=n-1$).

заметил еще Paul Erdős