2014 dxdy logo

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

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




 
 Комбинаторика (количество пар множеств, сумма)
Сообщение12.02.2014, 12:44 
Даны натуральные числа $m$ и $n$. Через $F_k$ обозначим количество пар множеств $(A,B)$, таких, что $A\subseteq\{1,\ldots,k\}$, $B\subseteq\{0,1,\ldots,k\}$, $|A|=m$, $|B|=n$, $\{1,\ldots,k\}\subseteq A\cup B$.

Доказать, что
$\sum_{k=0}^{+\infty}(-1)^k F_k = 0 $

Интересуют разные способы решения.

 
 
 
 Re: Комбинаторика (количество пар множеств, сумма)
Сообщение12.02.2014, 21:34 
Можно попробовать явно вычислить формулу для $F_k$ через биномиальные коэффициенты и вычислить полученную сумму.
Кстати, вычисление суммы простое, если вспомнить формулу для $k$-й конечной разности.

 
 
 
 Re: Комбинаторика (количество пар множеств, сумма)
Сообщение12.02.2014, 21:43 
Зачем-то переместили в "Помогите решить, разобраться", т.е., вместо красивых разных способов решения будут только подсказки, чтобы я решил, хотя я решение знаю.

-- Ср фев 12, 2014 22:51:38 --

Но вот прямого решения "в лоб" я не вижу.

-- Ср фев 12, 2014 23:10:52 --

Sonic86 в сообщении #825720 писал(а):
Можно попробовать явно вычислить формулу для $F_k$ через биномиальные коэффициенты и вычислить полученную сумму.
Кстати, вычисление суммы простое, если вспомнить формулу для $k$-й конечной разности.


Да, через конечную разность красиво получается.
Но, всё-таки, это не "учебное" решение, не понимаю причину переноса темы.

 
 
 
 Re: Комбинаторика (количество пар множеств, сумма)
Сообщение13.02.2014, 00:43 
Аватара пользователя
У меня выходит, что сумма равна не $0$, а $(-1)^{m+n}$.
Пусть, например, $m=2, n=2$.
Перечислю ненулевые $F_k$.

$F_2=1$:
$A=\{1,2\}, B=\{1, 2\}$

$F_3=6$:
$A=\{1,2\}, B=\{1,3\}$
$A=\{1,2\}, B=\{2,3\}$
$A=\{1,3\}, B=\{1,2\}$
$A=\{1,3\}, B=\{2,3\}$
$A=\{2,3\}, B=\{1,2\}$
$A=\{2,3\}, B=\{1,3\}$

$F_4=6$:
$A=\{1,2\}, B=\{3,4\}$
$A=\{1,3\}, B=\{2,4\}$
$A=\{1,4\}, B=\{2,3\}$
$A=\{2,3\}, B=\{1,4\}$
$A=\{2,4\}, B=\{1,3\}$
$A=\{3,4\}, B=\{1,2\}$

Но $1-6+6=1$. :-(

Вообще, $F_k=C_k^m C_m^{k-m}$. Ненулевые значения $F_k$ будут для $\max(m, n)\leqslant k \leqslant m+n$.

 
 
 
 Re: Комбинаторика (количество пар множеств, сумма)
Сообщение13.02.2014, 06:54 
svv в сообщении #825767 писал(а):
У меня выходит, что сумма равна не $0$, а $(-1)^{m+n}$.
svv в сообщении #825767 писал(а):
Вообще, $F_k=C_k^m C_m^{k-m}$.
У меня вышло $F_k=\binom{k}{m}\binom{m+1}{m+n-k}$, и в результате сумма при $m,n\geqslant 1$ для проверенных мной нескольких случае получилась равной нулю.
А, Вы, видимо, упустили, что элементы $B$ м.б. равными нулю.

маткиб в сообщении #825728 писал(а):
хотя я решение знаю.
А как Вы решали?

маткиб в сообщении #825728 писал(а):
Да, через конечную разность красиво получается.
Насчет конечной разности - я проверю еще, ночью решал, такое ощущение, что наврал.
маткиб в сообщении #825728 писал(а):
Но, всё-таки, это не "учебное" решение
Есть такая книжка Грэхем, Кнут, Паташник Конкретная математика. Там есть куча стандартных приемов для вычисления сумм с биномиальными коэффициентами. Такое, конечно, не проходят, на сами приемы довольно простые :roll:

 
 
 
 Re: Комбинаторика (количество пар множеств, сумма)
Сообщение13.02.2014, 14:30 
Аватара пользователя
Sonic86 в сообщении #825795 писал(а):
А, Вы, видимо, упустили, что элементы $B$ м.б. равными нулю.

Совершенно верно! Упустил.

Но тогда элемент $0$ всегда принадлежит множеству $B$ (но не $A$), а разве это не равносильно просто изменению $|B|$ на $1$? Т.е. в моем примере считайте, что $n=3$ и допишите к каждому множеству $B$ ещё элемент $0$. Как это изменит сумму?

 
 
 
 Re: Комбинаторика (количество пар множеств, сумма)
Сообщение13.02.2014, 14:33 
Sonic86 в сообщении #825795 писал(а):
А как Вы решали?


Сначала представляем значение выражения как
$\sum_{A,B,k} (-1)^k$
где суммирование ведётся только по тройкам, удовлетворяющим условию. Все эти тройки разделим на группы следующим образом: для $A,B,k$ находим максимальное $r$, такое, что $|B\cap \{0,1,\ldots,r\}|=1$, вектор
$(I_{p+1\in A},I_{p+2\in A},\ldots,I_{k\in A};\ I_{p+1\in B},I_{p+2\in B},\ldots,I_{k\in B})$
объявляем кодом группы ($I$ означает индикатор). Суммирование внутри одной группы сводится к исходной задаче для $n=1$, а она решается элементарно, хоть в лоб (если расписать через биномиальные коэффициенты, получается разность двух одинаковых чисел). При этом может получиться $m=0$, но в этом случае утверждение тоже верно.

-- Чт фев 13, 2014 15:35:27 --

Sonic86 в сообщении #825795 писал(а):
Есть такая книжка Грэхем, Кнут, Паташник Конкретная математика. Там есть куча стандартных приемов для вычисления сумм с биномиальными коэффициентами. Такое, конечно, не проходят, на сами приемы довольно простые

Ну если конкретную математику учебником считать, то тут очень далеко уйти можно...

 
 
 
 Re: Комбинаторика (количество пар множеств, сумма)
Сообщение13.02.2014, 14:37 
Аватара пользователя
Вопрос снят. Опять не заметил, что $\{1,\ldots,k\}\subseteq A\cup B$, т.е. 0 не обязан кому-то принадлежать.

 
 
 
 Re: Комбинаторика (количество пар множеств, сумма)
Сообщение13.02.2014, 14:41 
Ещё можно тупо выписать рекуррентное соотношение, обрезая k-ый элемент, опять же сводим задачу к задаче меньшего размера, пока не дойдём до $n=1$.

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


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