A340156 Square array read by upward antidiagonals: T(n, k) is the number of n-ary strings of length k containing 00.

1, 1, 3, 1, 5, 8, 1, 7, 21, 19, 1, 9, 40, 79, 43, 1, 11, 65, 205, 281, 94, 1, 13, 96, 421, 991, 963, 201, 1, 15, 133, 751, 2569, 4612, 3217, 423, 1, 17, 176, 1219, 5531, 15085, 20905, 10547, 880, 1, 19, 225, 1849, 10513, 39186, 86241, 92935, 34089, 1815

Offset

2,3

Links

Robert P. P. McKone, Antidiagonals n = 2..100, flattened

Formula

T(n, k) = n^k - A180165(n+1,k-1), where A180165 in the number of strings not containing 00.

m(2) = [1 - 1/n, 1/n, 0; 1 - 1/n, 0, 1/n; 0, 0, 1], is the probability/transition matrix for two consecutive "0" -> "containing 00".

From A.H.M. Smeets, May 07 2026: (Start)

Row n is a linear recurrence with constant coefficients, signature (2*n-1, -(n-1)^2, -n*(n-1)) and starting values (0, 0, 1) for k = 0, 1, 2.

T(2,k) = A008466(k) = 2^k - A000045(k+2).

T(3,k) = A186244(k) = 3^k - A028859(k).

T(4,k) = A351529(k) = 4^k - A125145(k).

T(5,k) = A351530(k) = 5^k - A086347(k).

T(6,k) = A395827(k) = 6^k - A180033(k).

T(7,k) = A395828(k) = 7^k - A180167(k).

T(8,k) = A395829(k) = 8^k - A395831(k).

T(10,k) = A322053(k) = 10^k - A322054(k).

T(16,k) = A395830(k) = 16^k - A395832(k). (End)

Example

For n = 3 and k = 4, there are 21 strings: {0000, 0001, 0002, 0010, 0011, 0012, 0020, 0021, 0022, 0100, 0200, 1000, 1001, 1002, 1100, 1200, 2000, 2001, 2002, 2100, 2200}.
Square table T(n,k):
     k=2:  k=3:  k=4:   k=5:    k=6:     k=7:
n=2:   1     3     8     19      43       94
n=3:   1     5    21     79     281      963
n=4:   1     7    40    205     991     4612
n=5:   1     9    65    421    2569    15085
n=6:   1    11    96    751    5531    39186
n=7:   1    13   133   1219   10513    87199
n=8:   1    15   176   1849   18271   173608
n=9:   1    17   225   2665   29681   317817

Mathematica

m[r_] := Normal[With[{p = 1/n}, SparseArray[{Band[{1, 2}] -> p, {i_, 1} /; i <= r -> 1 - p, {r + 1, r + 1} -> 1}]]];
T[n_, k_, r_] := MatrixPower[m[r], k][[1, r + 1]]*n^k;
Reverse[Table[T[n, k - n + 2, 2], {k, 2, 11}, {n, 2, k}], 2] // Flatten (* Robert P. P. McKone, Jan 26 2021 *)

Prog

(Python)
T, n = [], 0
while n < 14:
    if n < 2: A = [0, 0, 0, 0]
    else: A = [0, 0, 1]
    k, s0, s1, s2 = 3, 2*n-1, -(n-1)**2, -n*(n-1)
    while k < 14-n: A, k = A+[s0*A[k-1]+s1*A[k-2]+s2*A[k-3]], k+1
    T, n = T+[A], n+1
f, g, n = 2, 0, 2
while f <= 56:
    while n-g > 1:
        print(T[n-g][g+2], end = ", ")
        f, g = f+1, g+1
    g, n = 0, n+1 # A.H.M. Smeets, May 06 2026

Crossrefs

Cf. A008466 (row 2), A186244 (row 3), A351529 (row 4), A351530 (row 5), A322053 (row 10), A000567 (column 4).

Cf. A180165 (not containing 00), A340242 (containing 000).

Cf. A000045, A028859, A125145, A086347, A180033, A180167, A322054.

Cf. A005563, A033445.

Sequence in context: A038738 A210741 A208760 * A340242 A116647 A063858

Adjacent sequences: A340153 A340154 A340155 * A340157 A340158 A340159

Keyword

nonn,tabl

Author

Robert P. P. McKone, Dec 29 2020

Status

approved