# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/ Search: id:a341761 Showing 1-1 of 1 %I A341761 #33 Mar 20 2024 16:36:35 %S A341761 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 A341761 -15,21,0,2,-12,31,-41,20,-21,28,0,-1,11,-41,76,-80,35,-28,36,0,2,-6, %U A341761 37,-109,161,-141,56,-36,45,0,0,9,-29,110,-251,308,-231,84,-45,55 %N A341761 Triangle read by rows in which row n is the coefficients of the subword complexity polynomial S(n,x). %C A341761 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 A341761 Note that although the coefficients can be negative, S(n,x) is always a nonnegative number for n,x >= 0. %C A341761 The degree of S(n,x) is n. %C A341761 The constant coefficient of S(n,x) is always 0. %C A341761 Conjecture: the coefficient of x^n in S(n,x) is n*(n+1)/2. %H A341761 Shiyao Guo, Table of n, a(n) for n = 0..1890 %H A341761 Shiyao Guo, On the Expected Subword Complexity of Random Words. %H A341761 Shiyao Guo, C++ program that computes subword complexity polynomial for n up to 60. %e A341761 The triangle begins as %e A341761 0; %e A341761 0, 1; %e A341761 0, -1, 3; %e A341761 0, 0, -3, 6; %e A341761 0, -1, 1, -6, 10; %e A341761 0, 2, -6, 4, -10, 15; %e A341761 0, -2, 10, -18, 10, -15, 21; %e A341761 0, 2, -12, 31, -41, 20, -21, 28; %e A341761 ... %e A341761 Below lists some subword complexity polynomials: %e A341761 S(0,x) = 0 %e A341761 S(1,x) = 1*x %e A341761 S(2,x) = -1*x + 3*x^2 %e A341761 S(3,x) = -3*x^2 + 6*x^3 %e A341761 S(4,x) = -1*x + x^2 - 6*x^3 + 10*x^4 %e A341761 ... %e A341761 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 A341761 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 A341761 (C++) // see link above %Y A341761 Cf. A340885 (values of S(n,2)). %K A341761 sign,tabl %O A341761 0,6 %A A341761 _Shiyao Guo_, Feb 19 2021 # Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE