A193517 T(n,k) = number of ways to place any number of 5X1 tiles of k distinguishable colors into an nX1 grid.
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 4, 5, 4, 1, 1, 1, 1, 5, 7, 7, 5, 1, 1, 1, 1, 6, 9, 10, 9, 6, 1, 1, 1, 1, 7, 11, 13, 13, 11, 8, 1, 1, 1, 1, 8, 13, 16, 17, 16, 17, 11, 1, 1, 1, 1, 9, 15, 19, 21, 21, 28, 27, 15, 1, 1, 1, 1, 10, 17, 22, 25, 26, 41, 49, 41, 20, 1, 1, 1
Offset: 1
Examples
Some solutions for n=11 k=3; colors=1, 2, 3; empty=0 ..0....2....2....0....0....1....0....3....3....0....0....0....0....3....1....0 ..0....2....2....0....1....1....3....3....3....3....2....3....1....3....1....1 ..0....2....2....0....1....1....3....3....3....3....2....3....1....3....1....1 ..3....2....2....0....1....1....3....3....3....3....2....3....1....3....1....1 ..3....2....2....0....1....1....3....3....3....3....2....3....1....3....1....1 ..3....1....0....2....1....0....3....3....0....3....2....3....1....0....0....1 ..3....1....3....2....1....1....2....3....2....0....0....3....0....3....0....2 ..3....1....3....2....1....1....2....3....2....0....0....3....0....3....0....2 ..0....1....3....2....1....1....2....3....2....0....0....3....0....3....0....2 ..0....1....3....2....1....1....2....3....2....0....0....3....0....3....0....2 ..0....0....3....0....1....1....2....0....2....0....0....3....0....3....0....2
Links
- R. H. Hardin, Table of n, a(n) for n = 1..9999
Crossrefs
Programs
-
Maple
T:= proc(n, k) option remember; `if`(n<0, 0, `if`(n<5 or k=0, 1, k*T(n-5, k) +T(n-1, k))) end: seq(seq(T(n, d+1-n), n=1..d), d=1..13); # Alois P. Heinz, Jul 29 2011 -
Mathematica
T[n_, k_] := T[n, k] = If[n<0, 0, If[n < 5 || k == 0, 1, k*T[n-5, k]+T[n-1, k]]]; Table[Table[T[n, d+1-n], {n, 1, d}], {d, 1, 14}] // Flatten (* Jean-François Alcover, Mar 04 2014, after Alois P. Heinz *)
Formula
With z X 1 tiles of k colors on an n X 1 grid (with n >= z), either there is a tile (of any of the k colors) 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.
T(n,k) = sum {s=0..[n/5]} (binomial(n-4*s,s)*k^s).
For z X 1 tiles, T(n,k,z) = sum{s=0..[n/z]} (binomial(n-(z-1)*s,s)*k^s). - R. H. Hardin, Jul 31 2011
Comments