|
| |
|
|
A340242
|
|
Square array read by upward antidiagonals: T(n,k) is the number of n-ary strings of length k containing 000.
|
|
3
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
2,3
|
|
|
LINKS
|
|
|
|
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
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
