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

[arseniiv]

Вот я нахожу замкнутое выражение для чисел Каталана. (1) Как сразу понять, минус или плюс (знаю, что минус) в формуле для производящей функции (ведь из уравнения для неё получаем $C(z) = \frac{1 \pm \sqrt{1 - 4z}}{2z}$)? (2) Как разложить её в ряд? Ряд Маклорена, очевидно, невозможно получить. А что тогда делать? (Мы это писали на лекции, но я ничего не увидел, а на слух не понял).
Может, ещё будут вопросы…

А, ну да. (3) Как разложить в ряд $(z + z^2 + z^3 + \ldots)^n = \frac{z^n}{(1 - z)^n}$?

[Хорхе]

(1) минус по ряду причин, подумайте почему
(2) почему невозможно, и к тому же очевидно? Разложите числитель и поделите на $z$, вот и все.
(3) разложите $(1-z)^{-n}$, это несложно.

[arseniiv]

Хорхе в сообщении #372466 писал(а):

(1) минус по ряду причин, подумайте почему

Так-то понятно, что будут не числа Каталана получаться, а что-то знакопеременное, но как наиболее быстро к этому прийти? Что именно использовать?

Хорхе в сообщении #372466 писал(а):

(2) почему невозможно, и к тому же очевидно? Разложите числитель и поделите на $z$, вот и все.

Ой. Всё время об этом забываю!

Хорхе в сообщении #372466 писал(а):

(3) разложите $(1-z)^{-n}$, это несложно.

Вот и тут о том, что множитель $z^n$ можно временно убрать, забыл. Пытался общее выражение для производной в целом найти. А так, конечно, проще! Получилось $\sum_{k = 0}^\infty {(-1)^k C_n^k z^{n + k}}$. Правильно?

[Zealint]

Вы же знаете, где искать ответ. Для чего писал?

[arseniiv]

Ой, ведь недавно заглядывал и забыл.

[Хорхе]

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

Хорхе в сообщении #372466 писал(а):

(1) минус по ряду причин, подумайте почему

Так-то понятно, что будут не числа Каталана получаться, а что-то знакопеременное, но как наиболее быстро к этому прийти? Что именно использовать?

Самое простое в данном случае - конечность производящей функции в нуле. С плюсом она бесконечна. Кстати, получится что-то не знакопеременное, а все больше знакоотрицательное.

[arseniiv]

А как можно найти производящую функцию для последовательности $s_n$, задаваемой так:

$$\left\{\begin{array}{lll} s_0 = 0 \\ s_1 = 1 \\ s_{n + 1} = 2^{s_n} - 2^{s_{n - 1}} + s_n \end{array}\right.$$

[caxap]

(Оффтоп)

arseniiv
Зверская последовательность!

In[7]:= Table[s[n]//N,{n,1,6}]
                                                      19728
Out[7]= {1., 2., 4., 16., 65536., 2.003529930406846 10     }

[ewert]

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

Хорхе в сообщении #372466 писал(а):

(3) разложите $(1-z)^{-n}$, это несложно.

Вот и тут о том, что множитель $z^n$ ожно временно убрать, забыл. Пытался общее выражение для производной в целом найти. А так, конечно, проще! Получилось $\sum_{k = 0}^\infty {(-1)^k C_n^k z^{n + k}}$. Правильно?

Нет. Во-первых: откуда там знакочередование-то возьмётся?... А во-вторых, и таких "Це" не бывает -- хотя бы потому, что у Вас же там будет получаться в т.ч. и $k>n$.

[Someone]

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

А как можно найти производящую функцию для последовательности $s_n$, задаваемой так:

$$\left\{\begin{array}{lll} s_0 = 0 \\ s_1 = 1 \\ s_{n + 1} = 2^{s_n} - 2^{s_{n - 1}} + s_n \end{array}\right.$$

Проще говоря,

$$s_n=\begin{cases}0\text{, если }n=0\text{,}\\ 2^{s_{n-1}}\text{, если }n>0\text{.}\end{cases}$$

То есть, при $n>1$

$$s_n=2^{2^{2^{.^{.^{.^2}}}}}$$

(всего $n-1$ двоек).

[arseniiv]

Вот каким именно образом вы это вывели? Не пойму…

[EtCetera]

Индукция...

[arseniiv]

(Оффтоп)

caxap в сообщении #374978 писал(а):

arseniiv
Зверская последовательность!

In[7]:= Table[s[n]//N,{n,1,6}]
                                                      19728
Out[7]= {1., 2., 4., 16., 65536., 2.003529930406846 10     }

Это частичные суммы количества [наследственно-конечных] множеств ранга $n$ (который в общем ординал) (или сдвинутых на $1$ в какую-то сторону для удобства, щас не пойму). В общем-то, я уже тут в другой теме и в OEIS узнал, как вычислять, но так пока и не узнал, как к этому приходить.
А ещё интересно, можно ли обойтись без тетрации.

-- Вс ноя 14, 2010 18:43:36 --

EtCetera в сообщении #375016 писал(а):

Индукция...

Насколько я понимаю, индукцией обычно доказывают какие-нибудь уже приготовленные в голове замеченные предположения, а если их нет, как тогда?

[EtCetera]

arseniiv

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

а если их нет

надо посчитать несколько первых членов и заметить в них некую закономерность. В данном случае это очень просто.

[arseniiv]

Someone в сообщении #374995 писал(а):

То есть, при $n>1$

$$s_n=2^{2^{2^{.^{.^{.^2}}}}}$$

(всего $n-1$ двоек).

Кстати, можно ведь ещё так написать: $s_n = 2^{.^{.^{.^{2^0}}}}$, где двоек $n$, и справедливо для $n = 0$ или $1$ тоже.

EtCetera, но ведь это только в данном! К тому же у меня сообразить без других бы здесь не вышло. Наверно.