Множество

[Spider Iovkov]

Съвкупността [tex]{A_{1}, ..., A_{k}}[/tex] наричаме Шпернерова, ако всеки две от тях са несравними, тоест никое не е подмножество на друго.

Нека [tex]A[/tex] е [tex]n[/tex]-елементно множество и [tex]{A_{1}, ..., A_{k}}[/tex] е Шпернерова съвкупност от подмножествата на [tex]A[/tex]. Ако [tex]|A_{i}|=n_{i}[/tex], тогава
[tex]\frac{1}{C_{n}^{n_{1}}}+\frac{1}{C_{n}^{n_{2}}}+...+\frac{1}{C_{n}^{n_{k}}}\le1[/tex]
и равенството е налице точно тогава, когато съвкупността [tex]{A_{1}, ..., A_{k}}[/tex] се състои от всички [tex]r[/tex]-елементни подмножества на [tex]A[/tex] за някое [tex]r[/tex]. Да се докаже това неравенство.

[Реклама]

[Baronov]

http://en.wikipedia.org/wiki/Lubell-Yamamoto-Meshalkin_inequality