A340156 - OEIS

A340156

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

1, 1, 3, 1, 5, 8, 1, 7, 21, 19, 1, 9, 40, 79, 43, 1, 11, 65, 205, 281, 94, 1, 13, 96, 421, 991, 963, 201, 1, 15, 133, 751, 2569, 4612, 3217, 423, 1, 17, 176, 1219, 5531, 15085, 20905, 10547, 880, 1, 19, 225, 1849, 10513, 39186, 86241, 92935, 34089, 1815

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

2,3

LINKS

Robert P. P. McKone, Antidiagonals n = 2..100, flattened

FORMULA

T(n, k) = n^k - A180165(n+1,k-1), where A180165 in the number of strings not containing 00.

m(2) = [1 - 1/n, 1/n, 0; 1 - 1/n, 0, 1/n; 0, 0, 1], is the probability/transition matrix for two consecutive "0" -> "containing 00".

EXAMPLE

For n = 3 and k = 4, there are 21 strings: {0000, 0001, 0002, 0010, 0011, 0012, 0020, 0021, 0022, 0100, 0200, 1000, 1001, 1002, 1100, 1200, 2000, 2001, 2002, 2100, 2200}.

Square table T(n,k):

k=2: k=3: k=4: k=5: k=6: k=7:

n=2: 1 3 8 19 43 94

n=3: 1 5 21 79 281 963

n=4: 1 7 40 205 991 4612

n=5: 1 9 65 421 2569 15085

n=6: 1 11 96 751 5531 39186

n=7: 1 13 133 1219 10513 87199

n=8: 1 15 176 1849 18271 173608

n=9: 1 17 225 2665 29681 317817

MATHEMATICA

m[r_] := Normal[With[{p = 1/n}, SparseArray[{Band[{1, 2}] -> p, {i_, 1} /; i <= r -> 1 - p, {r + 1, r + 1} -> 1}]]];