スターリング数
手順1として、要素 n − 1 {\displaystyle n-1} 個をグループ k − 1 {\displaystyle k-1} 個に分割し、 n {\displaystyle n} 番目の要素を k {\displaystyle k} 番目のグループとして単独で追加すればよい。手順2として、要素 n − 1 {\displaystyle n-1} 個をグループ k {\displaystyle k} 個に分割し、 n {\displaystyle n} 番目の要素を k {\displaystyle k} 個のグループのどれかに挿入する。手順1で構成される組み合わせの数は、要素 n − 1 {\displaystyle n-1} 個をグループ k − 1 {\displaystyle k-1} 個に分割する組み合わせの数に等しい。手順2で構成される組み合わせの数は、要素 n − 1 {\displaystyle n-1} 個をグループ k {\displaystyle k} に分割する組み合わせの数の k {\displaystyle k} 倍に等しい。したがって、手順1と手順2で構成される組み合わせの和として、求める組み合わせの数は第2種スターリング数の漸化式で与えられる。要素 n {\displaystyle n} 個をグループ k {\displaystyle k} 個に分割する組み合わせは、第2種スターリング数 { n k } {\displaystyle \{{\textstyle {n \atop k}}\}} で与えられる。
この考え方を一般化し、 n {\displaystyle n} 個の要素から 巡回列 k {\displaystyle k} 個を作るには、手順1として、 n − 1 {\displaystyle n-1} 個の要素から 巡回列 k − 1 {\displaystyle k-1} 個を作った後、 k {\displaystyle k} 番目の巡回列として n {\displaystyle n} 番目の要素を単独で追加する。その組み合わせの数は、 n − 1 {\displaystyle n-1} 個の要素から 巡回列 k − 1 {\displaystyle k-1} 個を作る組み合わせの数に等しい。手順2として、 n − 1 {\displaystyle n-1} 個の要素から巡回列 k {\displaystyle k} 個を作った後、 n {\displaystyle n} 番目の要素を既存の巡回列に挿入する。その組み合わせの数は、 n − 1 {\displaystyle n-1} 個の要素から 巡回列 k {\displaystyle k} 個を作る組み合わせの数を n − 1 {\displaystyle n-1} 倍した値となる。手順1と手順2の組み合わせの和であることを考えると、 n {\displaystyle n} 個の要素から 巡回列 k {\displaystyle k} 個を作る組み合わせの数は第1スターリング数の漸化式で与えられることがわかる。したがって、その組み合わせの数は第1スターリング数 [ n k ] {\displaystyle [{\textstyle {n \atop k}}]} に等しい。