Рекуррентное соотношение

Dakota · Сообщение **Dakota** » 16 янв 2012, 18:38

Телефонная станция на n абонентов имеет возможность соединять абонентов только попарно. Необходимо проверить следующее рекуррентное соотношение:
$T_{n+1} (t) = T_n (t) + ntT_{n-1}(t)$ , где $T_{n} (t)$ - производящая функция числа соединений.
Подскажите план действий. Заранее спасибо.

Sonic86 · Сообщение **Sonic86** » 16 янв 2012, 18:46

А вроде бы очевидно. Просто попробуйте в лоб рассуждать.
Я начну: пусть число способов соединения $$k$$

из

абонентов равно $$[t^k]T_n(t)$$

(это так в Кнуте обозначается коэффициент в ПФ при $$t^k$$

). Добавим $$n+1$$

-го абонента. Ищем $[t^k]T_{n+1}(t)$ . $$n+1$$

-й абонент либо входит в $$k$$

соединяемых абонентов, либо не входит. Если не входит, то получаем $$[t^k]T_n(t)$$

соединений $$k$$

абонентов из $$n$$

, т.е. $[t^k]T_{n+1}(t)=[t^k]T_{n}(t)+$ еще что-то. 2-й случай должен давать 2-е слагаемое - попробуйте.

Dakota · Сообщение **Dakota** » 16 янв 2012, 19:14

Sonic86 писал(а):Source of the post
А вроде бы очевидно. Просто попробуйте в лоб рассуждать.
Я начну: пусть число способов соединения из абонентов равно (это так в Кнуте обозначается коэффициент в ПФ при ). Добавим -го абонента. Ищем $[t^k]T_{n+1}(t)$ . -й абонент либо входит в соединяемых абонентов, либо не входит. Если не входит, то получаем соединений абонентов из , т.е. $[t^k]T_{n+1}(t)=[t^k]T_{n}(t)+$ еще что-то. 2-й случай должен давать 2-е слагаемое - попробуйте.

дальше значит так: если входит, то получаем $n[t^{k-1}]T_{n-1}(t)$ и подставляем всё это в ПФ?

Sonic86 · Сообщение **Sonic86** » 16 янв 2012, 19:15

Ну да.

yourdomain.com