組み合わせ数学における意味
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/20 06:25 UTC 版)
「スターリング数」の記事における「組み合わせ数学における意味」の解説
第1種スターリング数 [ n k ] {\displaystyle [{\textstyle {n \atop k}}]} は、組合せ数学において、 n {\displaystyle n} 個の要素を k {\displaystyle k} 個の巡回列に分割する組み合わせの数を与える。巡回列は山手線の駅のように繰り返される要素を示したデータ列である。ここでは、巡回列を ( 0 , 2 , 1 , 3 ) {\displaystyle (0,2,1,3)} のように書こう。この場合、0, 2, 1, 3の順に数値が繰り返される場合を意味する。巡回列の場合、順列ではあるが ( 0 , 2 , 1 , 3 ) {\displaystyle (0,2,1,3)} と ( 2 , 1 , 3 , 0 ) {\displaystyle (2,1,3,0)} のように要素を巡回置換した巡回列どうしは同一とみなす。したがって、 n {\displaystyle n} 個の要素で構成される巡回列の組み合わせは ( n − 1 ) ! {\displaystyle (n-1)!} 通りである。 また、 ( 1 ) {\displaystyle (1)} は1個の要素で構成される巡回列であると考える。 例として4個の要素を巡回列2個に分割する組み合わせを考えよう そのような分割においては、構成要素が1個と3個の巡回列に分割する組み合わせと、構成要素が2個と2個の巡回列に分割する組み合わせがある。前者の分割法では、4個の要素から、単独で巡回列をなす要素1個を選び、残りの3個の要素で巡回列を作る組み合わせを考えればよい。 要素4個から1個を選ぶ組み合わせは4通りであり、3個の要素から巡回列を作る組み合わせは2通りである。したがって、前者の分割法による組み合わせは全部で8通りとなる。後者については、4個の要素から巡回列をなす2個を選び、それぞれ2個の巡回列の組み合わせを考えればよい。 要素4個から2個を選ぶのは6通りの組み合わせがあり、2個の要素が巡回列は1通りしかない。しかし、得られる2個の巡回列は同一構造の巡回列なので、6通りの組み合わせからその自由度を補正する必要がある。つまり、2分の1するということであり、後者の分割法による組み合わせは3通りである。つまり、4個の要素を巡回列2個に分割する組み合わせは全部で11通りとなる。この数値は [ 4 2 ] {\displaystyle [{\textstyle {4 \atop 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通りになる。 この考え方を一般化し、 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}}]} に等しい。
※この「組み合わせ数学における意味」の解説は、「スターリング数」の解説の一部です。
「組み合わせ数学における意味」を含む「スターリング数」の記事については、「スターリング数」の概要を参照ください。
組み合わせ数学における意味
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/20 06:25 UTC 版)
「スターリング数」の記事における「組み合わせ数学における意味」の解説
第2種スターリング数 { n k } {\displaystyle \{{\textstyle {n \atop k}}\}} は、組合せ数学において、番号づけされた n {\displaystyle n} 個の要素をグループ k {\displaystyle k} 個に分割する組み合わせの数を与える。 分割する要素は番号付けされているので個別に区別できるが、グループは順序を特に区別しないものとする。 選択された要素を ( 0 , 2 , 3 ) {\displaystyle (0,2,3)} と書いた場合、 ( 0 , 3 , 2 ) {\displaystyle (0,3,2)} のように要素を置換した列も同一であるとみなす。分割されたグループに含まれる要素の数は均等である必要はなく、1個の要素しか含まないグループがあってもよいとする。 要素4個をグループ2個に分割するには、要素が1個と3個のグループに分割する場合と、要素が2個と2個のグループに分割する組み合わせが挙げられる。 前者の分割法では、要素4個から単独グループをなす要素1個を選ぶ組み合わせ、すなわち、4通りだけが存在する。後者の分割法では、要素4個から一方のグループを構成する2個を選ぶ組み合わせを考えればよい。その組み合わせは6通りあるのだが、分割される双方のグループが要素2個で構成されることから、グループ間に対称性がある。その対称性から2の自由度がある。その自由度を補正すると、後者の分割法は3通りの組み合わせがあることになる。したがって、要素 0, 1, 2, 3 をグループ2個に分割する組み合わせは、全部で以下の7通りがある。 [ ( 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つの手順で組み合わせをつくればよい。 手順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}}\}} で与えられる。
※この「組み合わせ数学における意味」の解説は、「スターリング数」の解説の一部です。
「組み合わせ数学における意味」を含む「スターリング数」の記事については、「スターリング数」の概要を参照ください。
- 組み合わせ数学における意味のページへのリンク
