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

 Tiling and counting (Posted on 2015-11-10)
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.)
 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      5510      8911     14412     23313     37714     61015     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

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

 Search: Search body:
Forums (0)