%I #39 Aug 16 2021 13:58:34
%S 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,
%T 1021,1037,238,1,15,133,756,2621,4831,3555,520,1,17,176,1225,5611,
%U 15569,22276,11961,1121,1,19,225,1856,10627,40091,90085,100768,39667,2391
%N Square array read by upward antidiagonals: T(n,k) is the number of n-ary strings of length k containing 000.
%H Robert P. P. McKone, <a href="/A340242/b340242.txt">Antidiagonals n = 2..100, flattened</a>
%F 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".
%e 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}.
%e Square table T(n,k):
%e k=3: k=4: k=5: k=6: k=7: k=8:
%e n=2: 1 3 8 20 47 107
%e n=3: 1 5 21 81 295 1037
%e n=4: 1 7 40 208 1021 4831
%e n=5: 1 9 65 425 2621 15569
%e n=6: 1 11 96 756 5611 40091
%e n=7: 1 13 133 1225 10627 88717
%e n=8: 1 15 176 1856 18425 175967
%e n=9: 1 17 225 2673 29881 321281
%t m[r_] := Normal[With[{p = 1/n}, SparseArray[{Band[{1, 2}] -> p, {i_, 1} /; i <= r -> 1 - p, {r + 1, r + 1} -> 1}]]];
%t T[n_, k_, r_] := MatrixPower[m[r], k][[1, r + 1]]*n^k;
%t Reverse[Table[T[n, k - n + 3, 3], {k, 2, 11}, {n, 2, k}], 2] // Flatten
%o (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
%Y Rows: A050231 (n=2), A231430 (n=3).
%Y Columns: A000567 (k=5), A103532 (k=6).
%Y Cf. A340156 (containing 00).
%Y Cf. A341050.
%Y Cf. A000073, A068601.
%K nonn,tabl
%O 2,3
%A _Robert P. P. McKone_, Jan 01 2021