2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3
 
 Re: Комбинаторные штучки
Сообщение05.12.2010, 14:27 
Хочу разложить в ряд производящую функцию $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$-кратной свёртке.

 
 
 
 Re: Комбинаторные штучки
Сообщение05.12.2010, 14:40 
Аватара пользователя
arseniiv
Бином Ньютона: $=\sum\limits_{k\ge 0} \binom{-n}k (-1)^k x^{2k}$, где $\binom{-n}k=(-1)^k \binom{n+k-1}k$.

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

Вот ещё задача на принцип включения-исключения. Простые задачи, где явно видно, как его применить, у меня выходят, а вот чуть сложнее — начинаются длинные пересечения-объединения, а толку всё никакого. В конце концов, рука устаёт, а голова в замешательстве. Может, меня наставят на путь истинный с этой задачей (вдруг до меня наконец дойдёт принцип правильного применения этого принципа).
Переведу условие сразу во множества, чтоб не писать много букв. Для всех $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 --

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

 
 
 
 Re: Комбинаторные штучки
Сообщение05.12.2010, 22:30 
Аватара пользователя
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$, но т. к. вы его как ПФ рассматриваете, то на это можно плюнуть.)

 
 
 
 Re: Комбинаторные штучки
Сообщение06.12.2010, 00:55 
Аватара пользователя

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

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

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

 
 
 
 Re: Комбинаторные штучки
Сообщение06.12.2010, 07:47 
arseniiv в сообщении #383965 писал(а):
А как это получить?

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

 
 
 
 Re: Комбинаторные штучки
Сообщение06.12.2010, 20:48 
:oops:

 
 
 
 Re: Комбинаторные штучки
Сообщение07.12.2010, 15:24 
Хояу найти число $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)$? Вроде бы дифференцирование и интегрирование не помогают.

 
 
 
 Re: Комбинаторные штучки
Сообщение07.12.2010, 15:57 
Аватара пользователя
Тут не будет красиво.

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


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