- FindStat

Identifier

St000518: Binary words ⟶ ℤ

Values

0 => 2

1 => 2

00 => 3

01 => 4

10 => 4

11 => 3

000 => 4

001 => 6

010 => 7

011 => 6

100 => 6

101 => 7

110 => 6

111 => 4

0000 => 5

0001 => 8

0010 => 10

0011 => 9

0100 => 10

0101 => 12

0110 => 11

0111 => 8

1000 => 8

1001 => 11

1010 => 12

1011 => 10

1100 => 9

1101 => 10

1110 => 8

1111 => 5

00000 => 6

00001 => 10

00010 => 13

00011 => 12

00100 => 14

00101 => 17

00110 => 16

00111 => 12

01000 => 13

01001 => 18

01010 => 20

01011 => 17

01100 => 16

01101 => 18

01110 => 15

01111 => 10

10000 => 10

10001 => 15

10010 => 18

10011 => 16

10100 => 17

10101 => 20

10110 => 18

10111 => 13

11000 => 12

11001 => 16

11010 => 17

11011 => 14

11100 => 12

11101 => 13

11110 => 10

11111 => 6

000000 => 7

000001 => 12

000010 => 16

000011 => 15

000100 => 18

000101 => 22

000110 => 21

000111 => 16

001000 => 18

001001 => 25

001010 => 28

001011 => 24

001100 => 23

001101 => 26

001110 => 22

001111 => 15

010000 => 16

010001 => 24

010010 => 29

010011 => 26

010100 => 28

010101 => 33

010110 => 30

010111 => 22

011000 => 21

011001 => 28

011010 => 30

011011 => 25

011100 => 22

011101 => 24

011110 => 19

011111 => 12

100000 => 12

100001 => 19

100010 => 24

100011 => 22

100100 => 25

100101 => 30

100110 => 28

>>> Load all 1200 entries. <<<

search for individual values

searching the database for the individual values of this statistic

/ search for generating function

searching the database for statistics with the same generating function

click to show known generating functions

$F_{1} = 2\ q^{2}$

$F_{2} = 2\ q^{3} + 2\ q^{4}$

$F_{3} = 2\ q^{4} + 4\ q^{6} + 2\ q^{7}$

$F_{4} = 2\ q^{5} + 4\ q^{8} + 2\ q^{9} + 4\ q^{10} + 2\ q^{11} + 2\ q^{12}$

$F_{5} = 2\ q^{6} + 4\ q^{10} + 4\ q^{12} + 4\ q^{13} + 2\ q^{14} + 2\ q^{15} + 4\ q^{16} + 4\ q^{17} + 4\ q^{18} + 2\ q^{20}$

$F_{6} = 2\ q^{7} + 4\ q^{12} + 4\ q^{15} + 6\ q^{16} + 4\ q^{18} + 2\ q^{19} + 4\ q^{21} + 8\ q^{22} + 2\ q^{23} + 6\ q^{24} + 4\ q^{25} + 4\ q^{26} + 6\ q^{28} + 2\ q^{29} + 4\ q^{30} + 2\ q^{33}$

$F_{7} = 2\ q^{8} + 4\ q^{14} + 4\ q^{18} + 4\ q^{19} + 4\ q^{20} + 4\ q^{22} + 4\ q^{23} + 4\ q^{26} + 4\ q^{27} + 4\ q^{28} + 4\ q^{29} + 8\ q^{30} + 4\ q^{31} + 6\ q^{32} + 4\ q^{33} + 4\ q^{34} + 4\ q^{35} + 8\ q^{36} + 6\ q^{38} + 2\ q^{39} + 12\ q^{40} + 4\ q^{42} + 4\ q^{43} + 2\ q^{44} + 4\ q^{45} + 4\ q^{46} + 4\ q^{48} + 4\ q^{49} + 2\ q^{54}$

