A341761 - OEIS

%I #33 Mar 20 2024 16:36:35

%S 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,

%T -15,21,0,2,-12,31,-41,20,-21,28,0,-1,11,-41,76,-80,35,-28,36,0,2,-6,

%U 37,-109,161,-141,56,-36,45,0,0,9,-29,110,-251,308,-231,84,-45,55

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

%C 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.

%C Note that although the coefficients can be negative, S(n,x) is always a nonnegative number for n,x >= 0.

%C The degree of S(n,x) is n.

%C The constant coefficient of S(n,x) is always 0.

%C Conjecture: the coefficient of x^n in S(n,x) is n*(n+1)/2.

%H Shiyao Guo, <a href="/A341761/b341761.txt">Table of n, a(n) for n = 0..1890</a>

%H Shiyao Guo, <a href="https://mivik.gitee.io/2021/research/expected-subword-complexity-en/">On the Expected Subword Complexity of Random Words</a>.

%H Shiyao Guo, <a href="https://gist.github.com/Mivik/0dd1068c0d768aa7f53abd78f9d4cf0f">C++ program that computes subword complexity polynomial for n up to 60.</a>

%e The triangle begins as

%e   0;

%e   0,   1;

%e   0,  -1,   3;

%e   0,   0,  -3,   6;

%e   0,  -1,   1,  -6,  10;

%e   0,   2,  -6,   4, -10,  15;

%e   0,  -2,  10, -18,  10, -15,  21;

%e   0,   2, -12,  31, -41,  20, -21,  28;

%e   ...

%e Below lists some subword complexity polynomials:

%e   S(0,x) = 0

%e   S(1,x) =    1*x

%e   S(2,x) =   -1*x + 3*x^2

%e   S(3,x) =         -3*x^2 + 6*x^3

%e   S(4,x) =   -1*x +   x^2 - 6*x^3 + 10*x^4

%e   ...

%e 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.

%t 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 *)

%o (C++) // see link above

%Y Cf. A340885 (values of S(n,2)).

%K sign,tabl

%O 0,6

%A _Shiyao Guo_, Feb 19 2021