- FindStat

Identifier

Mp00096: Binary words —Foata bijection⟶ Binary words
Mp00135: Binary words —rotate front-to-back⟶ Binary words
Mp00316: Binary words —inverse Foata bijection⟶ Binary words

Images

0 => 0 => 0 => 0

1 => 1 => 1 => 1

00 => 00 => 00 => 00

01 => 01 => 10 => 10

10 => 10 => 01 => 01

11 => 11 => 11 => 11

000 => 000 => 000 => 000

001 => 001 => 010 => 100

010 => 100 => 001 => 001

011 => 011 => 110 => 110

100 => 010 => 100 => 010

101 => 101 => 011 => 011

110 => 110 => 101 => 101

111 => 111 => 111 => 111

0000 => 0000 => 0000 => 0000

0001 => 0001 => 0010 => 1000

0010 => 1000 => 0001 => 0001

0011 => 0011 => 0110 => 1100

0100 => 0100 => 1000 => 0010

0101 => 1001 => 0011 => 0011

0110 => 1010 => 0101 => 1001

0111 => 0111 => 1110 => 1110

1000 => 0010 => 0100 => 0100

1001 => 0101 => 1010 => 0110

1010 => 1100 => 1001 => 0101

1011 => 1011 => 0111 => 0111

1100 => 0110 => 1100 => 1010

1101 => 1101 => 1011 => 1011

1110 => 1110 => 1101 => 1101

1111 => 1111 => 1111 => 1111

00000 => 00000 => 00000 => 00000

00001 => 00001 => 00010 => 10000

00010 => 10000 => 00001 => 00001

00011 => 00011 => 00110 => 11000

00100 => 01000 => 10000 => 00010

00101 => 10001 => 00011 => 00011

00110 => 10010 => 00101 => 10001

00111 => 00111 => 01110 => 11100

01000 => 00100 => 01000 => 00100

01001 => 01001 => 10010 => 00110

01010 => 11000 => 10001 => 00101

01011 => 10011 => 00111 => 00111

01100 => 01010 => 10100 => 10010

01101 => 10101 => 01011 => 10011

01110 => 10110 => 01101 => 11001

01111 => 01111 => 11110 => 11110

10000 => 00010 => 00100 => 01000

10001 => 00101 => 01010 => 01100

10010 => 10100 => 01001 => 01001

10011 => 01011 => 10110 => 01110

10100 => 01100 => 11000 => 01010

10101 => 11001 => 10011 => 01011

10110 => 11010 => 10101 => 01101

10111 => 10111 => 01111 => 01111

11000 => 00110 => 01100 => 10100

11001 => 01101 => 11010 => 10110

11010 => 11100 => 11001 => 10101

11011 => 11011 => 10111 => 10111

11100 => 01110 => 11100 => 11010

11101 => 11101 => 11011 => 11011

11110 => 11110 => 11101 => 11101

11111 => 11111 => 11111 => 11111

000000 => 000000 => 000000 => 000000

000001 => 000001 => 000010 => 100000

000010 => 100000 => 000001 => 000001

000011 => 000011 => 000110 => 110000

000100 => 010000 => 100000 => 000010

000101 => 100001 => 000011 => 000011

000110 => 100010 => 000101 => 100001

000111 => 000111 => 001110 => 111000

001000 => 001000 => 010000 => 000100

001001 => 010001 => 100010 => 000110

001010 => 110000 => 100001 => 000101

001011 => 100011 => 000111 => 000111

001100 => 010010 => 100100 => 100010

001101 => 100101 => 001011 => 100011

001110 => 100110 => 001101 => 110001

001111 => 001111 => 011110 => 111100

010000 => 000100 => 001000 => 001000

010001 => 001001 => 010010 => 001100

010010 => 101000 => 010001 => 001001

010011 => 010011 => 100110 => 001110

010100 => 011000 => 110000 => 001010

010101 => 110001 => 100011 => 001011

010110 => 110010 => 100101 => 001101

010111 => 100111 => 001111 => 001111

011000 => 001010 => 010100 => 100100

011001 => 010101 => 101010 => 100110

011010 => 110100 => 101001 => 100101

011011 => 101011 => 010111 => 100111

011100 => 010110 => 101100 => 110010

011101 => 101101 => 011011 => 110011

011110 => 101110 => 011101 => 111001

011111 => 011111 => 111110 => 111110

100000 => 000010 => 000100 => 010000

100001 => 000101 => 001010 => 011000

100010 => 100100 => 001001 => 010001

100011 => 001011 => 010110 => 011100

100100 => 010100 => 101000 => 010010

100101 => 101001 => 010011 => 010011

100110 => 101010 => 010101 => 011001

>>> Load all 1047 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.

So $\phi(4154223) = 1254423$.

Map

rotate front-to-back

Description

The rotation of a binary word, first letter last.
This is the word obtained by moving the first letter to the end.

Map

inverse Foata bijection

Description

The inverse of Foata's bijection.
See Mp00096Foata bijection.