スターリング数
[ ( 0 ) , ( 1 , 2 , 3 ) ] , [ ( 1 ) , ( 0 , 2 , 3 ) ] , [ ( 2 ) , ( 0 , 1 , 3 ) ] , [ ( 3 ) , ( 0 , 1 , 2 ) ] , [ ( 0 , 1 ) , ( 2 , 3 ) ] , [ ( 0 , 2 ) , ( 1 , 3 ) ] , [ ( 0 , 3 ) , ( 1 , 2 ) ] {\displaystyle {\begin{array}{llll}{}[(0),(1,2,3)],&[(1),(0,2,3)],&[(2),(0,1,3)],&[(3),(0,1,2)],\\{}[(0,1),(2,3)],&[(0,2),(1,3)],&[(0,3),(1,2)]\end{array}}}
上で列挙した要素4個をグループ2個に分割する組み合わせは、次のように構成することもできる。手順1として、要素3個をグループ1個に分割し、4番目の要素を第2のグループとして単独で追加する。手順2として、要素3個をグループ2個に分割し、4番目の要素をどちらかのグループに挿入する。手順1で構成される組み合わせは、要素3個をグループ1個に分割する組み合わせの数:1通りに等しい。手順2で構成される組み合わせは、要素3個をグループ2個に分割する組み合わせの数:3通りに対して、4番目の要素を2つのグループのどちらかに挿入する組み合わせ(2 通り)があるので、全部で6通りである。手順1と手順2による組み合わせの和は7通りとなり、上で列挙した組み合わせの数と一致する。
これを一般化して、要素 n {\displaystyle n} 個をグループ k {\displaystyle k} 個に分割するには、次の2つの手順で組み合わせを作ればよい。
[ ( 0 ) , ( 1 , 2 , 3 ) ] , [ ( 0 ) , ( 1 , 3 , 2 ) ] , [ ( 1 ) , ( 0 , 2 , 3 ) ] , [ ( 1 ) , ( 0 , 3 , 2 ) ] [ ( 2 ) , ( 0 , 1 , 3 ) ] , [ ( 2 ) , ( 0 , 3 , 1 ) ] , [ ( 3 ) , ( 0 , 1 , 2 ) ] , [ ( 3 ) , ( 0 , 2 , 1 ) ] [ ( 0 , 1 ) , ( 2 , 3 ) ] , [ ( 0 , 2 ) , ( 1 , 3 ) ] , [ ( 0 , 3 ) , ( 1 , 2 ) ] {\displaystyle {\begin{array}{llll}{}[(0),(1,2,3)],&[(0),(1,3,2)],&[(1),(0,2,3)],&[(1),(0,3,2)]\\{}[(2),(0,1,3)],&[(2),(0,3,1)],&[(3),(0,1,2)],&[(3),(0,2,1)]\\{}[(0,1),(2,3)],&[(0,2),(1,3)],&[(0,3),(1,2)]\end{array}}}
上で説明した直接的な順列の作り方のほかに、4個の要素から巡回列2個を作る方法として次の手順を考える。手順1として、3個の要素から巡回列1個を作り、4番目の要素を単独要素の巡回列として追加する。手順2として、3個の要素から巡回列2個を作り、4番目の要素を既に作られた巡回列に追加する。手順1では、3個の要素から巡回列を作る組み合わせとして2通りが可能である。手順2では、3個の要素から巡回列2個を作る組み合わせが3通りある。さらに、4番目の要素を既存の巡回列に挿入する組み合わせは3通りずつあるので、手順2による組み合わせは9通りとなる。よって、手順1と手順2による組み合わせの合計として11通りになる。