Теорема(Шпернер). Нека n е естествено число и А е фамилия от подмножества на множеството {1,2,...,n} така, че никой елемент на А не се съдържа в друг елемент на А.
Тогава max|A|=Ckn , където к=[n/2].(тук под Ckn=n!/k!(n-k)! разбираме съответния биномен коефициент)
Д-во: Да разгледаме множеството на всички вериги Т от вида Т1,Т2,...,Тn, като |Тi|=i, Тi е подмножество на Тi+1, за всяко i=1,2,...,n-1.
Броят на веригите е n! понеже 1 елемент на Т1 може да се избере по n-начина, след като е избран този елемент участва в Т2 и 2-рия елемент можем да го изберем по n-1 начина.Тези 2 елемента участват в Т3, а 3-тия елемент на Т3 можем да го изберем по n-2 начина и т.н. Броя на всички вериги от Т е |T|=n!.
Нека А={A1,A2,...,Ar} е търсената фамилия, kъдето Ai не е подмножество на Aj за всеки i,j: 1≤i≠j≤r.
За всяко i от множеството {1,2,...,n},ако |Ai|=ki, то Ai принадлежи на точно ki!(n-ki)! вериги от Т, т.е.
Ai=Тki и съответните вериги с участието на Тki-фиксирано с ki на брой елемента са:
Т1,...,Тki-1,Тki,Тki+1,...,Тn.
Както казахме елементите на Ai=Тki са фиксирани и са ki на брой. Тогава Тki+1 съдържа Тki и има с един елемент повече, този елемент можем да го изберем по n-ki начина.Аналогично Тki+2 съдържа Тki+1 и има с един елемент повече, който можем да го изберем n-ki-1 начина, и т.н. частта от веригата Тki+1,Тki+2,...,Тn може да се избере по (n-ki)(n-ki-1)...2.1=(n-ki)! начина.
Аналогично частта Т1,Т2,...,Тki-1 от Т при фиксирано Ai=Тki може да се избере
по ki! начина.Наистина Тki съдържа точно ki елемента,Тki-1 се различава от Тki с това че е подмножество на Тki и има един елемент по-малко, тогава броя на начините по които можем да получим Тki-1 от Тki като премахнем един елемент е ki. Аналогично Тki-2 може да се избере по ki-1 начина и т.н., Т1 може да се избере по 2 начина. Значи броя на начините
по които може да изберем веригата Т(i) = Т1,Т2,...,Тki-1,Тki+1,...,Тn-1,Тn
e ki!(n-ki)!.
Значи Ai участва в точно ki!(n-ki)! вериги и никои 2 елемента Ai и Aj не учстват в една и съща верига, в противен случай -би се оказало,че Ai е подмножество на Aj или обратно.
Така показахме,че на всеки елемент Ai на А, i=1,2,...,r съотвестват ki!(n-ki)! на брой вериги във всяка от които участва само Ai.
Значи разбихме веригите в групи по ki!(n-ki)! на брой, и като сумираме по i=1,2,...,r получаваме ∑ki!(n-ki)! = n!, т.е.
∑ki!(n-ki)!/n! = 1 => ∑1/Ckin=1. Нека s=[n/2], тогава Ckin≤Csn, понеже най-голямата стойност на Cjn се достига при j=[n/2].Тогава
1/Csn≤1/Cnki => 1=∑1/Ckin≥∑1/Csn=r/Cns => r≤Csn.
Но ако изберем Ai да са всичките [n/2] елементни подмножества на {1,2,...,n}, то за всеки i,j: 1≤i<j≤r Ai не е подмножество на Aj, нито обратното.Така получихме r≥Csn.
Значи Csn≤r≤Csn =>
max|A|=r =Csn , при s=[n/2]. С това теоремата е доказана.
|
Меню
Регистрирайте се