$F_{8} = 2\ q^{9} + 4\ q^{16} + 4\ q^{21} + 4\ q^{22} + 4\ q^{24} + 2\ q^{25} + 4\ q^{26} + 2\ q^{27} + 4\ q^{28} + 4\ q^{31} + 4\ q^{32} + 4\ q^{34} + 8\ q^{36} + 8\ q^{37} + 4\ q^{38} + 6\ q^{39} + 2\ q^{40} + 6\ q^{41} + 12\ q^{42} + 8\ q^{44} + 8\ q^{46} + 6\ q^{47} + 8\ q^{48} + 8\ q^{50} + 4\ q^{51} + 10\ q^{52} + 8\ q^{54} + 6\ q^{55} + 8\ q^{56} + 2\ q^{57} + 8\ q^{58} + 4\ q^{59} + 8\ q^{60} + 4\ q^{61} + 4\ q^{62} + 8\ q^{63} + 6\ q^{64} + 4\ q^{65} + 4\ q^{66} + 4\ q^{67} + 4\ q^{68} + 2\ q^{69} + 8\ q^{70} + 2\ q^{72} + 2\ q^{73} + 4\ q^{74} + 4\ q^{75} + 4\ q^{78} + 2\ q^{79} + 4\ q^{80} + 2\ q^{88}$

$F_{9} = 2\ q^{10} + 4\ q^{18} + 4\ q^{24} + 4\ q^{25} + 4\ q^{28} + 8\ q^{30} + 2\ q^{31} + 4\ q^{33} + 2\ q^{34} + 4\ q^{36} + 4\ q^{37} + 4\ q^{40} + 4\ q^{42} + 4\ q^{43} + 4\ q^{44} + 8\ q^{45} + 8\ q^{46} + 4\ q^{48} + 8\ q^{49} + 6\ q^{50} + 4\ q^{51} + 12\ q^{52} + 4\ q^{53} + 4\ q^{54} + 2\ q^{55} + 6\ q^{56} + 4\ q^{57} + 12\ q^{58} + 12\ q^{60} + 8\ q^{61} + 4\ q^{62} + 4\ q^{63} + 10\ q^{64} + 12\ q^{66} + 4\ q^{68} + 4\ q^{69} + 16\ q^{70} + 2\ q^{71} + 16\ q^{72} + 4\ q^{73} + 4\ q^{74} + 8\ q^{75} + 6\ q^{76} + 8\ q^{77} + 12\ q^{78} + 4\ q^{79} + 8\ q^{81} + 16\ q^{82} + 8\ q^{83} + 12\ q^{84} + 4\ q^{85} + 8\ q^{86} + 4\ q^{87} + 12\ q^{88} + 6\ q^{90} + 8\ q^{91} + 8\ q^{92} + 4\ q^{93} + 6\ q^{94} + 12\ q^{96} + 8\ q^{97} + 4\ q^{98} + 8\ q^{99} + 8\ q^{100} + 4\ q^{102} + 4\ q^{103} + 8\ q^{104} + 4\ q^{105} + 4\ q^{106} + 4\ q^{107} + 8\ q^{108} + 8\ q^{110} + 6\ q^{111} + 4\ q^{114} + 4\ q^{115} + 4\ q^{116} + 6\ q^{118} + 4\ q^{120} + 4\ q^{122} + 4\ q^{127} + 4\ q^{128} + 4\ q^{130} + 2\ q^{143}$

Description

The number of distinct subsequences in a binary word.
In contrast to the subword complexity St000294The number of distinct factors of a binary word. this is the cardinality of the set of all subsequences of not necessarily consecutive letters.

References

[1] Flaxman, A., Harrow, A. W., Sorkin, G. B. Strings with maximally many distinct subsequences and substrings MathSciNet:2034422
[2] Elzinga, C., Rahmann, S., Wang, H. Algorithms for subsequence combinatorics MathSciNet:2473913

Code

def statistic(w):
    return len(Set(Subwords(w)))

Created

Jun 01, 2016 at 09:30 by Martin Rubey

Updated

Jun 01, 2016 at 09:30 by Martin Rubey