Задача
COM-B2-M02-P015 Рекурсия для беспорядков
#15
★★★★☆ Уровень 4 из 5
Докажите рекурсию \(D_n=(n-1)(D_{n-1}+D_{n-2})\) для \(n\ge2\).
Посмотрите, куда переходит элемент \(1\), и что происходит с элементом, попавшим на место \(1\).
В беспорядке элемент \(1\) переходит на место \(j\ne1\), \(n-1\) вариантов. Рассмотрим элемент \(j\). Если \(j\) переходит на место \(1\), то остальные \(n-2\) элементов образуют беспорядок: \(D_{n-2}\) способов. Если \(j\) не переходит на место \(1\), то после объединения мест \(1\) и \(j\) задача сводится к беспорядку \(n-1\) элементов: \(D_{n-1}\) способов. Итого \(D_n=(n-1)(D_{n-1}+D_{n-2})\).
Это не включения-исключения, но важно для темы беспорядков.