平成１１年１１月１６日

［大縄跳び］

　太郎さんは、過去に、このような数列を扱ったことを覚えています。

読者の皆さん！思い出してください。

ＮＯ１　＜四年寝太郎＞さんからの解答１５日１０時受信　１６日更新

大縄がn本の時の軌跡の数をP(n)で表す。回答1)書いて数えてみました。

P(1)=1　　　P(2)=2　　　　P(3)=5　　　　P(4)=14

回答2)一番左の人が持っている縄の中にいる組と、残りの組で考える。例えば

5本の場合で考えると、

左が単独の縄の場合、残りの縄は4本。

左が1組を中に含むペアの場合、残りの縄は3本。

左が2組を中に含むペアの場合、残りの縄は2本。

左が3組を中に含むペアの場合、残りの縄は1本。

左が4組を中に含むペアの場合、残りの縄は0本。

P(5)は左が中に含む組み合わせと残りの縄でできる組み合わせの積の合計だ

からP(5)=P(4)+P(1)*P(3)+P(2)*P(2)+P(3)*P(1)+P(4)

ここでP(0)=1とおくと、一般にP(n)は以下のように表せる。

n-1

P(n)=Σ P(i)*P(n-i-1)

i=0

コメント:多分1)はあっていると思います。2)の考え方はちょっと自信ないで

す。それに、一般のP(n)の求め方が分かりません。これって求められるものな

のでしょうか？くやしぃーーーっ！ 　　　　　　　　　

＜水の流れ：コメント＞　漸化式まで正解ですね。後は、一般のP(n)の式をｎで表してください。　

ＮＯ２　＜Ｊｕｎ＞さんからの解答１５日１３時受信　１６日更新

ＮＯ３　＜ch3cooh＞さんからの解答１５日１６時受信　１６日更新

縄跳びの問題：今回の課題は、数列ですね？

数学を専門でやっていたのではないので、一部の専門用語に怪しいところがありますが･･･

（一番大外の縄が、全体をかこっている必要があるかどうか不明なので、次のような手順で求めました。）

例) n=3の場合

ポイントを0,1,2,3,4,5とする。縄はポイント間を接続しているものとする。

(大外の縄が必要な場合)

0-5, 1-2, 3-4

0-5, 1-4, 2-3

(大外の縄が不要な場合)

0-1, 2-3, 4-5

0-1, 2-5, 3-4

0-3, 1-2, 4-5

0-5, 1-2, 3-4

0-5, 1-4, 2-3

１）下準備（大外に縄があり、その内側にn-1本の縄の組合わせがある場合）

n= 1 の場合 "(1)" とする　　0-1

n= 2 の場合 "(2)" とする　　0-3, 1-2　　(0-1,2-3の組は、上記条件を満たさない)

n= 3 の場合　　　　　　　　　0-5, 1-2, 3-4 : これは、0-5, 1-2, (1*) である。　

　　　　　　　　　　　　　　　0-5, 1-4, 2-3 : これは、0-5, (2*) である。

(x*)は、(x)の組合わせの開始する点を必要に応じて延長したもの

n= 4 の場合　(1*を用いる組合わせ)　0-7, 1-2, 3-4, 5-6 : これは、0-7, 1-2, 3-4, (1*) である。

(2*を用いる組合わせ)　　　0-7, 1-2, 3-6, 4-5 : これは、0-7, 1-2, (2*) である。

　　　　　　　　　　　　　0-7, 1-4, 2-3, 5-6 : これは、0-7, (2*), 5-6 である。

　　　　　　　　　　　　　0-7, 1-6, 2-3, 4-5 :

(3*を用いる組合わ)　　　　0-7, 1-6, 2-5, 3-4 : これは、0-7, (3*) である。

以後、同様に拡張できる。　これを数式として考えると( g(n) として)

g(1)= 1

g(2)= 1

g(n)= 1+Σ(i=2 to n-1) g(i)*(n-i)　とすると･･･

g(3)= 1+g(2)*1= 2

g(4)= 1+g(2)*2+g(3)*1= 1+2+2= 5

g(5)= 1+g(2)*3+g(3)*2+g(4)*1= 1+3+4+5= 13

g(6)= 1+g(2)*4+g(3)*3+g(4)*2+g(5)*1= 1+4+6+10+13= 34　　　…となる。

２）大外に縄がある必要の無い場合　これを、f(n)とすると、f(n)= g(n+1)となる。

上の式をg(n)を必要としない式とするには･･･

p(n)= g(n+1)-g(n)

= {1+g(2)*(n-1)+g(3)*(n-2)+g(4)*(n-3)･･･+g(n-1)*2+g(n)*1}

-{1+g(2)*(n-2)+g(3)*(n-3)+g(4)*(n-4)･･･+g(n-1)*1}

= { g(2) +g(3) +g(4) ･･･+g(n-1) +g(n) }

p(n+1)-p(n)

= { g(2) +g(3) +g(4) ･･･+g(n) +g(n+1) }

-{ g(2) +g(3) +g(4) ･･･+g(n) }

= g(n+1)

これを整理すると･･･

g(n+2)-3*g(n+1)+g(n)= 0

ここで、

G^(n+2)-3*G^(n+1)+G^(n)= G^(n)*(G^2-3*G^1+1)= 0 である。

ゆえに、g(n)の基底は(3±√5)/2である。

g(n)= a*((3+√5)/2)^n+b*((3-√5)/2)^n

が成り立つものとして、

(a= an+√5ar,b= bn+√5br: an,ar,bn,br;整数)

g(1)= (an+√5ar)*((3+√5)/2)^1+(bn+√5br)*((3-√5)/2)^1

