3×ｍの長方形に2×1の長方形を敷き詰める方法は何通りか分かるかたいら

質問

3×ｍの長方形に2×1の長方形を敷き詰める方法は何通りか分かるかたいらっしゃいますか？

回答お願いします。

漸化式なども分かるとありがたいです。

回答No.2

nag0720 · ベストアンサー

漸化式だけ

mは偶数でなければばらないので、m=2kとします。

3×2kの長方形に2×1の長方形を敷き詰めるときの敷き詰めかたの数をA(k)とすると、
A(1)=3
A(2)は、
3×4の敷き詰めかたが3×2と3×2に分けられる場合は、A(1)*A(1)通り、
3×2と3×2に分けられない場合は、2通りなので、
A(2)=A(1)*A(1)+2=11
A(3)は、
3×6の敷き詰めかたが3×2と3×4に分けられる場合は、A(1)*A(2)通り、
3×2と3×4に分けられないが、3×4と3×2に分けられる場合は、2*A(1)通り、
3×2と3×4にも3×4と3×2にも分けられない場合は、2通りなので、
A(3)=A(1)*A(2)+2*A(1)+2=41
というように考えると、漸化式は、
A(0)=1
A(n)=A(n-1)+2*Σ[i=0・・・n-1]A(i)　（n>0）

回答No.4

nag0720

＃２です。ついでに一般項を。

A(n)=A(n-1)+2*Σ[i=0・・・n-1]A(i)
A(n-1)=A(n-2)+2*Σ[i=0・・・n-2]A(i)
上式から下式を引くと
A(n)-A(n-1)=A(n-1)-A(n-2)+2*A(n-1)
A(n)=4*A(n-1)-A(n-2)

α=2+√3、β=2-√3　とおくと、
A(n)-β*A(n-1)=α*(A(n-1)-β*A(n-2))
B(n)=A(n)-β*A(n-1)
とおくと、
B(n)=α*B(n-1)

あとは御自分でどうぞ。

お礼

これは三項間漸化式ですかね。

分かりました。ありがとうございます。

回答No.3

foriver7

#1です。

やはり、数え漏らしがありました。#2さんなので正しいかと・・・

回答No.1

foriver7

参考程度の意見で書かせてもらいます。

ｍが奇数の時は敷き詰められないのは理解できていますか？長方形をｋ個敷き詰めると・・・
３×ｍ　＝　奇数　ですが、
２×ｋ　＝　偶数　で、面積が絶対に等しくなることはありません。

なので、ｍは２以上の偶数として話を進めましょう。

まず初めにｍ＝２のとき敷き詰め方は何通りあるでしょうか？
これは自分で考えられると思います。３通りあります。

それではnを自然数としてｍ＝2ｎのとき(ｍは偶数なので)Ａ(2ｎ)通り敷き詰め方があるとすると
普通はA(2n+1)の時を考えて漸化式を考えますが、このときは奇数なので詰められないですよね。
なのでA(2(n+1))=(A(2n+2))の時を考えましょう。

このとき、長方形は、3×2nから3×(2n+2)に変わっていますので最後に3×2分のスペースが空くことになります。このスペースへの敷き詰め方は何通りありますか？A(2)と同じですよね？
なので、漸化式は

A(2(n+1)) = A(2n) + 3 ,A(2) = 3

と、なります。後は基本通りに、等差数列の漸化式を解いていけば出ると思います。