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

%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