A143461 Square array A(n,k) of numbers of length n quaternary words with at least k 0-digits between any other digits (n,k >= 0), read by antidiagonals.

1, 1, 4, 1, 4, 16, 1, 4, 7, 64, 1, 4, 7, 19, 256, 1, 4, 7, 10, 40, 1024, 1, 4, 7, 10, 22, 97, 4096, 1, 4, 7, 10, 13, 43, 217, 16384, 1, 4, 7, 10, 13, 25, 73, 508, 65536, 1, 4, 7, 10, 13, 16, 46, 139, 1159, 262144, 1, 4, 7, 10, 13, 16, 28, 76, 268, 2683, 1048576, 1, 4, 7, 10, 13, 16, 19, 49, 115, 487, 6160, 4194304

Offset: 0

Author

Alois P. Heinz, Aug 16 2008

Keywords

• nonn
• tabl

Examples

			A (3,1) = 19, because 19 quaternary words of length 3 have at least 1 0-digit between any other digits: 000, 001, 002, 003, 010, 020, 030, 100, 101, 102, 103, 200, 201, 202, 203, 300, 301, 301, 303.
Square array A(n,k) begins:
       1,   1,   1,  1,  1,  1,  1,  1,  ...
       4,   4,   4,  4,  4,  4,  4,  4,  ...
      16,   7,   7,  7,  7,  7,  7,  7,  ...
      64,  19,  10, 10, 10, 10, 10, 10,  ...
     256,  40,  22, 13, 13, 13, 13, 13,  ...
    1024,  97,  43, 25, 16, 16, 16, 16,  ...
    4096, 217,  73, 46, 28, 19, 19, 19,  ...
   16384, 508, 139, 76, 49, 31, 22, 22,  ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..140, flattened

Crossrefs

Columns k=0-9 give: A000302, A006130(n+1), A084386(n+2), A143454, A143455, A143456, A143457, A143458, A143459, A143460.

Main diagonal gives A016777.

Programs

Maple

A:= proc(n, k) option remember; if k=0 then 4^n elif n<=k+1 then 3*n+1 else A(n-1, k) +3*A(n-k-1, k) fi end: seq(seq(A(n, d-n), n=0..d), d=0..13);

Mathematica

a[n_, 0] := 4^n; a[n_, k_] /; n <= k+1 := 3*n+1; a[n_, k_] := a[n, k] = a[n-1, k] + 3*a[n-k-1, k]; Table[a[n-k, k], {n, 0, 13}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Jan 15 2014, after Maple *)

Formula

G.f. of column k: 1/(x^k*(1-x-3*x^(k+1))).

A(n,k) = 4^n if k=0, else A(n,k) = 3*n+1 if n<=k+1, else A(n,k) = A(n-1,k) + 3*A(n-k-1,k).