2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3, 4, 5, 6  След.
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 15:34 
Аватара пользователя
Правильный, прошу прощения, не заметил в гуще всего остального.

Хорошо.

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

 
 
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 15:55 
Аватара пользователя
Ну раз всего макс. цепей $n!$, а всего $k$-элементных множеств $\binom n k$, то через каждое $k$-элементное множество проходит $n!\big/ \binom n k$ макс. цепей.

 
 
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 16:23 
Ответ правильный,но не обоснованно почему через каждое $k$-элементное множество проходит одинаковое количество максимальных цепей.

 
 
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 16:34 
Аватара пользователя
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))$. Противоречие.

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

 
 
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 16:53 
Аватара пользователя
Это прекрасно. Рассуждения на тему симметрии всесильны, потому что они верны.

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

 
 
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 17:13 
Аватара пользователя
Когда $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!$.

 
 
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 18:03 
Аватара пользователя
Чудесно. Теперь напишите неравенство из этого моего поста, и Вы в дамках!

 
 
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 18:24 
Аватара пользователя
Получается $\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$ быть не может, а равенства мы знаем как добиться (см. первый пост). Всё, конец?

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

 
 
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 18:47 
Аватара пользователя
Всё, конец.

Насчет "не до конца разобрался", есть замечательное высказывание (тут у кого-то в подписи увидел):
Дж. фон Нейман писал(а):
В математике вещи не понимают. К ним привыкают.

 
 
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 18:51 
Аватара пользователя
Хорхе в сообщении #357702 писал(а):
В математике вещи не понимают. К ним привыкают.

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

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

 
 
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 19:10 
Аватара пользователя
caxap в сообщении #357705 писал(а):
Мы знаем, что всего макс. цепей $n!$, значит $\ell \cdot k!\,(n-k)! \geqslant n! \iff \ell \geqslant \binom n k$.

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

 
 
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 19:36 
Аватара пользователя
Хорхе в сообщении #357712 писал(а):
Только вот неравенство в другую сторону, а так правильно.

:shock: Странно. Я уже собирался исправлять, а вы ответили. Ведь $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!$. Извиняюсь за тупость.

 
 
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 20:58 
Аватара пользователя
Ещё задачки из того же параграфа:

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$.

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

 
 
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 21:05 
Аватара пользователя
Первая решена правильно.

А вот тут:
caxap в сообщении #357774 писал(а):
Рассмотрим множество $B\subset A$ тех элементов из $A$, которые несравнимы.

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

 
 
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 21:24 
Аватара пользователя
Хорхе в сообщении #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$.

 
 
 [ Сообщений: 81 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group