- FindStat

edit this map or download as text // json

Identifier

Mp00096: Binary words —Foata bijection⟶ Binary words

Images

0 => 0

1 => 1

00 => 00

01 => 01

10 => 10

11 => 11

000 => 000

001 => 001

010 => 100

011 => 011

100 => 010

101 => 101

110 => 110

111 => 111

0000 => 0000

0001 => 0001

0010 => 1000

0011 => 0011

0100 => 0100

0101 => 1001

0110 => 1010

0111 => 0111

1000 => 0010

1001 => 0101

1010 => 1100

1011 => 1011

1100 => 0110

1101 => 1101

1110 => 1110

1111 => 1111

00000 => 00000

00001 => 00001

00010 => 10000

00011 => 00011

00100 => 01000

00101 => 10001

00110 => 10010

00111 => 00111

01000 => 00100

01001 => 01001

01010 => 11000

01011 => 10011

01100 => 01010

01101 => 10101

01110 => 10110

01111 => 01111

10000 => 00010

10001 => 00101

10010 => 10100

10011 => 01011

10100 => 01100

10101 => 11001

10110 => 11010

10111 => 10111

11000 => 00110

11001 => 01101

11010 => 11100

11011 => 11011

11100 => 01110

11101 => 11101

11110 => 11110

11111 => 11111

000000 => 000000

000001 => 000001

000010 => 100000

000011 => 000011

000100 => 010000

000101 => 100001

000110 => 100010

000111 => 000111

001000 => 001000

001001 => 010001

001010 => 110000

001011 => 100011

001100 => 010010

001101 => 100101

001110 => 100110

001111 => 001111

010000 => 000100

010001 => 001001

010010 => 101000

010011 => 010011

010100 => 011000

010101 => 110001

010110 => 110010

010111 => 100111

011000 => 001010

011001 => 010101

011010 => 110100

011011 => 101011

011100 => 010110

011101 => 101101

011110 => 101110

011111 => 011111

100000 => 000010

100001 => 000101

100010 => 100100

100011 => 001011

100100 => 010100

100101 => 101001

>>> Load all 5998 entries. <<<

click to show experimental identities (only identities of compositions of up to three maps are shown)

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

References

[1] Foata, D., Schützenberger, M.-P. Major index and inversion number of permutations MathSciNet:0506852
[2] Foata bijection Mp00067

Properties

bijective, graded

Sage code

def mapping(w):
    return w.foata_bijection()

Weight

Created

Jan 29, 2020 at 13:26 by FindStatCrew

Updated

Jan 29, 2020 at 13:26 by Martin Rubey