All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Tiling and counting (Posted on 2015-11-10) Difficulty: 2 of 5
In how many ways can a 2xn grid be tiled using only 2x1 tiles, which can be laid either horizontally or vertically?

Design a way to enumerate those patterns.

See The Solution Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution He's back | Comment 1 of 2
That is, Fibonacci is back:

 n     ways
 1       1
 2       2
 3       3
 4       5
 5       8
 6      13
 7      21
 8      34
 9      55
10      89
11     144
12     233
13     377
14     610
15     987 n F(n+1)

based on the fact that any even subset can have tiles paired horizontally (i.e., each tile parallel to the long axis of the grid), and the remainder are placed vertically across the width of the grid.  If v is the number that are vertical (across the width of the grid) then n-v/2 is the number of pairs set out horizontally. For each possible number of verticals they can be anywhere in the v + ((n - v)/2) positions for individual vertical tiles mixed with paired horizontal sets: Sigma(C(v+(n-v)/2,v)), obviously summed only for even n-v.

Using = to represent two horizontal tiles and | to represent individual vertical tiles, the ways are represented graphically (each set headed with n and ways):


1 1
|

2 2
=
||

3 3
|=
=|
|||

4 5
= =
||=
=||
|=|
||||

5 8
|= =
= =|
=|=
|||=
=|||
|=||
||=|
|||||

6 13
= = =
||= =
= =||
=|=|
=||=
|= =|
|=|=
||||=
=||||
|=|||
||=||
|||=|
||||||

7 21
|= = =
= = =|
= =|=
=|= =
|||= =
= =|||
=|=||
=||=|
=|||=
|= =||
|=|=|
|=||=
||= =|
||=|=
|||||=
=|||||
|=||||
||=|||
|||=||
||||=|
|||||||


DefDbl A-Z
Dim crlf$, save(15)
Function mform$(x, t$)
  a$ = Format$(x, t$)
  If Len(a$) < Len(t$) Then a$ = Space$(Len(t$) - Len(a$)) & a$
  mform$ = a$
End Function

Private Sub Form_Load()
 Text1.Text = ""
 crlf$ = Chr(13) + Chr(10)
 Form1.Visible = True
 DoEvents
 
 For n = 1 To 15
  tot = 0
  For upright = 0 To n
    rest = n - upright
    If rest Mod 2 = 0 Then
      tot = tot + combi(rest / 2 + upright, upright)
    End If
  Next
  save(n) = tot
  Text1.Text = Text1.Text & mform(n, "#0") & mform(tot, "#######0") & crlf
 Next
   
 For n = 1 To 7
   Text1.Text = Text1.Text & crlf & n & Str(save(n)) & crlf
   For upright = 0 To n
    rest = n - upright
    If rest Mod 2 = 0 Then
      s$ = String(upright, "|") + String(rest / 2, "=")
      h$ = s
      Do
        s2$ = s
        Do
          ix = InStr(s2, "==")
          If ix Then s2 = Left(s2, ix) + " " + Mid(s2, ix + 1)
        Loop Until ix = 0
        Text1.Text = Text1.Text & s2 & crlf
        permute s
      Loop Until s = h
    End If
   Next
 Next
   
   
  Text1.Text = Text1.Text & "done" & crlf
 
End Sub

Function combi(n, r)
  c = 1
  For i = n To n - r + 1 Step -1
    c = c * i
  Next
  For i = 2 To r
    c = c / i
  Next
  combi = c
End Function


  Posted by Charlie on 2015-11-10 10:49:22
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information