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

1, 1, 3, 1, 5, 8, 1, 7, 21, 20, 1, 9, 40, 81, 47, 1, 11, 65, 208, 295, 107, 1, 13, 96, 425, 1021, 1037, 238, 1, 15, 133, 756, 2621, 4831, 3555, 520, 1, 17, 176, 1225, 5611, 15569, 22276, 11961, 1121, 1, 19, 225, 1856, 10627, 40091, 90085, 100768, 39667, 2391

Offset: 2

Author

Robert P. P. McKone, Jan 01 2021

Keywords

• nonn
• tabl

Examples

			For n = 4 and k = 5, there are 40 strings: {00000, 00001, 00002, 00003, 00010, 00011, 00012, 00013, 00020, 00021, 00022, 00023, 00030, 00031, 00032, 00033, 01000, 02000, 03000, 10000, 10001, 10002, 10003, 11000, 12000, 13000, 20000, 20001, 20002, 20003, 21000, 22000, 23000, 30000, 30001, 30002, 30003, 31000, 32000, 33000}.
Square table T(n,k):
      k=3: k=4:  k=5:   k=6:    k=7:     k=8:
n=2:    1    3     8     20      47      107
n=3:    1    5    21     81     295     1037
n=4:    1    7    40    208    1021     4831
n=5:    1    9    65    425    2621    15569
n=6:    1   11    96    756    5611    40091
n=7:    1   13   133   1225   10627    88717
n=8:    1   15   176   1856   18425   175967
n=9:    1   17   225   2673   29881   321281
		

Links

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

Crossrefs

Rows: A050231 (n=2), A231430 (n=3).

Columns: A000567 (k=5), A103532 (k=6).

Cf. A340156 (containing 00).

Cf. A341050.

Cf. A000073, A068601.

Programs

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 + 3, 3], {k, 2, 11}, {n, 2, k}], 2] // Flatten

PARI

my(x2='x^2+'x+1); T(n,k) = n^k - polcoeff(lift(x2*Mod('x, 'x^3-(n-1)*x2)^k), 2); \\ Kevin Ryde, Jan 02 2021

Formula

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