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