The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 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. 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 Cf. A340885 (values of S(n,2)). Sequence in context: A091921 A037285 A337981 * A181787 A318925 A285213 Adjacent sequences: A341758 A341759 A341760 * A341762 A341763 A341764 KEYWORD sign,tabl AUTHOR Shiyao Guo, Feb 19 2021 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 23 11:05 EDT 2023. Contains 365544 sequences. (Running on oeis4.)