2014 dxdy logo

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

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




 
 Доказательство комбинаторных формул
Сообщение27.08.2009, 11:48 
Пусть $F$ - некоторая формула с целыми числами, либо сравнение. Пусть $D_1$ - ее доказательство, основанное на комбинаторных рассуждениях для множеств или для групп. Можно ли тогда утверждать, что для $F$ есть доказательство $D_2$ использующее чисто числовые рассуждения?
Может литература есть по этому вопросу, где это все нормально описано?

-- Чт авг 27, 2009 13:35:47 --

Вот задача для примера:
доказать, что для любого натурального $n$ и простого $p$ $n$ делит $\phi (p^n-1)$.

 
 
 
 Re: Доказательство комбинаторных формул
Сообщение04.09.2009, 14:38 
Я, кажется, очень коротко написал... Подробнее:
Возьмем формулу $C^p_{2p} \equiv 2 (\mod p), p$ - простое. Ее можно доказать двумя способами:
1. $C^p_{2p} = 2 \frac{(p+1)(p+2)...(2p-1) \cdot(p-1)!}{(p-1)!^2} \equiv 2 \frac{(p-1)!^2}{(p-1)!^2} \equiv 2 (\mod p)$.
2. Возьмем множество $X$ двоичных векторов длины $2p$, содержащих $p$ нулей и $p$ единиц. Введем на $X$ отношение эквивалентности: $a \sim b \Leftrightarrow a$ - циклическая перестановка $b$. Тогда отношение эквивалентности разбивает $X$ на классы эквивалентности 2-х типов. 1-й тип содержит только 1 класс, который содержит только те 2 вектора, у которых единицы и нули чередуются. 2-й тип содержит остальные классы мощности $p$. Поскольку $|X|=C^p_{2p}$, то $C^p_{2p} - 2$ делится на $p$. Ч.т.д.
Таких числовых формул, имеющих 2 разных доказательства можно привести много. Например, свертка Вандермонда биномиальных коэффициентов, вышеупомянутая $n | \phi(p^n-1)$, возможно туда же можно отнести бином Ньютона, и еще кажется формулы делимости, которые получаются из леммы Бернсайда.
Вопрос такой. Может ли кто-нибудь толком сформулировать определение класса таких формул, определения таких 2-х типов доказательства, или это деление условно, есть ли литература на эту тему?

 
 
 
 Re: Доказательство комбинаторных формул
Сообщение05.09.2009, 06:45 
Аватара пользователя
Стенли в "Перечислительной комбинаторике" явно разделяет эти два типа доказательств.

 
 
 
 Re: Доказательство комбинаторных формул
Сообщение08.09.2009, 06:27 
maxal!
Спасибо, книга интересная, почитаю :-)

 
 
 [ Сообщений: 4 ] 


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