login
A373547
Triangle read by rows: T(n,k) = 4^k*binomial(n+k, n-k) with 0 <= k <= n.
1
1, 1, 4, 1, 12, 16, 1, 24, 80, 64, 1, 40, 240, 448, 256, 1, 60, 560, 1792, 2304, 1024, 1, 84, 1120, 5376, 11520, 11264, 4096, 1, 112, 2016, 13440, 42240, 67584, 53248, 16384, 1, 144, 3360, 29568, 126720, 292864, 372736, 245760, 65536, 1, 180, 5280, 59136, 329472, 1025024, 1863680, 1966080, 1114112, 262144
OFFSET
0,3
COMMENTS
T(n,k) is the number of occurrences of the periodic substring (01)^k in the periodic string (0011)^n (see Proposition 4.3 at page 6 in Fang).
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).
LINKS
Wenjie Fang, Maximal number of subword occurrences in a word, arXiv:2406.02971 [math.CO], 2024.
FORMULA
G.f.: (1 - x)/((1 - x)^2 - 4*x*y).
T(n,k) = A000302(k)*A085478(n,k).
Sum_{k=0..n} T(n-k,k) = A046717(n).
T(n,2) = A130810(n+2).
T(n,3) = A130812(n+3).
EXAMPLE
The triangle begins as:
1;
1, 4;
1, 12, 16;
1, 24, 80, 64;
1, 40, 240, 448, 256;
1, 60, 560, 1792, 2304, 1024;
1, 84, 1120, 5376, 11520, 11264, 4096;
...
T(2,1) = 12 since there are 12 occurrences of (01)^1 = 01 in (0011)^2 = 00110011: {1, 3}, {1, 4}, {1, 7}, {1, 8}, {2, 3}, {2, 4}, {2, 7}, {2, 8}, {5, 7}, {5, 8}, {6, 7}, {6, 8}.
MATHEMATICA
T[n_, k_]:=4^k Binomial[n+k, n-k]; Table[T[n, k], {n, 0, 9}, {k, 0, n}]//Flatten (* or *)
T[n_, k_]:=SeriesCoefficient[(1-x)/((1-x)^2-4x y), {x, 0, n}, {y, 0, k}]; Table[T[n, k], {n, 0, 9}, {k, 0, n}]//Flatten
CROSSREFS
Cf. A000012 (k=0), A000302 (diagonal), A001653 (row sums), A046092 (k=1), A046717, A085478, A130810, A130812, A373628.
Sequence in context: A157394 A338864 A078219 * A370129 A187541 A117413
KEYWORD
nonn,tabl
AUTHOR
Stefano Spezia, Jun 09 2024
STATUS
approved