順列の転位                                戻る

  ある地方では、年齢順に結婚しなければならないという慣習があるという。

 その地方のある家庭には、5人の未婚の娘さんがいた。

 1人の娘さんが結婚する毎に、未婚の姉はそれぞれ「慣習が破られた!」と不満を

 もらした。娘5人がすべて結婚するまで、父は、合計5回不満を聞いたという。

  5人の娘さんたちは、どのような順番で結婚していったのだろうか?


 この場合の数は、かなりたくさんありそう...。

 例えば、娘さんを年齢の高い方から、「1、2、3、4、5」とすると、問題の条件を満たす場
合として、
       3、2、4、5、1

がある。「3」が結婚するときは、「1」と「2」が不満をもらし、「2」が結婚するときは、「1」が
不満をもらす。そして、「4」「5」が結婚するときも、それぞれ「1」が不満をもらす。
 以上の計5回の不満をお父さんは聞くことになるわけだ。


 冒頭の問題を一般化すれば、順列における転位数の問題となる。

 自然数 1、2、3、・・・、n に対して、その任意の順列 σ を

  σ(1)、σ(2)、σ(3)、・・・、σ(n)

とする。このとき、

   x<y に対して、 σ(x)>σ(y)

であるとき、「転位がある」と言われる。

 1つの順列において、転位がある組の数を、転位数(転倒数)という。

例 (1) 1、2、3 ・・・ 転位数は、「0」

   (2) 2、3、1 ・・・ (2,1)と(3,1)の2組あるので、転位数は、「2」

   (3) 3、2、1 ・・・ (2,1)と(3,1)と(3,2)の3組あるので、転位数は、「3」

 転位数が偶数の順列を「偶順列」、転位数が奇数の順列を「奇順列」という。

例 順列 3、1、4、2 の転位数は、「3」である。

  実際に、転位がある組が、(3,1)と(3,2)と(4,2)の3組あるからである。

 あみだくじを考えると、この転位数の概念が理解される。

           転位数は、左図における線分の

   交差数に等しい。

練習問題 順列 6、5、3、2、1、4 の転位数を求めよ。   (答え:12)


 順列 σ の転位数が r のとき、(−1) を順列の符号といい、sgn(σ)と表す。

    sgn(σ)=(−1)


 冒頭の問題について、1、2、3、4、5 の全順列を考え、転位数を計算してみた。

