平成１３年４月８日

[流れ星]

　　　　　　　　第７２回数学的な応募問題

　　　　　　　　　　＜解答募集期間：４月１日〜４月１５日＞

［２段に並べる］

太郎さんは、授業の中で、縦が２個、横が２ｎ個の升目のそれぞれに赤か白のマグネットを並べるときがあります。
縦にも横にも白のマグネットを連続して並べない方法は何通りあるか、知りたくなりました。

　　　　　　　　　　　　縦に２個、横に２ｎ個の升目

　 　 　 　
　 　 　 　

ここで、問題です。

問題１：ｎ＝１のとき、このような並び方は何通りあるか。
問題２：ｎ＝２のとき、このような並び方は何通りあるか。
問題３：ｎ＝３のとき、このような並び方は何通りあるか。
問題４：このような２段に並べる場合の数をａｎとするとき、規則性を発見して、漸化式を作ってください。
問題５：この数列｛ａｎ｝の一般項をｎで表してください。　

ＮＯ１＜清川（kiyo）＞さんからの報告　受信２日21時57分　更新８日

いつもお世話になっています。kiyoです。
数列サイトで検索して見ました。
( Chebyshev's polynomials of the 2nd kind.)とありました。
検索結果は以下の通りでした。
特性方程式からの一般項は今後の課題とします。
今後とも宜しくお願いします。
ID Number: A002315 (Formerly M4423 and N1869)
Sequence:1,7,41,239,1393,8119,47321,275807,1607521,9369319,54608393, 318281039,1855077841,10812186007,63018038201,367296043199, 2140758220993,12477253282759,72722761475561,423859315570607， 2470433131948081
Name: a(n) = 6a(n-1) - a(n-2). a(0)=1,a(1)=7
Also NSW numbers: x such that x^2 - 2.y^2 = -1 for some y.
References E. Barcucci et al., A combinatorial interpretation of the　recurrence
f_{n+1} = 6 f_n - f_{n-1}, Discrete Math., 190 (1998)　235-240.
A. H. Beiler, Recreations in the Theory of Numbers, Dover,NY, 1964, p.256.
A. S. Fraenkel, Recent results and questions in　combinatorial gamｅcomplexities,
　　　　　　　　Theoretical Computer Science, vol. 249, no. 2　(2000),　265-288.
D. H. Lehmer, Lacunary recurrence formulas for the numbers　of
Bernoulli and Euler, Annals Math., 36 (1935), 637-649.
Problem 47, Amer. Math. Monthly, 4 (1897), 25-28.
P. Ribenboim, The Book of Prime Number Records.
Springer-Verlag, NY,2nd ed., 1989, p. 288.
R. A. Sulanke, Moments of generalized Motzkin paths, J.Integer　Sequences, Vol. 3 (2000), #00.1.
P.-F. Teilhet, Reply to Query 2094, L'Interm\'{e}diaire des　Math\'{e}maticiens, 10 (1903),235-238.
Links: Sulanke paper
A.S. Fraenkel, Arrays, numeration systems and games.
Index entries for sequences related to Chebyshe　polynomials.
Link to a section of Eric Weisstein's World of Mathematics.
Formula: a(n)=sqrt(2*(A001653(n))^2-1). G.f.: (1+x)/(1-6*x+x^2).
a(n)= S(n,6)+S(n-1,6) = S(2*n,sqrt(8)), S(n,x)=U(n,x/2) are
Chebyshev's polynomials of the 2nd kind.
Cf. A049310. S(n,6)=A001109(n+1).
See also: Bisection of A001333. A002315=sqrt{2*(A001653)^2-1}.
Keywords: nonn,easy,nice
Offset: 0
Author(s): njas
Extension: More terms from James A. Sellers (sellersj@cedarville.edu), Feb 16 2000

＜水の流れ：コメント＞この問題の数列が既に報告されていたのですか。驚きます。さらに、漸化式までもね。当初、この問題を作成していたときは、縦２個、横ｎ個の升目を考えていましたが、出題するときは、横を２ｎ個にしていました。太郎さんとの予定が違っていました。
漸化式を発見される場合は、縦２個、横ｎ個の升目として考えてください。そして、特性方程式の解から、一般項を求めます。この答えでｎの所を２ｎと置き換えても良いです。

ＮＯ２＜清川（kiyo）＞さん解答　受信２日22時41分　更新８日
 いつもお世話になっています。kiyoです。漸化式をもとにA(50)まで求めて見ました。
今後とも宜しくお願いします。追伸：「マグネット」の漸化式は解決したのでしょうか。
REM ２段に並べる
OPTION BASE 0
DIM A(50)
LET A(0)=1
LET A(1)=7
FOR I=2 TO 50
LET A(I)=A(I-1)*6-A(I-2)
NEXT I
FOR I=0 TO 50
PRINT "A";"(";I;")";"=";A(I)
NEXT I
END
A( 0 )= 1
A( 1 )= 7
A( 2 )= 41
A( 3 )= 239
A( 4 )= 1393
A( 5 )= 8119
A( 6 )= 47321
A( 7 )= 275807
A( 8 )= 1607521
A( 9 )= 9369319
A( 10 )= 54608393
A( 11 )= 318281039
A( 12 )= 1855077841
A( 13 )= 10812186007
A( 14 )= 63018038201
A( 15 )= 367296043199
A( 16 )= 2140758220993
A( 17 )= 12477253282759
A( 18 )= 72722761475561
A( 19 )= 423859315570607
A( 20 )= 2470433131948081
A( 21 )= 14398739476117879
A( 22 )= 83922003724759193
A( 23 )= 489133282872437279
A( 24 )= 2850877693509864481
A( 25 )= 16616132878186749607
A( 26 )= 96845919575610633161
A( 27 )= 564459384575477049359
A( 28 )= 3289910387877251662993
A( 29 )= 19175002942688032928599
A( 30 )= 111760107268250945908601
A( 31 )= 651385640666817642523007
A( 32 )= 3796553736732654909229441
A( 33 )= 22127936779729111812853639
A( 34 )= 128971066941642015967892393
A( 35 )= 751698464870122983994500719
A( 36 )= 4381219722279095887999111921
A( 37 )= 25535619868804452344000170807
A( 38 )= 148832499490547618176001912921
A( 39 )= 867459377074481256712011306719
A( 40 )= 5055923762956339922096065927393
A( 41 )= 29468083200663558275864384257639
A( 42 )= 171752575441025009733090239618441
A( 43 )= 1001047369445486500122677053453007
A( 44 )= 5834531641231893991002972081099601
A( 45 )= 34006142477945877445895155433144599
A( 46 )= 198202323226443370684367960517767993
A( 47 )= 1155207796880714346660312607673463359
A( 48 )= 6733044458057842709277507685523012161
A( 49 )= 39243058951466341909004733505464609607
A( 50 )= 228725309250740208744750893347264645481
ＮＯ３＜清川（kiyo）＞さん解答　受信４日21時22分　更新８日
いつもお世話になっています。kiyoです。一般項を求めることが出来ました。
A(n)=((SQR(2)+1)*(3+SQR(8))^n-(SQR(2)-1)*(3-SQR(8))^n)/2
今後とも宜しくお願いします。
＜水の流れ＞　皆さんのおかげで、今日に至っています。これからもよろしくお願いします。８日記述

ＮＯ４＜浜田＞さん解答　受信9日11時12分　更新９日
 【いつの間にか，解答が出ていましたね．皆さん，早いです．エクセルのマクロで解いてみました．とりあえずｎ≦６の場合の数を求めるプログラムです．'****の部分の数を増やせば，ｎ＞６の場合の数も求められますが，時間がかかってしまいます．】
Option Explicit
Sub Macro1()
Dim n As Integer
Dim j(24) As Integer '****
For n = 1 To 6 '****
Cells(n, 1).Value = n
Cells(n, 2).Value = 0
Call check(n, 1, j())
Next n
End Sub
Sub check(ByVal n As Integer, ByVal m As Integer, ByRef j() As Integer)
j(m) = 0 '0->red, 1->white
While j(m) <= 1
j(m + 1) = 0
While j(m + 1) <= 1
If dame(m, j()) = 0 Then
If m + 1 < 4 * n Then
Call check(n, m + 2, j())
Else
Cells(n, 2).Value = Cells(n, 2).Value + 1
End If
End If
j(m + 1) = j(m + 1) + 1
Wend
j(m) = j(m) + 1
Wend
End Sub
Private Function dame(ByVal m As Integer, ByRef j() As Integer)
Dim i As Integer
Dim i1 As Integer
Dim i2 As Integer
dame = 0
i = 0
While dame = 0 And i <= -2 * (m > 1)
Select Case i
Case 0
i1 = m
i2 = m + 1
Case 1
i1 = m - 2
i2 = m
Case Else
i1 = m - 1
i2 = m + 1
End Select
dame = -(j(i1) = 1 And j(i2) = 1)
i = i + 1
Wend
End Function　　よって、求める答は
1 7
2 41
3 239
4 1393
5 8119
6 47321
＜水の流れ＞　皆さんのおかげです。感謝に気持ちでいっぱいです。これからもよろしくお願いします。９日記述

　　　　＜自宅＞　　mizuryu@aqua.ocn.ne.jp