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

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 3, 1, 1, 1, 4, 5, 4, 1, 1, 1, 5, 7, 7, 5, 1, 1, 1, 6, 9, 10, 9, 7, 1, 1, 1, 7, 11, 13, 13, 15, 10, 1, 1, 1, 8, 13, 16, 17, 25, 25, 14, 1, 1, 1, 9, 15, 19, 21, 37, 46, 39, 19, 1, 1, 1, 10, 17, 22, 25, 51, 73, 76, 57, 26, 1, 1, 1, 11, 19, 25, 29, 67, 106, 125, 115, 87, 36

Offset

1,10

Links

R. H. Hardin, Table of n, a(n) for n = 1..9999

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..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/4]} binomial(n-3*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

Example

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
   2   3   4   5    6    7    8    9   10   11   12    13    14
   3   5   7   9   11   13   15   17   19   21   23    25    27
   4   7  10  13   16   19   22   25   28   31   34    37    40
   5   9  13  17   21   25   29   33   37   41   45    49    53
   7  15  25  37   51   67   85  105  127  151  177   205   235
  10  25  46  73  106  145  190  241  298  361  430   505   586
  14  39  76 125  186  259  344  441  550  671  804   949  1106
  19  57 115 193  291  409  547  705  883 1081 1299  1537  1795
  26  87 190 341  546  811 1142 1545 2026 2591 3246  3997  4850
  36 137 328 633 1076 1681 2472 3473 4708 6201 7976 10057 12468
Some solutions for n=9 k=3; colors=1, 2, 3; empty=0
..0....3....0....0....3....3....0....0....0....0....2....2....0....0....1....2
..1....3....0....2....3....3....3....0....0....0....2....2....1....0....1....2
..1....3....0....2....3....3....3....2....0....0....2....2....1....0....1....2
..1....3....3....2....3....3....3....2....1....0....2....2....1....0....1....2
..1....0....3....2....0....3....3....2....1....0....2....0....1....0....0....0
..2....3....3....2....0....3....3....2....1....3....2....2....0....0....0....3
..2....3....3....2....0....3....3....0....1....3....2....2....0....0....0....3
..2....3....0....2....0....3....3....0....0....3....2....2....0....0....0....3
..2....3....0....2....0....0....3....0....0....3....0....2....0....0....0....3

Maple

T:= proc(n, k) option remember;
      `if`(n<0, 0,
      `if`(n<4 or k=0, 1, k*T(n-4, 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 < 4 || k == 0, 1, k*T[n-4, k]+T[n-1, k]]]; Table[Table[T[n, d+1-n], {n, 1, d}], {d, 1, 13}] // Flatten (* Jean-François Alcover, Mar 04 2014, after Alois P. Heinz *)

Crossrefs

Column 1 is A003269(n+1),

Column 2 is A052942,

Column 3 is A143454(n-3),

Row 8 is A082111,

Row 9 is A100536(n+1),

Row 10 is A051866(n+1).

Sequence in context: A373362 A373145 A096815 * A124445 A124279 A297299

Adjacent sequences: A193513 A193514 A193515 * A193517 A193518 A193519

Keyword

nonn,tabl

Author

R. H. Hardin, with proof and formula from Robert Israel in the Sequence Fans Mailing List, Jul 29 2011

Status

approved