Верещагин, Шень. Эквивалентность и порядок

[Хорхе]

Правильный, прошу прощения, не заметил в гуще всего остального.

Хорошо.

Теперь такой вопрос: сколько цепей проходит через данное $k$-элементное множество $A$ (Вы можете представить такую цепь как объединение двух: той, что из $\varnothing$ приходит в $A$, и той, что из $A$ приходит $U$)?

[caxap]

Ну раз всего макс. цепей $n!$, а всего $k$-элементных множеств $\binom n k$, то через каждое $k$-элементное множество проходит $n!\big/ \binom n k$ макс. цепей.

[Null]

Ответ правильный,но не обоснованно почему через каждое $k$-элементное множество проходит одинаковое количество максимальных цепей.

[caxap]

Null
В силу симметрии все $k$-элементные множества равнозначны.

(Доказательство)

Предположим, что $k$-элементных множеств ($\in \mathcal P(U)$), содержащих элемент $u_1\in U$ больше, чем тех, которые содержат $u_2\in U$. Выполним биекцию $\varphi: U\to U$, которая переставит эти элементы ($u_1\mapsto u_2$ и наоборот; остальные элементы перейдут в себя). С одной стороны, теперь больше должно стать количество множеств, содержащих $u_2$, чем содержащих $u_1$. А с другой стороны -- ничего измениться не должно, т. к. $U=\varphi(U)$ и $\mathcal P(U)=\mathcal P(\varphi(U))$. Противоречие.

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

[Хорхе]

Это прекрасно. Рассуждения на тему симметрии всесильны, потому что они верны.

Теперь вопрос: какое наименьшее (по $k$) значение принимает $n!/{n\choose k}$?

[caxap]

Когда $k=0$ (или $k=n$), то $f(n,k):=n!\big/ \binom nk=k!\, (n-k)!=n!$. Если будем увеличивать $k$ (до середины $\lfloor n/2\rfloor$), то $f(n,k)$ будет уменьшаться (увеличивая $k$, мы "добавляем" множитель в $k!$ ценой потери бОльшего множителя из $(n-k)!$). Поскольку $f(n,k)=f(k,n)$, то такая же ситуация будет при уменьшении $k$ от $n$ до $\lfloor n/2\rfloor$. Значит минимум будет как раз посрединке, при $k=\lfloor n/2\rfloor$, т. е. $f(n,k)=f(\lceil n/2\rceil,\lfloor n/2\rfloor)=\lceil n/2\rceil !\, \lfloor n/2\rfloor!$.

[Хорхе]

Чудесно. Теперь напишите неравенство из этого моего поста, и Вы в дамках!

[caxap]

Получается $\lceil n/2\rceil !\, \lfloor n/2\rfloor! \cdot \ell \leqslant n!$ и

$$\ell \leqslant \frac{n!}{\lceil n/2\rceil !\, \lfloor n/2\rfloor!} = \binom n {\lfloor n/2\rfloor}$$

То есть мы доказали, что больше этого $\ell$ быть не может, а равенства мы знаем как добиться (см. первый пост). Всё, конец?

В формулках всё, конечно, здорово выходит, но я пока не до конца разобрался, откуда берётся то неравенство...

[Хорхе]

Всё, конец.

Насчет "не до конца разобрался", есть замечательное высказывание (тут у кого-то в подписи увидел):

Дж. фон Нейман писал(а):

В математике вещи не понимают. К ним привыкают.

[caxap]

Хорхе в сообщении #357702 писал(а):

В математике вещи не понимают. К ним привыкают.

Не, ну так нельзя. Надо понять.

Через каждый элемент максимальной антицепи длины $\ell$ может проходить $k!\,(n-k)!$ макс. цепей, где $k$ -- мощность рассматриваемого элемента антицепи. Мы знаем, что всего макс. цепей $n!$, значит $\ell \cdot k!\,(n-k)! \geqslant n! \iff \ell \geqslant \binom n k$.

[Хорхе]

caxap в сообщении #357705 писал(а):

