Да, извините, ступил
![:oops: :oops:](./images/smilies/icon_redface.gif)
Поздно было...
Ну вот давайте на примере множества
![$U=\{a,b,c,d,e\}$ $U=\{a,b,c,d,e\}$](https://dxdy-01.korotkov.co.uk/f/4/f/c/4fc1fb07da6fad4bd3082cc0e911d9e382.png)
рассмотрим (я буду для краткости писать просто "abcde"). А потом перейдем к общему случаю.
![$\mathcal P(U)$ $\mathcal P(U)$](https://dxdy-02.korotkov.co.uk/f/9/7/d/97dcbc05958e5ddd66dc7948d3c5301c82.png)
будет содержать:
мощности 0) 1 элемент:
![$\varnothing$ $\varnothing$](https://dxdy-01.korotkov.co.uk/f/0/2/7/027e4f6240ef037b4e6e1348274b505282.png)
;
мощности 1) 5 элементов: "a","b","c","d","e";
мощности 2) 10 элементов: "ab","ac","ad","ae","bc","bd","be","cd","ce","de";
мощности 3) 10 элементов: "abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde";
мощности 4) 5 элементов: "abcd","abce","abde","acde","bcde";
мощности 5) 1 элемент: "abcde".
Посчитаем количество возможных максимальных цепей:
![$s_0=\varnothing$ $s_0=\varnothing$](https://dxdy-03.korotkov.co.uk/f/6/3/8/638fffe282f8874a6ae71950f310a86882.png)
выбираем одним способом,
![$s_1$ $s_1$](https://dxdy-03.korotkov.co.uk/f/2/8/6/286f7d4815c0996530bda7973b1ec5ea82.png)
(напр. "a") выбираем 5 способами,
![$s_2$ $s_2$](https://dxdy-02.korotkov.co.uk/f/9/7/c/97c7f491f7ac1623c0a86b1fb656029b82.png)
(напр. "ab") выбираем 5-1 способами,
![$s_3$ $s_3$](https://dxdy-04.korotkov.co.uk/f/b/5/0/b507dc5337a783c005c65bf133ed415b82.png)
(напр. "abc") -- 5-2 способами,
![$s_4$ $s_4$](https://dxdy-03.korotkov.co.uk/f/2/c/e/2ceb35984410572f06b0a996a47ba31b82.png)
(напр. "abcd") -- 5-3 способами и
![$s_5=U$ $s_5=U$](https://dxdy-03.korotkov.co.uk/f/6/7/b/67b8b78bb096de47afcb5770371a13d082.png)
-- 5-4=1 способом.
В общем случае аналогично:
![$N=n \cdot (n-1) \cdot (n-2) \cdots 1 = n!$ $N=n \cdot (n-1) \cdot (n-2) \cdots 1 = n!$](https://dxdy-03.korotkov.co.uk/f/6/6/9/6699022b7ee46011454c605d1919e92b82.png)
.
-- Чт сен 30, 2010 11:07:16 --учитывая, что каждая цепь может проходить только через один элемент антицепи,
А это откуда следует? Напр. цепь a,ab,abc,abcde и антицепь b,c,de не содержат общего элемента. Если же вы имели ввиду максимальные цепи и антицепи, то, по-моему, здесь нужно знать, какая будет максимальная антицепь, а мы это и пытаемся определить.
-- Чт сен 30, 2010 11:30:07 --Неужели нельзя проще? Предположим мы выбрали антицепь
![$S$ $S$](https://dxdy-03.korotkov.co.uk/f/e/2/5/e257acd1ccbe7fcb654708f1a866bfe982.png)
из всех элементов
![$\mathcal P(U)$ $\mathcal P(U)$](https://dxdy-02.korotkov.co.uk/f/9/7/d/97dcbc05958e5ddd66dc7948d3c5301c82.png)
средней мощности
![$\lfloor n/2\rfloor$ $\lfloor n/2\rfloor$](https://dxdy-04.korotkov.co.uk/f/3/3/8/338967e3d765ed070d52afec9792cdb882.png)
(как я писал в первом посте). Надо доказать, что любое отступление приведёт к уменьшению
![$|S|$ $|S|$](https://dxdy-03.korotkov.co.uk/f/6/5/8/65840c883e7323ab67192c3db4729de182.png)
.
Просто взять дополнительный элемент из оставшегося
![$\mathcal P(U)$ $\mathcal P(U)$](https://dxdy-02.korotkov.co.uk/f/9/7/d/97dcbc05958e5ddd66dc7948d3c5301c82.png)
нельзя: он обязательно будет включатся в какой-то элемент
![$S$ $S$](https://dxdy-03.korotkov.co.uk/f/e/2/5/e257acd1ccbe7fcb654708f1a866bfe982.png)
или наоборот. Значит, чтобы взять из
![$\mathcal P(U)$ $\mathcal P(U)$](https://dxdy-02.korotkov.co.uk/f/9/7/d/97dcbc05958e5ddd66dc7948d3c5301c82.png)
какой-то другой элемент, надо исключить какой-то (какие-то) элементы из текущего
![$S$ $S$](https://dxdy-03.korotkov.co.uk/f/e/2/5/e257acd1ccbe7fcb654708f1a866bfe982.png)
. Но любой элемент
![$s'\in\mathcal P(U)$ $s'\in\mathcal P(U)$](https://dxdy-01.korotkov.co.uk/f/4/5/6/456f4857fc5fede2a8a19e302ca315d282.png)
даже ближайщей снизу мощности
![$\lfloor n/2\rfloor-1$ $\lfloor n/2\rfloor-1$](https://dxdy-03.korotkov.co.uk/f/2/0/3/203bf0a40cf30eaf4748c302ee40c52f82.png)
включается в
![$n-\lfloor n/2\rfloor = \lceil n/2\rceil$ $n-\lfloor n/2\rfloor = \lceil n/2\rceil$](https://dxdy-03.korotkov.co.uk/f/e/a/6/ea64eddc8f4ce53e3fcd084c8a57e84f82.png)
элементов текущего
(а более низкой мощности -- включается в ещё большее число), а значит, чтобы включить один
![$s'$ $s'$](https://dxdy-03.korotkov.co.uk/f/6/7/5/675c2f5707a1fa7050c12adc1872ba3282.png)
надо исключить
![$\lceil n/2\rceil-1$ $\lceil n/2\rceil-1$](https://dxdy-02.korotkov.co.uk/f/5/8/e/58e4c07185c026f1e7436d144b6a490082.png)
элементов из текущего
![$S$ $S$](https://dxdy-03.korotkov.co.uk/f/e/2/5/e257acd1ccbe7fcb654708f1a866bfe982.png)
.
Таким образом, включение элемента из
мощности меньше средней, в итоге уменьшает мощность
.Аналогичная ситуация с элементами из
![$\mathcal P(U)$ $\mathcal P(U)$](https://dxdy-02.korotkov.co.uk/f/9/7/d/97dcbc05958e5ddd66dc7948d3c5301c82.png)
мощности, больше средней.
Значит любое отступление в сторону от текущего
приведет к уменьшению его мощности. А значит максимум и будет, когда
![$S$ $S$](https://dxdy-03.korotkov.co.uk/f/e/2/5/e257acd1ccbe7fcb654708f1a866bfe982.png)
состоит из всех элементов
![$\mathcal P(U)$ $\mathcal P(U)$](https://dxdy-02.korotkov.co.uk/f/9/7/d/97dcbc05958e5ddd66dc7948d3c5301c82.png)
средней мощности.
Такое доказательство годится?
(Ув. Хорхе, если честно, по мне лучше вылизать данное доказательство, если оно имеет верное направление, чем то, на которое направляете меня вы. Просто потому, что в своём я хоть что-то понимаю. Но если мой путь никуда не ведёт, то буду следоватать вашему методу
)