図形の埋め込み5                           戻る

 1×2のタイル を用いて、次の3×2の図形

    

を埋め尽くすことを考える。1×2のタイルは、縦にも横にもしてよいものとする。

 このとき、埋め尽くす方法は、明らかに 3通りある。(ただし、色は区別しないものとする。)

               

 同様にして、3×4の図形

    

を埋め尽くす方法は、全部で11通りある。

      

      

    

 そこで、問題です。

(1) 3×6の図形

    

 を埋め尽くす方法は、全部で何通りあるか?


(2) 3×8の図形

    

 を埋め尽くす方法は、全部で何通りあるか?
























(答)(1) 41通り  (2) 153通り

 3×4の図形

    

を埋め尽くす方法の数は、上記では漏れなく重複なく数え上げたが、その11通りは、

      

      



のように、

  

と、真ん中でくっきり分断される場合と

  

のように、真ん中でくっきりとは分断されない場合に場合分けされる。

 分断される場合は、3×2の図形の埋め尽くす方法の数 3 通りを用いて、

   3×3=9(通り)

分断されない場合は、上図のように2通りあるので、

従って、求める場合の数は、 9+2=11(通り) と求められる。

 このような見方、考え方をすれば、3×6の図形の場合も、全てを数え上げなくても計算で
求めることが可能である。

(1)(イ) 分断線が2箇所ある場合

          3×2の図形が3連の場合なので、この条件で
   埋め尽くされる方法の数は、

     3×3×3=27(通り)


(ロ) 分断線が1ヶ箇所のみの場合

           3×2+2×3
  =12(通り)

(ハ) 分断線がない場合

    

 この場合の埋め尽くす方法は、次の2通りしかない。

       

 以上から、3×6の図形を埋め尽くす方法の数は、

   3×3×3+3×2+2×3+2=27+12+2=41(通り)

となる。

(2) (1)と同様に分類して、

3×3×3×3+3×3×2+2×3×3+3×2×3+3×2+2×2+2×3+2=153(通り)

であることが分かる。


(追記) 令和3年10月10日付け

 上記で

 1×2のタイル を用いて、

 3×2の図形を埋め尽くす方法の数は、 3通り

 3×4の図形を埋め尽くす方法の数は、 11通り

 3×6の図形を埋め尽くす方法の数は、 41通り

 3×8の図形を埋め尽くす方法の数は、 153通り

であることを知った。

 3×1の図形を埋め尽くす方法の数は、明らかに、 1通り であるので、

数列 1,3,11,41,153,・・・ が得られる。

 この数列を「オンライン整数列大辞典」に問い合わせると、「A001835」や「A079035」が
ヒットした。

 それらのページでは、「ドミノを用いて、3×2nの長方形を埋め尽くす方法の数 a」が調
べられている。(ドミノ=2つの正方形をつなげた形)

 数列{an} について、漸化式

  1=1、a2=3、an+2=4an+1−an (n=1,2,3,・・・)

が成り立つという。

例 a3=4a2−a1=4×3−1=11

   a4=4a3−a2=4×11−3=41

   a5=4a4−a3=4×41−11=153

で、確かに、これまでの結果と一致する。


 果たして、この漸化式は、どうやって作ったのだろうか?


(追記) 令和3年10月11日付け

 3×2nの図形を1×2のタイルで埋め尽くす方法の数をa通りとおく。

 漸化式を考えるために、まず、3×2の図形

     

を埋め尽くす方法

               

を、次の2つの場合に分類する。

・ 3つの1×2のタイルがすべて縦1列に並ぶ場合

    

・ その他の場合

          

 同様にして、3×4の図形

    

を埋め尽くす方法を、次の2つの場合に分類する。

・ 左端の3つの1×2のタイルがすべて縦1列に並ぶ場合

        

・ その他の場合で、真ん中でくっきり分断される場合

        

        

  真ん中でくっきりとは分断されない場合

      

 そこで、

 左端の3つの1×2のタイルがすべて縦1列に並ぶときの埋め尽くす方法の数をx通り

それ以外のときの埋め尽くす方法の数を、y通りとおくとき、上図の場合から、

 3×2の図形について、 a1=3 、x1=1 、y1=2  から、a1=x1+y1 である。

 3×4の図形について、 a2=11 、x2=3 、y2=8 から、 a2=x2+y2 である。

 このとき、 x2=1×a1=x1+y1 で、 y2=(2x1+2y1)+y1=2x1+3y1 である。

 このことから、一般的に、

   xn+1=a=x+y 、yn+1=2x+3y

が成り立つ。 y=xn+1−x を代入して、 xn+2−xn+1=2x+3(xn+1−x) から、

漸化式 xn+2=4xn+1−x を得る。


 DD++ さんからのコメントです。(令和3年10月12日付け)

 分断線の考え方で、一番右の分断線がどこなのを考えれば、

 a[n] = 3*a[n-1] + 2*a[n-2] + 2*a[n-3] + …… + 2*a[1] + 2

 添字をずらして、

 a[n-1] = 3*a[n-2] + 2*a[n-3] + …… + 2*a[1] + 2

 これらの差をとると、 a[n] - a[n-1] = 3*a[n-1] - a[n-2] から、

  a[n] = 4*a[n-1] - a[n-2]

ですかね。


(コメント) DD++ さん、ありがとうございます。左端の3×2の部分を除いて、分断されない
      部分の埋め尽くす方法の数が、いつも2通りというのが急所かな?そうすれば、
      連立の漸化式を立てるまでもなかったですね。


(追記) 令和3年10月17日付け

 冒頭の問題で、すぐ気がつくことは、1×2のタイル の面積は2、偶数なので、

この1×2のタイルを用いて、3×(2n+1)の図形を埋め尽くすことは絶対に不可能だとい
うことである。

 また、3×2nの図形を1×2のタイルで埋め尽くす方法の数をa通りとおくと、数列{an

  1,3,11,41,153,・・・ 

から、すべての自然数 n に対して、a は奇数であることが推測されるが、漸化式

  1=1、a2=3、an+2=4an+1−an (n=1,2,3,・・・)

から、明らかなことだろう。

 実際に、a1=1、a2=3 は奇数で、漸化式より、a3 も奇数となる。以下、帰納的に、

すべての自然数 n に対して、a は奇数であることが分かる。

(厳密には、数学的帰納法による)



  以下、工事中!