OFFSET
1,3
COMMENTS
Transposed variant of A083856. - R. J. Mathar, Aug 23 2011
As to the sequences by columns beginning (1, N, ...), let m = (N-1). The g.f. for the sequence (1, N, ...) is 1/(1 - x - m*x^2). Alternatively, the corresponding matrix generator is [[1,1], [m,0]]. Another equivalency is simply: The sequence beginning (1, N, ...) is the INVERT transform of (1, m, 0, 0, 0, ...). Convergents to the sequences a(n)/a(n-1) are (1 + sqrt(4*m+1))/2. - Gary W. Adamson, Feb 25 2014
LINKS
R. H. Hardin, Table of n, a(n) for n = 1..9999
Ron H. Hardin, Re: A193376 Tabl = 20 existing sequences, Sequence Fans mailing list, 2011.
Robert Israel, Re: A193376 Tabl = 20 existing sequences, Sequence Fans mailing list, 2011.
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. Thus, 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 r of the polynomial k*x^z + x - 1.
For z = 2, T(n,k) = ((2*k / (sqrt(1 + 4*k) - 1))^(n+1) - (-2*k/(sqrt(1 + 4*k) + 1))^(n+1)) / sqrt(1 + 4*k).
T(n,k) = Sum_{s=0..[n/2]} binomial(n-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
Array T(n,k) (with rows n >= 1 and column k >= 1) begins as follows:
..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...
..5..11...19...29....41....55....71.....89....109....131....155....181...
..8..21...40...65....96...133...176....225....280....341....408....481...
.13..43...97..181...301...463...673....937...1261...1651...2113...2653...
.21..85..217..441...781..1261..1905...2737...3781...5061...6601...8425...
.34.171..508.1165..2286..4039..6616..10233..15130..21571..29844..40261...
.55.341.1159.2929..6191.11605.19951..32129..49159..72181.102455.141361...
.89.683.2683.7589.17621.35839.66263.113993.185329.287891.430739.624493...
...
Some solutions for n = 5 and k = 3 with colors = 1, 2, 3 and empty = 0:
..0....2....3....2....0....1....0....0....2....0....0....2....3....0....0....0
..0....2....3....2....2....1....2....3....2....1....0....2....3....1....1....1
..1....0....0....0....2....0....2....3....2....1....0....1....0....1....1....1
..1....2....2....0....3....2....2....3....2....0....3....1....3....3....2....1
..0....2....2....0....3....2....2....3....0....0....3....0....3....3....2....1
MAPLE
T:= proc(n, k) option remember; `if`(n<0, 0,
`if`(n<2 or k=0, 1, k*T(n-2, k) +T(n-1, k)))
end;
seq(seq(T(n, d+1-n), n=1..d), d=1..12); # Alois P. Heinz, Jul 29 2011
MATHEMATICA
T[n_, k_] := T[n, k] = If[n < 0, 0, If[n < 2 || k == 0, 1, k*T[n-2, k]+T[n-1, k]]]; Table[Table[T[n, d+1-n], {n, 1, d}], {d, 1, 12}] // Flatten (* Jean-François Alcover, Mar 04 2014, after Alois P. Heinz *)
CROSSREFS
Column 1 is A000045(n+1), column 2 is A001045(n+1), column 3 is A006130, column 4 is A006131, column 5 is A015440, column 6 is A015441(n+1), column 7 is A015442(n+1), column 8 is A015443, column 9 is A015445, column 10 is A015446, column 11 is A015447, and column 12 is A053404,
KEYWORD
nonn,tabl
AUTHOR
R. H. Hardin, Jul 24 2011
EXTENSIONS
Formula and proof from Robert Israel in the Sequence Fans mailing list.
STATUS
approved