Комбинаторные штучки

[arseniiv]

Хочу разложить в ряд производящую функцию $A(x) = (1 - x^2)^{-n}$. Знаю, что $(1 - x^2)^{-1} = \sum_{i = 0}^{\infty} {((i + 1) \bmod 2) x^i}$ производит последовательность $(1,\,0,\,1,\,0,\,\ldots)$. Только не знаю, что станет с коэффициентами ряда при $n$-кратной свёртке.

[caxap]

arseniiv
Бином Ньютона: $=\sum\limits_{k\ge 0} \binom{-n}k (-1)^k x^{2k}$, где $\binom{-n}k=(-1)^k \binom{n+k-1}k$.

[arseniiv]

А как это получить? Вечно у меня голова не соображает сама, более того, ещё со школы она научилась зачем-то решать задачи в какую-то обратную сторону. Очевидное только подтвердить, но никак не увидеть может.

Вот ещё задача на принцип включения-исключения. Простые задачи, где явно видно, как его применить, у меня выходят, а вот чуть сложнее — начинаются длинные пересечения-объединения, а толку всё никакого. В конце концов, рука устаёт, а голова в замешательстве. Может, меня наставят на путь истинный с этой задачей (вдруг до меня наконец дойдёт принцип правильного применения этого принципа).
Переведу условие сразу во множества, чтоб не писать много букв. Для всех $1 \leqslant i \leqslant 5$ $A_i \subset A$, $|A_i| = 48$, $|A| = 96$. Найти мощность множества $\left\{a\ |\ \forall_{i \ne j \ne k} \left(a \in A_i \cap A_j \cap A_k \right) \right\}$ элементов, содержащихся хотя бы в трёх из пяти заданных множеств (пояснил, потому что не уверен, что правильно записал).

-- Вс дек 05, 2010 22:25:11 --

Я выписывал всевозможные объединения, но ничего не нашёл. Набирать их сюда нет смысла, и так лист исписал.

-- Вс дек 05, 2010 22:28:13 --

Про бином до меня только что всё же дошло. А как расписать его, если мы не вводили на лекциях расширенные биномиальные коэффициенты? (Мне, по крайней мере, так кажется.)

[caxap]

arseniiv в сообщении #383965 писал(а):

А как это получить?

Бином Ньютона -- это формула Тейлора для $f(x)=(1+x)^r$, $r\in \mathbb R$. В окрестности нуля будет $f(x)=\sum\limits_{k\ge 0}\dfrac{f^{(k)}(0)}{k!}x^k$, но $f'(x)=r(1+x)^{r-1}$, $f''(x)=r(r-1)(1+x)^{r-2}$, ..., $f^{(k)}(x)=r^{\underline{k}}(1+x)^{r-k}$ (тут $r^{\underline k}:=r(r-1)\cdots(r-k+1)$ -- нижняя факториальная степень). То есть получаем $(1+x)^r=\sum\limits_{k\ge 1} \dfrac{r^{\underline{k}}}{k!} x^k$. А за биномиальный коэффициент просто по определению можно принять $\binom{r}{k}:=r^{\underline{k}}/{k!}$ для любого $r\in\mathbb R$. В частности, для целого положительного $r$ будет $\binom{-r}k=(-1)^k \binom{r+k-1}k$ (в Конкретной Математике эта формула называется обращением верхнего индекса).

-- 05 дек 2010, 22:34 --

(Ряд сходится только для $|x|<1$, но т. к. вы его как ПФ рассматриваете, то на это можно плюнуть.)

[caxap]

(Мысли вслух)

arseniiv в сообщении #383965 писал(а):

Найти мощность множества...

Ну в таких задачах, где подразумевается, что а) данных достаточно и б) решение существует, ответ найти очень просто, взяв самую простую ситуацию и посчитав ответ. Напр. когда $A_1=A_2=A_3=A_4\neq A_5$. Тогда, разумеется, ответ -- $48$. Осталось доказать. Например, можно попытаться показать, что $m\ge 48$ и $m\le 48$ ($m$ -- искомая мощность), возможно, от противного.

Хотя лично у меня в голове образ такой возник (и не знаю как описать даже): предположим сначала, что $A_1=A_2=A_3\neq A_4= A_5$ (как будто лежат друг на дружке $3$ карты слева, а справа ещё $2$. Длина каждой карты -- $48$, а всей конструкции -- $96$), тут $m=48$. Теперь изменяем множество $A_1$ (сдвигаем верхнюю карту из левой стопки, возможно, разрезая её поперёк на части). Видно, что сколько убывает с одной стороны, столько же и прибывает с другой, т. е. от изменения $A_1$ суммарная длина участков, где друг на дружке лежат три слоя карт ($m$) не меняется. Следуя тем же макаром, можно постепенно показать, что не только $A_1$, но и вообще любые карты можно по разному двигать, при этом $m$ остаётся $48$.

Ой и сумбурно написал. Но это я к тому, что у такой задачи наверняка есть какое-то элементарное решение на уровне школьника.

[Zealint]

arseniiv в сообщении #383965 писал(а):

А как это получить?

Вы будете удивлены, но ответ все тут же.

[arseniiv]

[arseniiv]

Хояу найти число $r_n$ единиц в двоичной записи числа $n$. Получилось
$\left\{\begin{array}{l} r_{2n} = r_n \\ r_{2n + 1} = r_n \\ r_0 = 0 \end{array}\right.$.
Для производящей функции получилось уравнение $R(z) = (z + 1)R(z^2) + z(1 - z^2)^{-1}$. Можно отсюда как-то выразить $R(z)$? Вроде бы дифференцирование и интегрирование не помогают.

[ИСН]

Тут не будет красиво.