順列 転位がある組 転位数
12345   0
12354 (4,5) 1
12435 (3,4) 1
12453 (3,4),(3,5) 2
12534 (3,5),(4,5) 2
12543 (3,4),(3,5),(4,5) 3
13245 (2,3) 1
13254 (2,3),(4,5) 2
13425 (2,3),(2,4) 2
13452 (2,3),(2,4),(2,5) 3
13524 (2,3),(2,5),(4,5) 3
13542 (2,3),(2,4),(2,5),(4,5) 4
14235 (2,4),(3,4) 2
14253 (2,4),(3,4),(3,5) 3
14325 (2,3),(2,4),(3,4) 3
14352 (2,3),(2,4),(2,5),(3,4) 4
14523 (2,4),(2,5),(3,4),(3,5) 4
14532 (2,3),(2,4),(2,5),(3,4),(3,5) 5
15234 (2,5),(3,5),(4,5) 3
15243 (2,5),(3,4),(3,5),(4,5) 4
15324 (2,3),(2,5),(3,5),(4,5) 4
15342 (2,3),(2,4),(2,5),(3,5),(4,5) 5
15423 (2,4),(2,5),(3,4),(3,5),(4,5) 5
15432 (2,3),(2,4),(2,5),(3,4),(3,5),(4,5) 6
21345 (1,2) 1
21354 (1,2),(4,5) 2
21435 (1,2),(3,4) 2
21453 (1,2),(3,4),(3,5) 3
21534 (1,2),(3,5),(4,5) 3
21543 (1,2),(3,4),(3,5),(4,5) 4
23145 (1,2),(1,3) 2
23154 (1,2),(1,3),(4,5) 3
23415 (1,2),(1,3),(1,4) 3
23451 (1,2),(1,3),(1,4),(1,5) 4
23514 (1,2),(1,3),(1,5),(4,5) 4
23541 (1,2),(1,3),(1,4),(1,5),(4,5) 5
24135 (1,2),(1,4),(3,4) 3
24153 (1,2),(1,4),(3,4),(3,5) 4
24315 (1,2),(1,3),(1,4),(3,4) 4
24351 (1,2),(1,3),(1,4),(1,5),(3,4) 5
24513 (1,2),(1,4),(1,5),(3,4),(3,5) 5
24531 (1,2),(1,3),(1,4),(1,5),(3,4),(3,5) 6
25134 (1,2),(1,5),(3,5),(4,5) 4
25143 (1,2),(1,5),(3,4),(3,5),(4,5) 5
25314 (1,2),(1,3),(1,5),(3,5),(4,5) 5
25341 (1,2),(1,3),(1,4),(1,5),(3,5),(4,5) 6
25413 (1,2),(1,4),(1,5),(3,4),(3,5),(4,5) 6
25431 (1,2),(1,3),(1,4),(1,5),(3,4),(3,5),(4,5) 7
31245 (1,3),(2,3) 2
31254 (1,3),(2,3),(4,5) 3
31425 (1,3),(2,3),(2,4) 3
31452 (1,3),(2,3),(2,4),(2,5) 4
31524 (1,3),(2,3),(2,5),(4,5) 4
31542 (1,3),(2,3),(2,4),(2,5),(4,5) 5
32145 (1,2),(1,3),(2,3) 3
32154 (1,2),(1,3),(2,3),(4,5) 4
32415 (1,2),(1,3),(1,4),(2,3) 4
32451 (1,2),(1,3),(1,4),(1,5),(2,3) 5
32514 (1,2),(1,3),(1,5),(2,3),(4,5) 5
32541 (1,2),(1,3),(1,4),(1,5),(2,3),(4,5) 6
順列 転位がある組 転位数
34125 (1,3),(1,4),(2,3),(2,4) 4
34152 (1,3),(1,4),(2,3),(2,4),(2,5) 5
34215 (1,2),(1,3),(1,4),(2,3),(2,4) 5
34251 (1,2),(1,3),(1,4),(1,5),(2,3),(2,4) 6
34512 (1,3),(1,4),(1,5),(2,3),(2,4),(2,5) 6
34521 (1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5) 7
35124 (1,3),(1,5),(2,3),(2,5),(4,5) 5
35142 (1,3),(1,5),(2,3),(2,4),(2,5),(4,5) 6
35214 (1,2),(1,3),(1,5),(2,3),(2,5),(4,5) 6
35241 (1,2),(1,3),(1,4),(1,5),(2,3),(2,5),(4,5) 7
35412 (1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(4,5) 7
35421 (1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(4,5) 8
41235 (1,4),(2,4),(3,4) 3
41253 (1,4),(2,4),(3,4),(3,5) 4
41325 (1,4),(2,3),(2,4),(3,4) 4
41352 (1,4),(2,3),(2,4),(2,5),(3,4) 5
41523 (1,4),(2,4),(2,5),(3,4),(3,5) 5
41532 (1,4),(2,3),(2,4),(2,5),(3,4),(3,5) 6
42135 (1,2),(1,4),(2,4),(3,4) 4
42153 (1,2),(1,4),(2,4),(3,4),(3,5) 5
42315 (1,2),(1,3),(1,4),(2,4),(3,4) 5
42351 (1,2),(1,3),(1,4),(1,5),(2,4),(3,4) 6
42513 (1,2),(1,4),(1,5),(2,4),(3,4),(3,5) 6
42531 (1,2),(1,3),(1,4),(1,5),(2,4),(3,4),(3,5) 7
43125 (1,3),(1,4),(2,3),(2,4),(3,4) 5
43152 (1,3),(1,4),(2,3),(2,4),(2,5),(3,4) 6
43215 (1,2),(1,3),(1,4),(2,3),(2,4),(3,4) 6
43251 (1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(3,4) 7
43512 (1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4) 7
43521 (1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4) 8
45123 (1,4),(1,5),(2,4),(2,5),(3,4),(3,5) 6
45132 (1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5) 7
45213 (1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5) 7
45231 (1,2),(1,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5) 8
45312 (1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5) 8
45321 (1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5) 9
51234 (1,5),(2,5),(3,5),(4,5) 4
51243 (1,5),(2,5),(3,4),(3,5),(4,5) 5
51324 (1,5),(2,3),(2,5),(3,5),(4,5) 5
51342 (1,5),(2,3),(2,4),(2,5),(3,5),(4,5) 6
51423 (1,5),(2,4),(2,5),(3,4),(3,5),(4,5) 6
51432 (1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5) 7
52134 (1,2),(1,5),(2,5),(3,5),(4,5) 5
52143 (1,2),(1,5),(2,5),(3,4),(3,5),(4,5) 6
52314 (1,2),(1,3),(1,5),(2,5),(3,5),(4,5) 6
52341 (1,2),(1,3),(1,4),(1,5),(2,5),(3,5),(4,5) 7
52413 (1,2),(1,4),(1,5),(2,5),(3,4),(3,5),(4,5) 7
52431 (1,2),(1,3),(1,4),(1,5),(2,5),(3,4),(3,5),(4,5) 8
53124 (1,3),(1,5),(2,3),(2,5),(3,5),(4,5) 6
53142 (1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5) 7
53214 (1,2),(1,3),(1,5),(2,3),(2,5),(3,5),(4,5) 7
53241 (1,2),(1,3),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5) 8
53412 (1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5) 8
53421 (1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5) 9
54123 (1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5) 7
54132 (1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5) 8
54213 (1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5) 8
54231 (1,2),(1,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5) 9
54312 (1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5) 9
54321 (1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5) 10

 上記の表から、自然数 1、2、3、・・・、n の順列に対して、n=5 のとき、転位数が5で
あるものの順列は、

  14532 、15342 、15423 、23541 、24351 、24513 、25143 、25314 、31542

  32451 、32514 、34152 、34215 、35124 、41352 、41523 、42153 、42315

  43125 、51243 、51324 、52134

の計22通りである。この22通りを計算で求めることは可能だろうか?

  (1,2) (1,3) (1,4) (1,5) (2,3) (2,4) (2,5) (3,4) (3,5) (4,5) 左右対称性
14532           タイプA
15342           タイプB
15423           タイプC
23541           タイプA
24351           タイプB
24513           タイプD
25143           タイプE
25314           タイプF
31542           タイプD
32451           タイプC
32514           タイプG
34152           タイプE
34215           タイプH
35124           タイプI
41352           タイプF
41523           タイプG
42153           タイプI
42315           タイプJ
43125           タイプK
51243           タイプH
51324           タイプJ
52134           タイプK

 単純に、10個の互換から5個選んでも、105=252(通り)なので、求める場合の数より
はるかに多い。

 順列は一つのあみだくじを作る。以下に列挙してみよう。ただし、一つの順列に対して、複
数のあみだくじが対応する可能性に注意しなければならない。したがって、あみだくじを用い
て、求める場合の数を得ることは困難だろう。

 あみだくじの上下の数字は省略してある。最上段の左側から、12345と並ぶ。

14532 15342 15423 23541 24351 24513 25143 25314
 
31542 32451 32514 34152 34215 35124 41352 41523
 
42153 42315 43125 51243 51324 52134


 当HPがいつもお世話になっているHN「FN」から、場合の数の求め方をご教示いただい
た。(平成23年8月1日付け)

 自然数 1、2、3、・・・、n の順列で、転位数が k であるものの個数を T( n ,k ) とする。

ただし、k は、0 以上で、2項係数 2=n(n−1)/2 以下である。

 T( n ,k )は次のようにして求めることができる。

n\k 10 11 12 13 14 15
                             
                           
                       
                 
15 20 22 20 15          
14 29 49 71 90 101 101 90 71 49 29 14

 n=1 のとき、転位は起こらないので、T( 1 ,0 )=1

 n=2 のとき、順列は、 12 または 21 なので、 T( 2 ,0 )=1 、T( 2 ,1 )=1

 n=3 のとき、順列は、 123 、132 、213 、231 、312 、321

  n=2 のときの順列を踏まえて、最後の数字「3」の入れ方により、次のように分類する。

 T( 3 ,0 ): 転位数が0なので、転位数が0の順列「12」の最後尾に「3」を入れる
        → 123

 よって、 T( 3 ,0 )=1

 T( 3 ,1 ): 転位数が1なので、転位数が1の順列「21」の最後尾に「3」を入れる
        → 213

 または、 転位数が0の順列「12」の最後尾から2番目になるように「3」を入れる
      → 132 (転位数が0から、+1増える)

 よって、 T( 3 ,1 )=2

 T( 3 ,2 ): 転位数が2なので、転位数が1の順列「21」の最後尾から2番目になるよう
        に「3」を入れる → 231 (転位数が1から、+1増える)

 または、 転位数が0の順列「12」の最後尾から3番目になるように「3」を入れる
      → 312 (転位数が0から、+2増える)

 よって、 T( 3 ,2 )=2

 T( 3 ,3 ): 転位数が3なので、転位数が1の順列「21」の最後尾から3番目になるよう
        に「3」を入れる → 321 (転位数が1から、+2増える)

 よって、 T( 3 ,3 )=1

 (自然数 1、2 の順列に3を添加する場合、転位数の増分は自然数 1、2 の個数2が限度である。

 このように考えると、

  T( 4 ,0 )=1 、T( 4 ,1 )=3 、T( 4 ,2 )=5 、T( 4 ,3 )=6 、

  T( 4 ,4 )=5 、T( 4 ,5 )=3 、T( 4 ,6 )=1

は、次のように機械的に求めることができる。

  T( 4 ,0 ): T( 3 ,0 )通りのそれぞれに対し、最後尾に「4」を入れる1通りのみ

    よって、 T( 4 ,0 )=T( 3 ,0 )=1

  T( 4 ,1 ): T( 3 ,1 )通りのそれぞれに対し、最後尾に「4」を入れる1通りのみ

    T( 3 ,0 )通りのそれぞれに対し、最後尾から2番目になるように「4」を入れる1通り
   のみ

 よって、 T( 4 ,1 )=T( 3 ,1 )+T( 3 ,0 )=2+1=3

  T( 4 ,2 ): T( 3 ,2 )通りのそれぞれに対し、最後尾に「4」を入れる1通りのみ

   T( 3 ,1 )通りのそれぞれに対し、最後尾から2番目になるように「4」を入れる1通り
  のみ

   T( 3 ,0 )通りのそれぞれに対し、最後尾から3番目になるように「4」を入れる1通り
  のみ

 よって、 T( 4 ,2 )=T( 3 ,2 )+T( 3 ,1 )+T( 3 ,0 )=2+2+1=5

  T( 4 ,3 ): T( 3 ,3 )通りのそれぞれに対し、最後尾に「4」を入れる1通りのみ

   T( 3 ,2 )通りのそれぞれに対し、最後尾から2番目になるように「4」を入れる1通り
  のみ

   T( 3 ,1 )通りのそれぞれに対し、最後尾から3番目になるように「4」を入れる1通り
  のみ

   T( 3 ,0 )通りのそれぞれに対し、最後尾から4番目になるように「4」を入れる1通り
  のみ

 よって、 T( 4 ,3 )=T( 3 ,3 )+T( 3 ,2 )+T( 3 ,1 )+T( 3 ,0 )

      =1+2+2+1=6

  T( 4 ,4 ): T( 3 ,3 )通りのそれぞれに対し、最後尾から2番目になるように「4」を
           入れる1通りのみ

   T( 3 ,2 )通りのそれぞれに対し、最後尾から3番目になるように「4」を入れる1通り
  のみ

   T( 3 ,1 )通りのそれぞれに対し、最後尾から4番目になるように「4」を入れる1通り
  のみ

 よって、 T( 4 ,4 )=T( 3 ,3 )+T( 3 ,2 )+T( 3 ,1 )=1+2+2=5

  T( 4 ,5 ): T( 3 ,3 )通りのそれぞれに対し、最後尾から3番目になるように「4」を
           入れる1通りのみ

   T( 3 ,2 )通りのそれぞれに対し、最後尾から4番目になるように「4」を入れる1通り
  のみ

 よって、 T( 4 ,5 )=T( 3 ,3 )+T( 3 ,2 )=1+2=3

  T( 4 ,6 ): T( 3 ,3 )通りのそれぞれに対し、最後尾から4番目になるように「4」を
         入れる1通りのみ

 よって、 T( 4 ,5 )=T( 3 ,3 )=1

 上記の計算の規則をみると、第行の値は、第3行の値を使って、真上の値を含めて、左
個の値を足せばよいことが分かる。

例 T( 4 ,3 )=1+2+2+1=6 、T( 5 ,5 )=3+5+6+5+3=22

 一般に、次の漸化式が成りつ。

  T( n+1 ,k )=T( n ,k )+T( n ,k−1 )+・・・+T(n ,k−n )

ただし、k<0 、k>2 のとき、T( n ,k )=0 とする。

(コメント) なるほど...今までのモヤモヤが雲散霧消しました!FNさんに感謝します。


 また、FNさんは、次の表も作られました。


0 1 2 3 4      0 1 2 3      0 1 2
1 2 3 4 5      1 2 3 4      1 2 3
1 2 3 4 5      1 2 3 4
2 3 4 5 6      2 3 4 5
2 3 4 5 6      2 3 4 5
3 4 5 6 7      3 4 5 6
1 2 3 4 5
2 3 4 5 6
2 3 4 5 6
3 4 5 6 7
3 4 5 6 7
4 5 6 7 8
2 3 4 5 6
3 4 5 6 7
3 4 5 6 7
4 5 6 7 8
4 5 6 7 8
5 6 7 8 9
3 4 5 6 7
4 5 6 7 8
4 5 6 7 8
5 6 7 8 9
5 6 7 8 9
6 7 8 9 10
      1、2、3、4、5 の全順列を考え、転位数を
     求めた表において、一番前が同じもの24個
     ずつにして、転位数の欄だけを取り出すと、
     左の5列になります。

      左から順に一番前が、1、2、3、4、5 である
     ものの転位数です。順に1ずつ増えて行って
     います。

      次の4列は、一番前が、1 である24個を、
     2番目が、2、3、4、5 の場合に分けて同様
     にしたものです。
     (次のは、一番前が1、2番目が 2 のものに
     ついて、同様にしたもの)

      このような現象が起こること、即ち、転位数
     が 1 ずつ増えていくことは容易にわかります
     が、漸化式の証明はこれとほとんど同じです。


 当HPがいつもお世話になっているHN「攻略法」さんにも解法をご教示いただきました。
                                       (平成23年8月1日付け)

個数の表に対応させて、並びをつくってみました。

k=0 0    1    2    3    4    5    6   (転位数)
n=1 1
n=2 12   21
n=3 123  132  312  321
        213  231
n=4 1234 1243 1423 4123 4132 4312 4321
        1324 1342 1432 4213 4231
        2134 2143 2413 3412 3421
             3124 3142 2431
             2314 2341 3241
                  3214


 m=4の並びから、n=5の並びを求めるには、

k=0 0     1     2     3     4     5     6     7(転位数)
n=5 1234_ 123_4 12_34 1_234 _1234 _1243
         1243_ 124_3 12_43 1_243 _1324
         1324_ 132_4 13_24 1_324 _2134
         2134_ 213_4 21_34 2_134 1_423
               1423_ 142_3 14_23 1_342
               1342_ 134_2 13_42 2_143
               2143_ 214_3 21_43 3_124
               3124_ 312_4 31_24 2_314
               2314_ 231_4 23_14 41_23
                     4123_ 412_3 14_32
                   1432_ 143_2 24_13
                   2413_ 241_3 31_42
                   3142_ 314_2 23_41
                   2341_ 234_1 32_14
                   3214_ 321_4 413_2
                           4132_ 421_3
                           4213_ 341_2
                           3412_ 243_1
                           2431_ 324_1
                           3241_ 4312_
                                 4231_
                                 3421_


 p列前(p<n(p≦n))なら、mの並びの右からp番目の前(後)に数字nを挿入する。

同列(p=0(p=1))は、最後に追加となる。残り(k=6、7、…)は、逆順なので省略。

 m=4、n=5 の場合、並び1234には、 イ1ロ2ハ3ニ4ホ の5箇所の位置に数字 5 を挿
入できる。

  イなら、転位数は4増加する。
  ロなら、転位数は3増加する。
  ハなら、転位数は2増加する。
  ニなら、転位数は1増加する。
  ホなら、転位数は0増加する。

(コメント) 攻略法さんに感謝します。

 上記の理論的な話が、オンライン整数列大辞典の「A008302」にある。

 その中で、次の事実に興味を引かれた。

T( 1 ,0 )=1 ・・・ 整式 1 の係数 1 に関連

T( 2 ,0)=1 、T( 2 ,1 )=1 ・・・ 整式 1+x の係数 1,1に関連

T( 3 ,0 )=1 、T( 3 ,1 )=2 、T( 3 ,2 )=2 、T(3 ,3 )=1

 ・・・ 整式 (1+x)(1+x+x2)=1+2x+2x2+x3 の係数 1,2,2,1 に関連

T( 4 ,0 )=1 、T( 4 ,1 )=3 、T( 4 ,2 )=5 、T(4 ,3 )=6 、

T( 4 ,4 )=5 、T( 4 ,5 )=3 、T( 4 ,6 )=1

 ・・・ 整式 (1+x)(1+x+x2)(1+x+x2+x3)= 1+3x+5x2+6x3+5x4+3x5+x6
   の係数 1,3,5,6,5,3,1 に関連

 以下同様。

 順列の転位数から作られる数列が、ある整式の係数になるという事実に驚かされる。

 このことから、 T( n ,k ) は、次の整式の x の係数で与えられる。

  (1+x)(1+x+x2)(1+x+x2+x3)・・・(1+x+x2+・・・+xn-1

例 T( 7 ,7 )を求めてみよう。

  (1+x)(1+x+x2)(1+x+x2+x3)・・・(1+x+x2+・・・+x6) を展開したとき、

7 の項が出る可能性は、

因数 1+・・・+x6 から x6 を選ぶとき

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの一つから

x を選べばよいから、5通り ・・・ T( 6 ,1 )の計算

因数 1+・・・+x6 から x5 を選ぶとき

 因数 1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの一つから x2 を選
ぶ場合は、4通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの二つから

それぞれ x を一つずつ選ぶ場合は、52=10通り

 よって、この場合は、 4+10=14通り ・・・ T( 6 ,2 )の計算

因数 1+・・・+x6 から x4 を選ぶとき

 因数 1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの一つから x3 を選ぶ場合は、
3通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの二つから

それぞれ x2 と x を一つずつ選ぶ場合は、4×4=16通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの三つから

それぞれ x を一つずつ選ぶ場合は、53=10通り

 よって、この場合は、 3+16+10=29通り ・・・ T( 6 ,3 )の計算

因数 1+・・・+x6 から x3 を選ぶとき

 因数 1+・・・+x4 、1+・・・+x5 のうちの一つから x4 を選ぶ場合は、2通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの二つから

それぞれ x3 と x を一つずつ選ぶ場合は、3×4=12通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの二つから

それぞれ x2 と x2 を一つずつ選ぶ場合は、42=6通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの三つから

それぞれ x2 と x と x を一つずつ選ぶ場合は、4×42=24通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの四つから

それぞれ x と x と x と x を一つずつ選ぶ場合は、54=5通り

 よって、この場合は、 2+12+6+24+5=49通り ・・・ T( 6 ,4 )の計算

因数 1+・・・+x6 から x2 を選ぶとき

 因数 1+・・・+x5 のうちの一つから x5 を選ぶ場合は、1通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの二つから

それぞれ x4 と x を一つずつ選ぶ場合は、2×4=8通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの二つから

それぞれ x3 と x2 を一つずつ選ぶ場合は、3×3=9通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの三つから

それぞれ x3 と x と x を一つずつ選ぶ場合は、3×42=18通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの三つから

それぞれ x2 と x2 と x を一つずつ選ぶ場合は、42×3=18通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの四つから

それぞれ x2 と x と x と x を一つずつ選ぶ場合は、4×43=16通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの五つから

それぞれ x と x と x と x と x を一つずつ選ぶ場合は、55=1通り

 よって、この場合は、 1+8+9+18+18+16+1=71通り ・・・ T( 6 ,5 )の計算

因数 1+・・・+x6 から x を選ぶとき

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの二つから

それぞれ x5 と x を一つずつ選ぶ場合は、1×4=4通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの二つから

それぞれ x4 と x2 を一つずつ選ぶ場合は、2×3=6通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの二つから

それぞれ x3 と x3 を一つずつ選ぶ場合は、32=3通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの三つから

それぞれ x4 と x と x を一つずつ選ぶ場合は、2×42=12通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの三つから

それぞれ x3 と x2 と x を一つずつ選ぶ場合は、3×3×3=27通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの三つから

それぞれ x2 と x2 と x2 を一つずつ選ぶ場合は、43=4通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの四つから

それぞれ x3 と x と x と x を一つずつ選ぶ場合は、3×43=12通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの四つから

それぞれ x2 と x2 と x と x を一つずつ選ぶ場合は、42×32=18通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの五つから

それぞれ x2 と x と x と x と x を一つずつ選ぶ場合は、4×44=4通り

 よって、この場合は、 4+6+3+12+27+4+12+18+4=90通り
                                        ・・・ T( 6 ,6 )の計算

因数 1+・・・+x6 から 1 を選ぶとき

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの二つから

それぞれ x5 と x2 を一つずつ選ぶ場合は、1×3=3通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの二つから

それぞれ x4 と x3 を一つずつ選ぶ場合は、2×2=4通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの三つから

それぞれ x5 と x と x を一つずつ選ぶ場合は、1×42=6通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの三つから

それぞれ x4 と x2 と x を一つずつ選ぶ場合は、2×3×3=18通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの三つから

それぞれ x3 と x3 と x を一つずつ選ぶ場合は、32×3=9通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの三つから

それぞれ x3 と x2 と x2 を一つずつ選ぶ場合は、3×32=9通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの四つから

それぞれ x4 と x と x と x を一つずつ選ぶ場合は、2×43=8通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの四つから

それぞれ x3 と x2 と x と x を一つずつ選ぶ場合は、3×3×32=27通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの四つから

それぞれ x2 と x2 と x2 と x を一つずつ選ぶ場合は、43×21=8通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの五つから

それぞれ x3 と x と x と x と x を一つずつ選ぶ場合は、3×44=3通り

 因数 1+x 、1+x+x2 、1+・・・+x3 、1+・・・+x4 、1+・・・+x5 のうちの五つから

それぞれ x2 と x2 と x と x と x を一つずつ選ぶ場合は、42×33=6通り

 よって、この場合は、 3+4+6+18+9+9+8+27+8+3+6=101通り
                                         ・・・ T( 6 ,7 )の計算

 以上から、 T( 7 ,7 )=5+14+29+49+71+90+101=359(通り) となる。

 上式の足している数がそれぞれ順番に

T( 6 ,1 )、T( 6 ,2 )、T( 6 ,3 )、T( 6 ,4 )、T( 6 ,5 )、T( 6 ,6 )、T( 6 ,7 )

となっている点からも、漸化式の成立が確認される。ただ、順列で考えた方が楽かも...!

(コメント) 手計算で計算してみて、自然数の分解にも関係があるんですね!何やらたくさ
      ん問題が作れそうな...雰囲気。



   以下、工事中