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

1, 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 5, 4, 1, 1, 5, 7, 7, 6, 1, 1, 6, 9, 10, 13, 9, 1, 1, 7, 11, 13, 22, 23, 13, 1, 1, 8, 13, 16, 33, 43, 37, 19, 1, 1, 9, 15, 19, 46, 69, 73, 63, 28, 1, 1, 10, 17, 22, 61, 101, 121, 139, 109, 41, 1, 1, 11, 19, 25, 78, 139, 181, 253, 268, 183, 60

Offset

1,6

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/3]} binomial(n-2*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
   2   3   4    5    6    7     8     9    10    11    12    13
   3   5   7    9   11   13    15    17    19    21    23    25
   4   7  10   13   16   19    22    25    28    31    34    37
   6  13  22   33   46   61    78    97   118   141   166   193
   9  23  43   69  101  139   183   233   289   351   419   493
  13  37  73  121  181  253   337   433   541   661   793   937
  19  63 139  253  411  619   883  1209  1603  2071  2619  3253
  28 109 268  529  916 1453  2164  3073  4204  5581  7228  9169
  41 183 487 1013 1821 2971  4523  6537  9073 12191 15951 20413
  60 309 904 2025 3876 6685 10704 16209 23500 32901 44760 59449
Some solutions for n=7 k=3; colors=1,2,3 and empty=0
..3....0....0....2....0....1....3....0....0....0....1....0....3....1....0....0
..3....0....0....2....2....1....3....2....1....0....1....3....3....1....0....0
..3....1....0....2....2....1....3....2....1....2....1....3....3....1....0....3
..1....1....3....0....2....0....0....2....1....2....3....3....0....2....0....3
..1....1....3....0....0....2....2....2....1....2....3....2....1....2....1....3
..1....0....3....0....0....2....2....2....1....0....3....2....1....2....1....0
..0....0....0....0....0....2....2....2....1....0....0....2....1....0....1....0

Maple

T:= proc(n, k) option remember;
      `if`(n<0, 0,
      `if`(n<3 or k=0, 1, k*T(n-3, 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

nmax = 13; t[_?Negative, _] = 0; t[n_, k_] /; (n < 3 || k == 0) = 1; t[n_, k_] := t[n, k] = k*t[n-3, k] + t[n-1, k]; Flatten[ Table[ t[n-k+1, k], {n, 1, nmax}, {k, n, 1, -1}]] (* Jean-François Alcover, Nov 28 2011, after Maple *)

Crossrefs

Column 1 is A000930,

Column 2 is A003229(n-1),

Column 3 is A084386,

Column 4 is A089977,

Column 10 is A178205,

Row 6 is A028872(n+2),

Row 7 is A144390(n+1),

Row 8 is A003154(n+1).

Sequence in context: A174448 A077028 A114225 * A259874 A256141 A072704

Adjacent sequences: A193512 A193513 A193514 * A193516 A193517 A193518

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