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,3

Links

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

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".

Example

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

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

Prog

(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

Crossrefs

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

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

Cf. A340156 (containing 00).

Cf. A341050.

Cf. A000073, A068601.

Sequence in context: A210741 A208760 A340156 * A116647 A063858 A209831

Adjacent sequences: A340239 A340240 A340241 * A340243 A340244 A340245

Keyword

nonn,tabl

Author

Robert P. P. McKone, Jan 01 2021

Status

approved