Комбинаторика (количество пар множеств, сумма)

[маткиб]

Даны натуральные числа $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 $

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

[Sonic86]

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

[маткиб]

Зачем-то переместили в "Помогите решить, разобраться", т.е., вместо красивых разных способов решения будут только подсказки, чтобы я решил, хотя я решение знаю.

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

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

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

Sonic86 в сообщении #825720 писал(а):

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

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

[svv]

У меня выходит, что сумма равна не $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$.

[Sonic86]

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 писал(а):

Но, всё-таки, это не "учебное" решение

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

[svv]

Sonic86 в сообщении #825795 писал(а):

А, Вы, видимо, упустили, что элементы $B$ м.б. равными нулю.

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

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

[маткиб]

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 писал(а):

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

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

[svv]

Вопрос снят. Опять не заметил, что $\{1,\ldots,k\}\subseteq A\cup B$, т.е. 0 не обязан кому-то принадлежать.

[маткиб]

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