A373628 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, 1, 9, 1, 81, 81, 1, 351, 1377, 729, 1, 1035, 11421, 18225, 6561, 1, 2430, 62613, 223803, 216513, 59049, 1, 4914, 259119, 1813023, 3523257, 2421009, 531441, 1, 8946, 874071, 10978740, 37850409, 49069719, 26040609, 4782969, 1, 15066, 2525499, 53362800, 303255981, 657274419, 631883349, 272629233, 43046721

Offset: 0

Author

Stefano Spezia, Jun 11 2024

Keywords

• nonn
• tabl

Comments

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.

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).

Examples

			The triangle begins as:
  1;
  1,    9;
  1,   81,    81;
  1,  351,  1377,    729;
  1, 1035, 11421,  18225,   6561;
  1, 2430, 62613, 223803, 216513, 59049;
  ...
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}.
		

Links

• Wenjie Fang, Maximal number of subword occurrences in a word, arXiv:2406.02971 [math.CO], 2024. See Proposition 4.10 at page 9 in Fang.

Crossrefs

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

Programs

Mathematica

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

Formula

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