cp's OEIS Frontend

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

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