

A341761


Triangle read by rows in which row n is the coefficients of the subword complexity polynomial S(n,x).


1



0, 0, 1, 0, 1, 3, 0, 0, 3, 6, 0, 1, 1, 6, 10, 0, 2, 6, 4, 10, 15, 0, 2, 10, 18, 10, 15, 21, 0, 2, 12, 31, 41, 20, 21, 28, 0, 1, 11, 41, 76, 80, 35, 28, 36, 0, 2, 6, 37, 109, 161, 141, 56, 36, 45, 0, 0, 9, 29, 110, 251, 308, 231, 84, 45, 55
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,6


COMMENTS

S(n,x) is the sum of subword complexities (number of nonempty distinct subwords) of all words of length n and an alphabet with size x.
Note that although the coefficients can be negative, S(n,x) is always a nonnegative number for n,x >= 0.
The degree of S(n,x) is n.
The constant coefficient of S(n,x) is always 0.
Conjecture: the coefficient of x^n in S(n,x) is n*(n+1)/2.


LINKS



EXAMPLE

The triangle begins as
0;
0, 1;
0, 1, 3;
0, 0, 3, 6;
0, 1, 1, 6, 10;
0, 2, 6, 4, 10, 15;
0, 2, 10, 18, 10, 15, 21;
0, 2, 12, 31, 41, 20, 21, 28;
...
Below lists some subword complexity polynomials:
S(0,x) = 0
S(1,x) = 1*x
S(2,x) = 1*x + 3*x^2
S(3,x) = 3*x^2 + 6*x^3
S(4,x) = 1*x + x^2  6*x^3 + 10*x^4
...
For n = 3 and x = 2 there are eight possible words: "aaa", "aab", "aba", "abb", "baa", "bab", "bba" and "bbb", and their subword complexities are 3, 5, 5, 5, 5, 5, 5 and 3 respectively, and their sum = S(3,2) = 3*(2^2)+6*(2^3) = 36.


MATHEMATICA

S[n_, x_] := Total[Length /@ DeleteDuplicates /@ Subsequences /@ Tuples[Table[i, {i, 0, x}], n]  1]; A341761[n_] := CoefficientList[FindSequenceFunction[ParallelTable[S[n, i], {i, 0, n + 1}], x], {x}]; Join[{0, 0, 1}, Table[A341761[n], {n, 2, 7}] // Flatten] (* Robert P. P. McKone, Feb 20 2021 *)


PROG

(C++) (* see link above *)


CROSSREFS



KEYWORD



AUTHOR



STATUS

approved



