login
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.
6

%I #39 Oct 02 2024 17:41:37

%S 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,

%T 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,

%U 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

%N 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.

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

%C From _Gary W. Adamson_, Dec 19 2009: (Start)

%C 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:

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

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

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

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

%C ... 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)

%H Alois P. Heinz, <a href="/A141539/b141539.txt">Table of n, a(n) for n = 0..140, flattened</a>

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

%F 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).

%e 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.

%e Square array A(n,k) begins:

%e 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 2, 2, 2, 2, 2, 2, 2, 2, ...

%e 4, 3, 3, 3, 3, 3, 3, 3, ...

%e 8, 5, 4, 4, 4, 4, 4, 4, ...

%e 16, 8, 6, 5, 5, 5, 5, 5, ...

%e 32, 13, 9, 7, 6, 6, 6, 6, ...

%e 64, 21, 13, 10, 8, 7, 7, 7, ...

%e 128, 34, 19, 14, 11, 9, 8, 8, ...

%p A:= proc(n, k) option remember;

%p if k=0 then 2^n

%p elif n<=k and n>=0 then n+1

%p elif n>0 then A(n-1, k) +A(n-k-1, k)

%p else A(n+1+k, k) -A(n+k, k)

%p fi

%p end:

%p seq(seq(A(n, d-n), n=0..d), d=0..15);

%t 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 *)

%Y 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).

%Y Main diagonal gives A000027(n+1).

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

%Y A(3n,n) gives A008778.

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

%Y A(2n,3n) gives A005408.

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

%Y See also A143291.

%K nonn,tabl

%O 0,3

%A _Alois P. Heinz_, Aug 15 2008