= (1/2)*( (3*an+5*ar+3*bn-5*br)+√5*(1*an+3*bn-1*bn+3*br) )

= 1

g(2)= (an+√5ar)*((3+√5)/2)^2+(bn+√5br)*((3-√5)/2)^2

= (an+√5ar)*((14+6√5)/4)+(bn+√5br)*((14-6√5)/4)

= (1/4)*( (14*an+30*ar+14*bn-30*br)+√5*(6*an+14*bn-6*bn+14*br) )

= 1

であるので、

M= 3 5 3 -5

1 3 -1 3

14 30 14 -30

6 14 -6 14

の 4x4のマトリクスの解を求めることにより、an,ar,bn,brが得られる。(筆算では計算する気がおきない)

f(n)をコンピュータで全数検索した値は･･･

n= 1

n= 2

n= 5

n= 13

n= 34

n= 89

n= 233

n= 610

n= 1597

n= 4181

n= 10946

n= 28657

n= 75025

n= 196418

n= 514229

ただし、 ((3+√5)/2)>1

((3-√5)/2)<0

であるので、最終的な答えは、a*((3+√5)/2)^nに収束する。

((3+√5)/2)^nと比較すると･･･

((3+√5)/2)^n f(n)/(((3+√5)/2)^n)

f(n)= 1 1.00000 1.00000

f(n)= 2 2.61803 1.30902

f(n)= 5 6.85410 1.37082

f(n)= 13 17.94427 1.38033

f(n)= 34 46.97871 1.38173

f(n)= 89 122.99187 1.38193

f(n)= 233 321.99689 1.38196

f(n)= 610 842.99881 1.38197

f(n)= 1597 2206.99955 1.38197

f(n)= 4181 5777.99983 1.38197

f(n)= 10946 15126.99993 1.38197

f(n)= 28657 39602.99997 1.38197

f(n)= 75025 103681.99999 1.38197

f(n)= 196418 271443.00000 1.38197

f(n)= 514229 710647.00000 1.38197　　　となる。

＜水の流れ：コメント＞　全体をかこっている必要はないとして、作問しました。

ＮＯ４　＜ヨッシー＞さんからの解答１５日１７時受信　１６日更新

　f(n) を 人数 2n 人の時の、軌跡の数とすると

問題１　f(1)＝1　f(2)＝1×3＝3　　f(3)＝3×5＝15　　f(4)＝15×7＝105　　（問題２の考え方２を使っています）

問題２　（考え方１）

2nの生徒を１列に並べ、前から２人ずつペアを作っていきます。並び方は (2n)! 通り、

このうち、重複して数えているのは、２人ずつのペアの並び順の n! 通りと、各ペア２人の並び順2^n 通り、

よって、f(n)＝(2n)!÷n!÷2^n＝2nＰn／2^n

（考え方２）

f(1)＝1 であり、f(n) がわかっているとします。このとき、さらに２人増えたとき、何倍になるかを考えます。

f(n) 通りのうちの１通りを

(a,b),(c,d),(e,f)・・・　とし、ここに (x,y) の２人が加わったとします。

●(a,b),(c,d),(e,f)・・・と独立して、ペア(x,y) を作るのが１通り、

●どれか１つのペアに割り込んで（たとえば(a,b)）、

　新しいペア (a,x),(b,y) または (a,y),(b,x) を作るのが　２×ｎ 通り。

合わせて、(2n+1) 倍になります。

つまり、f(1)＝1，f(n)＝f(n-1)×(2n-1) という漸化式になります。

よって、f(n)＝Π(k=1〜n)(2n-1)

＜水の流れ：コメント＞１６日記入　誰かコメントください。

ＮＯ５　＜ch3cooh＞さんからの解答１６日１０時受信　１７日更新

出したしばらく後で、ミスに気がつきました。計数を行うためには、全体を囲っている組で考えるのが、計算のためには適切と思われるのですが、内部の分割の考え方でミスっていました。

g(1) : 1

g(2) : 1

内部 g(1)

g(3) : 2

内部 g(1)+g(1) : 1

g(2) : 1

g(4) : 5

g(1)+g(1)+g(1) : 1

g(1)+g(2) : 2

g(3) : 2

g(5) : 9

g(1)+g(1)+g(1)+g(1) : 1

g(1)+g(1)+g(2) : 3

g(1)+g(3) : 4

g(2)+g(2) : 1 < この組合わせが除外されていた

g(6) : 16

g(1)+g(1)+g(1)+g(1)+g(1) : 1

g(1)+g(1)+g(1)+g(2) : 4

g(1)+g(1)+g(3) : 2*3= 6

g(1)+g(2)+g(2) : 1*3= 3 <

g(2)+g(3) : 2 <

g(7) : 96 ?

g(1)+g(1)+g(1)+g(1)+g(1)+g(1) : 1

g(1)+g(1)+g(1)+g(1)+g(2) : 5

g(1)+g(1)+g(1)+g(3) : 2*4= 8

g(1)+g(1)+g(2)+g(2) : 6 <

g(1)+g(1)+g(4) : 3*5= 15

g(1)+g(2)+g(3) : 8*2= 16 <

g(1)+g(5) : 2*9= 18

g(2)+g(2)+g(2) : 1

g(2)+g(4) : 2*5= 10 <

g(6) : 16

構成要素の位置の組合わせなので、 構成要素数のコンビネーションで重複も含めた総数を計算した後に、重複したケースを除外することで、計算が出来る(と思う)。

(大外を囲っている必要があるという制限を設けたのは、上記のような計数の方が楽ではないかと考えたためです。)

正確な計算については、現在再考中です。

＜水の流れ：コメント＞１７日記入　みなさんの苦労の後が滲んでいます。考えてね。これからの皆さんのレポートを楽しみにまっています。