login
Triangle read by rows: T(n,k) is the number of occurrences of the periodic substring (0011)^k in the periodic string (000111)^n.
1

%I #13 Jun 12 2024 17:20:52

%S 1,1,9,1,81,81,1,351,1377,729,1,1035,11421,18225,6561,1,2430,62613,

%T 223803,216513,59049,1,4914,259119,1813023,3523257,2421009,531441,1,

%U 8946,874071,10978740,37850409,49069719,26040609,4782969,1,15066,2525499,53362800,303255981,657274419,631883349,272629233,43046721

%N Triangle read by rows: T(n,k) is the number of occurrences of the periodic substring (0011)^k in the periodic string (000111)^n.

%C The word (w_1, w_2, ..., w_r)^m is defined as the word obtained by concatenating (w_1, w_2, ..., w_r) m times.

%C A word w' = (w'_1, w'_2, ..., w'_s) is said be a subword of a given word w = (w_1, w_2, ..., w_r), if there is some set P = {p_1 < ... < p_s} of integers from 1 to r satisfying w_{p_j} = w'_j for all 1 <= j <= s, and we call the set P an occurrence of w' in w (see Preliminaries section at pp. 2-3 in Fang).

%H Wenjie Fang, <a href="http://www.arxiv.org/abs/2406.02971">Maximal number of subword occurrences in a word</a>, arXiv:2406.02971 [math.CO], 2024. See Proposition 4.10 at page 9 in Fang.

%F G.f.: (1 - x)^3/((1 - x)^4 - 9*x*(1 + 2*x)^2*y).

%e The triangle begins as:

%e 1;

%e 1, 9;

%e 1, 81, 81;

%e 1, 351, 1377, 729;

%e 1, 1035, 11421, 18225, 6561;

%e 1, 2430, 62613, 223803, 216513, 59049;

%e ...

%e T(1,1) = 9 since there are 9 occurrences of (0011)^1 = 0011 in (000111)^1 = 000111: {1, 2, 4, 5}, {1, 2, 4, 6}, {1, 2, 5, 6}, {1, 3, 4, 5}, {1, 3, 4, 6}, {1, 3, 5, 6}, {2, 3, 4, 5}, {2, 3, 4, 6}, {2, 3, 5, 6}.

%t T[n_, k_]:=SeriesCoefficient[(1-x)^3/((1-x)^4-9x(1+2x)^2y), {x, 0, n}, {y, 0, k}]; Table[T[n, k], {n, 0, 8}, {k, 0, n}]//Flatten

%Y Cf. A000012 (k=0), A001019 (diagonal), A085478, A373547.

%K nonn,tabl

%O 0,3

%A _Stefano Spezia_, Jun 11 2024