# [seqfan] Re: A193376 Tabl = 20 existing sequences

Ron Hardin rhhardin at att.net
Tue Jul 26 02:52:43 CEST 2011

```Nice proof.  It speeds up the 10000 term b-files considerably, if you don't have
to actually enumerate to guarantee correctness.

Doing the cases for 3X1, 4X1, 5X1 and 6X1 tiles, I need formula lines, if Maple
or something can find verified solutions

They would otherwise read something like the following (cross references found
automatically, not checked)

T(n,k)=Number of ways to place any number of 3X1 tiles of k distinguishable
colors into a nX1 grid

Table starts
..1...1...1...1...1....1....1....1....1....1....1....1.....1.....1.....1.....1
..1...1...1...1...1....1....1....1....1....1....1....1.....1.....1.....1.....1
..2...3...4...5...6....7....8....9...10...11...12...13....14....15....16....17
..3...5...7...9..11...13...15...17...19...21...23...25....27....29....31....33
..4...7..10..13..16...19...22...25...28...31...34...37....40....43....46....49
..6..13..22..33..46...61...78...97..118..141..166..193...222...253...286...321
..9..23..43..69.101..139..183..233..289..351..419..493...573...659...751...849
.13..37..73.121.181..253..337..433..541..661..793..937..1093..1261..1441..1633
.19..63.139.253.411..619..883.1209.1603.2071.2619.3253..3979..4803..5731..6769
.28.109.268.529.916.1453.2164.3073.4204.5581.7228.9169.11428.14029.16996.20353

Column 1 is A000930
Column 2 is A003229(n-1)
Column 3 is A084386
Column 4 is A089977
Column 10 is A178205
Row 3 is A000027(n+1)
Row 4 is A004273(n+1)
Row 5 is A016777
Row 6 is A028872(n+2)
Row 7 is A144390(n+1)
Row 8 is A003154(n+1)

T(n,k)=Number of ways to place any number of 4X1 tiles of k distinguishable
colors into an nX1 grid

Table starts
..1...1...1...1....1....1....1....1....1....1....1.....1.....1.....1.....1
..1...1...1...1....1....1....1....1....1....1....1.....1.....1.....1.....1
..1...1...1...1....1....1....1....1....1....1....1.....1.....1.....1.....1
..2...3...4...5....6....7....8....9...10...11...12....13....14....15....16
..3...5...7...9...11...13...15...17...19...21...23....25....27....29....31
..4...7..10..13...16...19...22...25...28...31...34....37....40....43....46
..5...9..13..17...21...25...29...33...37...41...45....49....53....57....61
..7..15..25..37...51...67...85..105..127..151..177...205...235...267...301
.10..25..46..73..106..145..190..241..298..361..430...505...586...673...766
.14..39..76.125..186..259..344..441..550..671..804...949..1106..1275..1456
.19..57.115.193..291..409..547..705..883.1081.1299..1537..1795..2073..2371
.26..87.190.341..546..811.1142.1545.2026.2591.3246..3997..4850..5811..6886
.36.137.328.633.1076.1681.2472.3473.4708.6201.7976.10057.12468.15233.18376

Column 1 is A003269(n+1)
Column 2 is A052942
Column 3 is A143454(n-3)
Row 4 is A000027(n+1)
Row 5 is A004273(n+1)
Row 6 is A016777
Row 7 is A004766
Row 8 is A082111
Row 9 is A100536(n+1)
Row 10 is A051866(n+1)

T(n,k)=Number of ways to place any number of 5X1 tiles of k distinguishable
colors into an nX1 grid

Table starts
..1..1...1...1...1...1...1....1....1....1....1....1....1....1....1....1....1
..1..1...1...1...1...1...1....1....1....1....1....1....1....1....1....1....1
..1..1...1...1...1...1...1....1....1....1....1....1....1....1....1....1....1
..1..1...1...1...1...1...1....1....1....1....1....1....1....1....1....1....1
..2..3...4...5...6...7...8....9...10...11...12...13...14...15...16...17...18
..3..5...7...9..11..13..15...17...19...21...23...25...27...29...31...33...35
..4..7..10..13..16..19..22...25...28...31...34...37...40...43...46...49...52
..5..9..13..17..21..25..29...33...37...41...45...49...53...57...61...65...69
..6.11..16..21..26..31..36...41...46...51...56...61...66...71...76...81...86
..8.17..28..41..56..73..92..113..136..161..188..217..248..281..316..353..392
.11.27..49..77.111.151.197..249..307..371..441..517..599..687..781..881..987
.15.41..79.129.191.265.351..449..559..681..815..961.1119.1289.1471.1665.1871
.20.59.118.197.296.415.554..713..892.1091.1310.1549.1808.2087.2386.2705.3044
.26.81.166.281.426.601.806.1041.1306.1601.1926.2281.2666.3081.3526.4001.4506

Column 1 is A003520
Column 2 is A143447(n-4)
Column 3 is A143455(n-4)
Row 5 is A000027(n+1)
Row 6 is A004273(n+1)
Row 7 is A016777
Row 8 is A004766
Row 9 is A016861
Row 10 is A028884

T(n,k)=Number of ways to place any number of 6X1 tiles of k distinguishable
colors into an nX1 grid

Table starts
..1..1...1...1...1...1...1...1...1....1....1....1....1....1....1....1....1....1
..1..1...1...1...1...1...1...1...1....1....1....1....1....1....1....1....1....1
..1..1...1...1...1...1...1...1...1....1....1....1....1....1....1....1....1....1
..1..1...1...1...1...1...1...1...1....1....1....1....1....1....1....1....1....1
..1..1...1...1...1...1...1...1...1....1....1....1....1....1....1....1....1....1
..2..3...4...5...6...7...8...9..10...11...12...13...14...15...16...17...18...19
..3..5...7...9..11..13..15..17..19...21...23...25...27...29...31...33...35...37
..4..7..10..13..16..19..22..25..28...31...34...37...40...43...46...49...52...55
..5..9..13..17..21..25..29..33..37...41...45...49...53...57...61...65...69...73
..6.11..16..21..26..31..36..41..46...51...56...61...66...71...76...81...86...91
..7.13..19..25..31..37..43..49..55...61...67...73...79...85...91...97..103..109
..9.19..31..45..61..79..99.121.145..171..199..229..261..295..331..369..409..451
.12.29..52..81.116.157.204.257.316..381..452..529..612..701..796..897.1004.1117
.16.43..82.133.196.271.358.457.568..691..826..973.1132.1303.1486.1681.1888.2107
.21.61.121.201.301.421.561.721.901.1101.1321.1561.1821.2101.2401.2721.3061.3421

Column 1 is A005708
Column 2 is A143448(n-5)
Column 3 is A143456(n-5)
Row 6 is A000027(n+1)
Row 7 is A004273(n+1)
Row 8 is A016777
Row 9 is A004766
Row 10 is A016861
Row 11 is A016921
Row 12 is A190576(n+1)
Row 15 is A069133(n+1)

rhhardin at mindspring.com
rhhardin at att.net (either)

----- Original Message ----
> From: "israel at math.ubc.ca" <israel at math.ubc.ca>
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> Sent: Mon, July 25, 2011 1:18:16 PM
> Subject: [seqfan] Re: A193376 Tabl = 20 existing sequences
>
> Yes, with z+1 tiles on an n x 1 grid (with n >= z), either there is a tile
> (of any of the k colours) on the first spot, followed by any configuration
> on the remaining (n-z) x 1 grid, or the first spot is vacant, followed by
> any configuration on the remaining (n-1) x 1. So T(n,k) = T(n-1,k) +
> k*T(n-z,k), with T(n,k) = 1 for n=0,1,...,z-1. The solution is T(n,k) =
> sum_r r^(-n-1)/(1 + z k r^(z-1)) where the sum is over the roots of the
> polynomial k x^z + x - 1.
>
> Robert Israel                                  israel at math.ubc.ca
> Department of  Mathematics        http://www.math.ubc.ca/~israel
> University of British  Columbia            Vancouver, BC,  Canada
>
> On Jul 25 2011, Ron Hardin wrote:
>
> >experimentally zX1  tiles give a table with the corresponding
> >a(n)=a(n-1)+k*a(n-z) column  recurrences, taking a quick spot preview.

```