Мы знаем, что всего макс. цепей $n!$, значит $\ell \cdot k!\,(n-k)! \geqslant n! \iff \ell \geqslant \binom n k$.

Только вот неравенство в другую сторону, а так правильно.

[caxap]

Хорхе в сообщении #357712 писал(а):

Только вот неравенство в другую сторону, а так правильно.

Странно. Я уже собирался исправлять, а вы ответили. Ведь $k$ -- это мощность элемента $s$ макс. антицепи $S$, а суммирование по элементам и ведётся, т. е. $k$ связанная переменная. Она из суммы выйти не смогла бы.

Ещё раз попробую. Через каждый $s\in S$ может проходить $|s|!\, (n-|s|)!$ макс. цепей. Проссумируем по всем элементам $S$:

$$\sum_{s\in S} |s|!\,(n-|s|)! \geqslant |S|\cdot \lceil n/2\rceil !\, \lfloor n/2 \rfloor !$$

С другой стороны эта сумма $\geqslant n!$, т. е. всех макс. цепей. А откуда вышло, что $|S|\cdot \lceil n/2\rceil !\, \lfloor n/2 \rfloor !\leqslant n!$ ?

-- Чт сен 30, 2010 19:47:20 --

Пардон, всё понял. Эта сумма $\leqslant n!$. Извиняюсь за тупость.

[caxap]

Ещё задачки из того же параграфа:

88. Сколько существует различных линейных порядков на множестве из $n$ элементов?

Каждому линейному порядку $a_1\leqslant a_2\leqslant\ldots\leqslant a_n$ можно поставить в соответствите последовательность $(a_1,a_2,\ldots,a_n)$. Таких последовательностей $n\cdot (n-1)\cdots 1=n!$ (по комбинаторному правилу умножения), а значит и линейных порядков столько же.

89. Докажите, что всякий частичный порядок на конечном множестве можно продолжить до линейного (если $x\leqslant y$ в исходном порядке, то и в новом должно быть так же).

Обозначим это множество $A$ и пусть в нём $n$ элементов. Рассмотрим множество $B\subset A$ тех элементов из $A$, которые не сравнимы. Введём порядок на $B$ следующим образом: возьмём любой элемент $b_1$ из $B$, затем возьмём второй $b_2$ и положим $b_1\leqslant' b_2$, затем третий $b_3$ и положим $b_2\leqslant' b_3$ и т. д., пока на всём множестве $B$ не получится линейный порядок.
На всех сравнимых элементах $A$ положим $\leqslant' = \leqslant$.
Далее возьмём максимальный элемент $a_n$ из $A$ и положим $a_n\leqslant' b_1$.

Таким образом, все элементы получились сравнимы, значит порядок линеен.

[Хорхе]

Первая решена правильно.

А вот тут:

caxap в сообщении #357774 писал(а):

Рассмотрим множество $B\subset A$ тех элементов из $A$, которые несравнимы.

непонятки. Вот если чум такой: $A=\{a,b,c\}$, $a<b$ --- единственное строгое сравнение, то чему равно $B$?

[caxap]

Хорхе в сообщении #357777 писал(а):

Вот если чум такой: $A=\{a,b,c\}$, $a<b$ --- единственное строгое сравнение, то чему равно $B$?

Ага, ошибся.

Попытка номер два. Для начала примем $\leqslant'=\leqslant$ на всех сравнимых элементах $A$.

Далее возьмём максимальный элемент $a_n\in A$ и рассмотрим множество $B$ тех элементов из $A$, которые не сравнимы с $a$. Внутри $B$ вводим порядок $\leqslant'$ так же, как я вводил его для $B$ в прошлом посте. Переносим этот порядок в множество $A$ и полагаем $a_n\leqslant' b_1$. Если в $A$ остались несравнимые элементы, переходим к началу абзаца и делаем те же шаги. Раз множество конечное, то рано или поздно из цикла выйдем. А раз выйдем, то значит порядок станет линейным.

-- Чт сен 30, 2010 21:33:27 --

В приведённом вами примере за один цикл получаем лум: $a <' b \leqslant c$, где $a <' b \iff a\leqslant' b \land a\neq b$.