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.
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 |
He's back
