A141539 Square array A(n,k) of numbers of length n binary words with at least k "0" between any two "1" digits (n,k >= 0), read by antidiagonals.

1, 1, 2, 1, 2, 4, 1, 2, 3, 8, 1, 2, 3, 5, 16, 1, 2, 3, 4, 8, 32, 1, 2, 3, 4, 6, 13, 64, 1, 2, 3, 4, 5, 9, 21, 128, 1, 2, 3, 4, 5, 7, 13, 34, 256, 1, 2, 3, 4, 5, 6, 10, 19, 55, 512, 1, 2, 3, 4, 5, 6, 8, 14, 28, 89, 1024, 1, 2, 3, 4, 5, 6, 7, 11, 19, 41, 144, 2048, 1, 2, 3, 4, 5, 6, 7, 9, 15, 26, 60, 233, 4096

Offset: 0

Author

Alois P. Heinz, Aug 15 2008

Keywords

• nonn
• tabl

Comments

A(n,k+1) = A(n,k) - A143291(n,k).

From Gary W. Adamson, Dec 19 2009: (Start)

Alternative method generated from variants of an infinite lower triangle T(n) = A000012 = (1; 1,1; 1,1,1; ...) such that T(n) has the leftmost column shifted up n times. Then take lim_{k->infinity} T(n)^k, obtaining a left-shifted vector considered as rows of an array (deleting the first 1) as follows:

1, 2, 4, 8, 16, 32, 64, 128, 256, ... = powers of 2

1, 1, 2, 3, 5, 8, 13, 21, 34, ... = Fibonacci numbers

1, 1, 1, 2, 3, 4, 6, 9, 13, ... = A000930

1, 1, 1, 1, 2, 3, 4, 5, 7, ... = A003269

... with the next rows A003520, A005708, A005709, ... such that beginning with the Fibonacci row, the succession of rows are recursive sequences generated from a(n) = a(n-1) + a(n-2); a(n) = a(n-1) + a(n-3), ... a(n) = a(n-1) + a(n-k); k = 2,3,4,... Last, columns going up from the topmost 1 become rows of triangle A141539. (End)

Examples

			A(4,2) = 6, because 6 binary words of length 4 have at least 2 "0" between any two "1" digits: 0000, 0001, 0010, 0100, 1000, 1001.
Square array A(n,k) begins:
    1,  1,  1,  1,  1,  1,  1,  1, ...
    2,  2,  2,  2,  2,  2,  2,  2, ...
    4,  3,  3,  3,  3,  3,  3,  3, ...
    8,  5,  4,  4,  4,  4,  4,  4, ...
   16,  8,  6,  5,  5,  5,  5,  5, ...
   32, 13,  9,  7,  6,  6,  6,  6, ...
   64, 21, 13, 10,  8,  7,  7,  7, ...
  128, 34, 19, 14, 11,  9,  8,  8, ...
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..140, flattened

Crossrefs

Cf. column k=0: A000079, k=1: A000045(n+2), k=2: A000930(n+2), A068921, A078012(n+5), k=3: A003269(n+4), A017898(n+7), k=4: A003520(n+4), A017899(n+9), k=5: A005708(n+5), A017900(n+11), k=6: A005709(n+6), A017901(n+13), k=7: A005710(n+7), A017902(n+15), k=8: A005711(n+7), A017903(n+17), k=9: A017904(n+19), k=10: A017905(n+21), k=11: A017906(n+23), k=12: A017907(n+25), k=13: A017908(n+27), k=14: A017909(n+29).

Main diagonal gives A000027(n+1).

A(2n,n) gives A000217(n+1)

A(3n,n) gives A008778.

A(3n,2n) gives A034856(n+1).

A(2n,3n) gives A005408.

A(2^n-1,n) gives A376697.

See also A143291.

Programs

Maple

A:= proc(n, k) option remember;
      if k=0 then 2^n
    elif n<=k and n>=0 then n+1
    elif n>0 then A(n-1, k) +A(n-k-1, k)
    else          A(n+1+k, k) -A(n+k, k)
      fi
    end:
seq(seq(A(n, d-n), n=0..d), d=0..15);

Mathematica

a[n_, k_] := a[n, k] = Which[k == 0, 2^n, n <= k && n >= 0, n+1, n > 0, a[n-1, k] + a[n-k-1, k], True, a[n+1+k, k] - a[n+k, k]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Dec 17 2013, translated from Maple *)

Formula

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

A(n,k) = 2^n if k=0, otherwise A(n,k) = n+1 if n<=k, otherwise A(n,k) = A(n-1,k) + A(n-k-1,k).