Shiyao Guo - cp's OEIS frontend

User: Shiyao Guo

Shiyao Guo has authored 2 sequences.

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

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

Offset: 0

Shiyao Guo, Feb 19 2021

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.

			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.

Shiyao Guo, Table of n, a(n) for n = 0..1890
Shiyao Guo, On the Expected Subword Complexity of Random Words.
Shiyao Guo, C++ program that computes subword complexity polynomial for n up to 60.

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

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

A340885 Sum of subword complexity (number of nonempty distinct subwords) of all binary strings of length n.

Original entry on oeis.org

0, 2, 10, 36, 114, 332, 916, 2428, 6242, 15652, 38460, 92916, 221256, 520332, 1210448, 2789100, 6372498, 14450420, 32547188, 72861376, 162211196, 359318644, 792287340, 1739623672, 3804904316, 8292351960, 18012452664, 39006099616, 84226667004, 181387693028, 389657293304

Offset: 0

Shiyao Guo, Jan 25 2021

nonn

a(n)/(2^n) is the expected subword complexity of a random binary string of length n.

All terms are even.

			For n = 2 there are four possible binary strings: "aa", "ab", "ba", "bb", and their subword complexities are 2, 3, 3 and 2 respectively, and their sum = a(2) = 10.

Shiyao Guo, Table of n, a(n) for n = 0..60
Shiyao Guo, C++ program used to compute values for n up to 60

Cf. A282949 (distinct complexity profiles), A094913 (maximum complexity), A134457 (numbers of strings achieving the maximum complexity).

cp's OEIS Frontend

User: Shiyao Guo

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica