- FindStat

Identifier

Mp00096: Binary words —Foata bijection⟶ Binary words
Mp00104: Binary words —reverse⟶ Binary words
Mp00261: Binary words —Burrows-Wheeler⟶ Binary words

Images

0 => 0 => 0 => 0

1 => 1 => 1 => 1

00 => 00 => 00 => 00

01 => 01 => 10 => 10

10 => 10 => 01 => 10

11 => 11 => 11 => 11

000 => 000 => 000 => 000

001 => 001 => 100 => 100

010 => 100 => 001 => 100

011 => 011 => 110 => 110

100 => 010 => 010 => 100

101 => 101 => 101 => 110

110 => 110 => 011 => 110

111 => 111 => 111 => 111

0000 => 0000 => 0000 => 0000

0001 => 0001 => 1000 => 1000

0010 => 1000 => 0001 => 1000

0011 => 0011 => 1100 => 1010

0100 => 0100 => 0010 => 1000

0101 => 1001 => 1001 => 1010

0110 => 1010 => 0101 => 1100

0111 => 0111 => 1110 => 1110

1000 => 0010 => 0100 => 1000

1001 => 0101 => 1010 => 1100

1010 => 1100 => 0011 => 1010

1011 => 1011 => 1101 => 1110

1100 => 0110 => 0110 => 1010

1101 => 1101 => 1011 => 1110

1110 => 1110 => 0111 => 1110

1111 => 1111 => 1111 => 1111

00000 => 00000 => 00000 => 00000

00001 => 00001 => 10000 => 10000

00010 => 10000 => 00001 => 10000

00011 => 00011 => 11000 => 10010

00100 => 01000 => 00010 => 10000

00101 => 10001 => 10001 => 10010

00110 => 10010 => 01001 => 11000

00111 => 00111 => 11100 => 10110

01000 => 00100 => 00100 => 10000

01001 => 01001 => 10010 => 11000

01010 => 11000 => 00011 => 10010

01011 => 10011 => 11001 => 10110

01100 => 01010 => 01010 => 11000

01101 => 10101 => 10101 => 11100

01110 => 10110 => 01101 => 11100

01111 => 01111 => 11110 => 11110

10000 => 00010 => 01000 => 10000

10001 => 00101 => 10100 => 11000

10010 => 10100 => 00101 => 11000

10011 => 01011 => 11010 => 11100

10100 => 01100 => 00110 => 10010

10101 => 11001 => 10011 => 10110

10110 => 11010 => 01011 => 11100

10111 => 10111 => 11101 => 11110

11000 => 00110 => 01100 => 10010

11001 => 01101 => 10110 => 11100

11010 => 11100 => 00111 => 10110

11011 => 11011 => 11011 => 11110

11100 => 01110 => 01110 => 10110

11101 => 11101 => 10111 => 11110

11110 => 11110 => 01111 => 11110

11111 => 11111 => 11111 => 11111

000000 => 000000 => 000000 => 000000

000001 => 000001 => 100000 => 100000

000010 => 100000 => 000001 => 100000

000011 => 000011 => 110000 => 100010

000100 => 010000 => 000010 => 100000

000101 => 100001 => 100001 => 100010

000110 => 100010 => 010001 => 101000

000111 => 000111 => 111000 => 100110

001000 => 001000 => 000100 => 100000

001001 => 010001 => 100010 => 101000

001010 => 110000 => 000011 => 100010

001011 => 100011 => 110001 => 100110

001100 => 010010 => 010010 => 110000

001101 => 100101 => 101001 => 110010

001110 => 100110 => 011001 => 101100

001111 => 001111 => 111100 => 101110

010000 => 000100 => 001000 => 100000

010001 => 001001 => 100100 => 110000

010010 => 101000 => 000101 => 101000

010011 => 010011 => 110010 => 101100

010100 => 011000 => 000110 => 100010

010101 => 110001 => 100011 => 100110

010110 => 110010 => 010011 => 110010

010111 => 100111 => 111001 => 101110

011000 => 001010 => 010100 => 101000

011001 => 010101 => 101010 => 111000

011010 => 110100 => 001011 => 101100

011011 => 101011 => 110101 => 111010

011100 => 010110 => 011010 => 110010

011101 => 101101 => 101101 => 111100

011110 => 101110 => 011101 => 111010

011111 => 011111 => 111110 => 111110

100000 => 000010 => 010000 => 100000

100001 => 000101 => 101000 => 101000

100010 => 100100 => 001001 => 110000

100011 => 001011 => 110100 => 110010

100100 => 010100 => 001010 => 101000

100101 => 101001 => 100101 => 101100

100110 => 101010 => 010101 => 111000

>>> Load all 1550 entries. <<<

Map

Foata bijection

Description

The Foata bijection

$\phi$ is a bijection on the set of words of given content (by a slight generalization of Section 2 in [1]).
Given a word

$w_1 w_2 ... w_n$ , compute the image inductively by starting with

$\phi(w_1) = w_1$ . At the

$i$ -th step, if

$\phi(w_1 w_2 ... w_i) = v_1 v_2 ... v_i$ , define

$\phi(w_1 w_2 ... w_i w_{i+1})$ by placing

$w_{i+1}$ on the end of the word

$v_1 v_2 ... v_i$ and breaking the word up into blocks as follows.

If $w_{i+1} \geq v_i$ , place a vertical line to the right of each $v_k$ for which $w_{i+1} \geq v_k$ .
If $w_{i+1} < v_i$ , place a vertical line to the right of each $v_k$ for which $w_{i+1} < v_k$ .

In either case, place a vertical line at the start of the word as well. Now, within each block between vertical lines, cyclically shift the entries one place to the right.
For instance, to compute

$\phi(4154223)$ , the sequence of words is

4,
|4|1 -- > 41,
|4|1|5 -- > 415,
|415|4 -- > 5414,
|5|4|14|2 -- > 54412,
|5441|2|2 -- > 154422,
|1|5442|2|3 -- > 1254423.

$\phi(4154223) = 1254423$ .

Map

reverse

Description

Return the reversal of a binary word.

Map

Burrows-Wheeler

Description

The Burrows-Wheeler transform of a binary word.
The Burrows-Wheeler transform of a finite word

$w$ is obtained from

$w$ by first listing the conjugates of

$w$ in lexicographic order and then concatenating the final letters of the conjugates in this order.