A282949 -id:A282949 - cp's OEIS frontend

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

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

A283502 Number of distinct subword complexity profiles for purely periodic binary infinite words of period n.

Original entry on oeis.org

1, 2, 2, 4, 3, 7, 6, 13, 13, 23, 25, 47, 51, 87, 110, 176, 214, 342, 424, 676, 841, 1253, 1660

Offset: 1

Jeffrey Shallit, Mar 09 2017

The subword complexity function p_i(x) maps i to the number of distinct contiguous blocks (aka subwords, aka factors) of length i in an infinite word x. The subword complexity profile of an infinite word x is the infinite list (p_1 (x), p_2 (x), p_3 (x), ...). For a purely periodic infinite word x, of period n, it suffices to consider the finite list (p_1 (x), p_2 (x), ..., p_n (x)). Furthermore, if x = www... with w of length n, it suffices to consider the list (p_1 (ww), p_2 (ww), ..., p_n (ww)).

			For period n = 5, there are exactly three distinct subword complexity profiles:  (1,1,1,...) corresponding to the word 000...; (2,3,4,5,5,5,...) corresponding to the word 000010000100001...; and
(2,4,5,5,5,...) corresponding to the word 000110001100011... .

Cf. A282949.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs