багатьох завданнях. Наприклад, нехай є сантиметрова стрічка (В«кравецькі метрВ») довжиною п + 1 см, яку треба розрізати на шматочки довжиною 1 см. Причому ріжуть її, заощаджуючи зусилля. На першому кроці проводять розріз в деякому місці. На другому кроці намічають місця розрізів двох отриманих частин, накладають їх один на одного відповідним чином і одним помахом ножиць проводять розріз. На третьому кроці так само розрізають отримані чотири частини і т. д. (якщо яка-небудь частина має довжину 1 см, то вона не піддається подальшим розрізах). Наприклад, якщо від стрічки довжиною 2k см кожен раз відрізати 1 см, то буде потрібно 2k-1 розрізів, а якщо різати все отримувані частини навпіл, то вистачить k розрізів. p> Можна довести, що число В n таких процесів, що закінчуються розрізанням стрічки на п + 1 сантиметрових шматочків, одно Т n (два процеси вважаються різними, якщо хоча б на одному кроці вони призводять до різних результатів). Доказ засноване на тому, що процеси розрізання представляють у вигляді об'єднання п класів, де в s-й клас потрапляють розрізання, при яких на першому кроці ліва частина має довжину s см. Це відразу призводить до рекурентному співвідношенню для В n , збігається з співвідношенням (3) для Т n . Так як, крім того, B0 = T0 = 1, то для всіх п маємо:
B n = T n = .
2. Черги і властивості поєднань
Виведені в попередніх пунктах формули дозволяють встановити подальші властивості числа сполучень С.
. Розіб'ємо на класи всі несприятливі перестановки з т букв "р" і k букв В«пВ» - за яких чергу в касу затримується. Віднесемо до s-му класу всі перестановки, для яких затримка вперше відбувається на місці 2s + 1, тоді перед ним стоїть s букв "р" і s букв В«пВ», на ньому стоїть буква В«рВ», а черга аж до цього місця проходить без затримки.
Ясно, що s може приймати значення 0, 1, 2, ..., т - 1. Знайдемо, скільки перестановок входить до s-й клас. На перших 2s місцях можуть стояти будь сприятливі перестановки з s букв "р" і s букв В«пВ» - адже до місця 2s + 1 черга не зупиняється. Як ми бачили, число таких перестановок одно. Далі, на місці 2s + 1 стоїть буква "р", а після неї - будь-яка перестановка залишилися т - s - 1 літер В«рВ» і k - s букв В«пВ». Число цих перестановок дорівнює
P (m-s-1, k-s) =
Таким чином, в силу правила твори число несприятливих перестановок s-гo класу одно
Оскільки загальне число несприятливих перестановок одно C k , а число класів одно т - 1, то отримуємо при т співвідношення
(4)
Це співвідношення є окремим випадком ф...
