edit this map or download as text // json
Identifier
Mp00316: Binary words inverse Foata bijectionBinary 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=>1100 0111=>0111 1000=>0010 1001=>0101 1010=>0110 1011=>1011 1100=>1010 1101=>1101 1110=>1110 1111=>1111 00000=>00000 00001=>00001 00010=>10000 00011=>00011 00100=>01000 00101=>10001 00110=>11000 00111=>00111 01000=>00100 01001=>01001 01010=>01100 01011=>10011 01100=>10100 01101=>11001 01110=>11100 01111=>01111 10000=>00010 10001=>00101 10010=>00110 10011=>01011 10100=>10010 10101=>01101 10110=>01110 10111=>10111 11000=>01010 11001=>10101 11010=>10110 11011=>11011 11100=>11010 11101=>11101 11110=>11110 11111=>11111 000000=>000000 000001=>000001 000010=>100000 000011=>000011 000100=>010000 000101=>100001 000110=>110000 000111=>000111 001000=>001000 001001=>010001 001010=>011000 001011=>100011 001100=>101000 001101=>110001 001110=>111000 001111=>001111 010000=>000100 010001=>001001 010010=>001100 010011=>010011 010100=>100100 010101=>011001 010110=>011100 010111=>100111 011000=>010100 011001=>101001 011010=>101100 011011=>110011 011100=>110100 011101=>111001 011110=>111100 011111=>011111 100000=>000010 100001=>000101 100010=>000110 100011=>001011 100100=>100010 100101=>001101 100110=>001110 100111=>010111 101000=>010010 101001=>100101 101010=>100110 101011=>011011 101100=>110010 101101=>011101 101110=>011110 101111=>101111 110000=>001010 110001=>010101 110010=>010110 110011=>101011 110100=>011010 110101=>101101 110110=>101110 110111=>110111 111000=>101010 111001=>110101 111010=>110110 111011=>111011 111100=>111010 111101=>111101 111110=>111110 111111=>111111 0000000=>0000000 0000001=>0000001 0000010=>1000000 0000011=>0000011 0000100=>0100000 0000101=>1000001 0000110=>1100000 0000111=>0000111 0001000=>0010000 0001001=>0100001 0001010=>0110000 0001011=>1000011 0001100=>1010000 0001101=>1100001 0001110=>1110000 0001111=>0001111 0010000=>0001000 0010001=>0010001 0010010=>0011000 0010011=>0100011 0010100=>1001000 0010101=>0110001 0010110=>0111000 0010111=>1000111 0011000=>0101000 0011001=>1010001 0011010=>1011000 0011011=>1100011 0011100=>1101000 0011101=>1110001 0011110=>1111000 0011111=>0011111 0100000=>0000100 0100001=>0001001 0100010=>0001100 0100011=>0010011 0100100=>1000100 0100101=>0011001 0100110=>0011100 0100111=>0100111 0101000=>0100100 0101001=>1001001 0101010=>1001100 0101011=>0110011 0101100=>1100100 0101101=>0111001 0101110=>0111100 0101111=>1001111 0110000=>0010100 0110001=>0101001 0110010=>0101100 0110011=>1010011 0110100=>0110100 0110101=>1011001 0110110=>1011100 0110111=>1100111 0111000=>1010100 0111001=>1101001 0111010=>1101100 0111011=>1110011 0111100=>1110100 0111101=>1111001 0111110=>1111100 0111111=>0111111 1000000=>0000010 1000001=>0000101 1000010=>0000110 1000011=>0001011 1000100=>1000010 1000101=>0001101 1000110=>0001110 1000111=>0010111 1001000=>0100010 1001001=>1000101 1001010=>1000110 1001011=>0011011 1001100=>1100010 1001101=>0011101 1001110=>0011110 1001111=>0101111 1010000=>0010010 1010001=>0100101 1010010=>0100110 1010011=>1001011 1010100=>0110010 1010101=>1001101 1010110=>1001110 1010111=>0110111 1011000=>1010010 1011001=>1100101 1011010=>1100110 1011011=>0111011 1011100=>1110010 1011101=>0111101 1011110=>0111110 1011111=>1011111 1100000=>0001010 1100001=>0010101 1100010=>0010110 1100011=>0101011 1100100=>0011010 1100101=>0101101 1100110=>0101110 1100111=>1010111 1101000=>1001010 1101001=>0110101 1101010=>0110110 1101011=>1011011 1101100=>0111010 1101101=>1011101 1101110=>1011110 1101111=>1101111 1110000=>0101010 1110001=>1010101 1110010=>1010110 1110011=>1101011 1110100=>1011010 1110101=>1101101 1110110=>1101110 1110111=>1110111 1111000=>1101010 1111001=>1110101 1111010=>1110110 1111011=>1111011 1111100=>1111010 1111101=>1111101 1111110=>1111110 1111111=>1111111 00000000=>00000000 00000001=>00000001 00000010=>10000000 00000011=>00000011 00000100=>01000000 00000101=>10000001 00000110=>11000000 00000111=>00000111 00001000=>00100000 00001001=>01000001 00001010=>01100000 00001011=>10000011 00001100=>10100000 00001101=>11000001 00001110=>11100000 00001111=>00001111 00010000=>00010000 00010001=>00100001 00010010=>00110000 00010011=>01000011 00010100=>10010000 00010101=>01100001 00010110=>01110000 00010111=>10000111 00011000=>01010000 00011001=>10100001 00011010=>10110000 00011011=>11000011 00011100=>11010000 00011101=>11100001 00011110=>11110000 00011111=>00011111 00100000=>00001000 00100001=>00010001 00100010=>00011000 00100011=>00100011 00100100=>10001000 00100101=>00110001 00100110=>00111000 00100111=>01000111 00101000=>01001000 00101001=>10010001 00101010=>10011000 00101011=>01100011 00101100=>11001000 00101101=>01110001 00101110=>01111000 00101111=>10001111 00110000=>00101000 00110001=>01010001 00110010=>01011000 00110011=>10100011 00110100=>01101000 00110101=>10110001 00110110=>10111000 00110111=>11000111 00111000=>10101000 00111001=>11010001 00111010=>11011000 00111011=>11100011 00111100=>11101000 00111101=>11110001 00111110=>11111000 00111111=>00111111 01000000=>00000100 01000001=>00001001 01000010=>00001100 01000011=>00010011 01000100=>10000100 01000101=>00011001 01000110=>00011100 01000111=>00100111 01001000=>01000100 01001001=>10001001 01001010=>10001100 01001011=>00110011 01001100=>11000100 01001101=>00111001 01001110=>00111100 01001111=>01001111 01010000=>00100100 01010001=>01001001 01010010=>01001100 01010011=>10010011 01010100=>01100100 01010101=>10011001 01010110=>10011100 01010111=>01100111 01011000=>10100100 01011001=>11001001 01011010=>11001100 01011011=>01110011 01011100=>11100100 01011101=>01111001 01011110=>01111100 01011111=>10011111 01100000=>00010100 01100001=>00101001 01100010=>00101100 01100011=>01010011 01100100=>00110100 01100101=>01011001 01100110=>01011100 01100111=>10100111 01101000=>10010100 01101001=>01101001 01101010=>01101100 01101011=>10110011 01101100=>01110100 01101101=>10111001 01101110=>10111100 01101111=>11001111 01110000=>01010100 01110001=>10101001 01110010=>10101100 01110011=>11010011 01110100=>10110100 01110101=>11011001 01110110=>11011100 01110111=>11100111 01111000=>11010100 01111001=>11101001 01111010=>11101100 01111011=>11110011 01111100=>11110100 01111101=>11111001 01111110=>11111100 01111111=>01111111 10000000=>00000010 10000001=>00000101 10000010=>00000110 10000011=>00001011 10000100=>10000010 10000101=>00001101 10000110=>00001110 10000111=>00010111 10001000=>01000010 10001001=>10000101 10001010=>10000110 10001011=>00011011 10001100=>11000010 10001101=>00011101 10001110=>00011110 10001111=>00101111 10010000=>00100010 10010001=>01000101 10010010=>01000110 10010011=>10001011 10010100=>01100010 10010101=>10001101 10010110=>10001110 10010111=>00110111 10011000=>10100010 10011001=>11000101 10011010=>11000110 10011011=>00111011 10011100=>11100010 10011101=>00111101 10011110=>00111110 10011111=>01011111 10100000=>00010010 10100001=>00100101 10100010=>00100110 10100011=>01001011 10100100=>00110010 10100101=>01001101 10100110=>01001110 10100111=>10010111 10101000=>10010010 10101001=>01100101 10101010=>01100110 10101011=>10011011 10101100=>01110010 10101101=>10011101 10101110=>10011110 10101111=>01101111 10110000=>01010010 10110001=>10100101 10110010=>10100110 10110011=>11001011 10110100=>10110010 10110101=>11001101 10110110=>11001110 10110111=>01110111 10111000=>11010010 10111001=>11100101 10111010=>11100110 10111011=>01111011 10111100=>11110010 10111101=>01111101 10111110=>01111110 10111111=>10111111 11000000=>00001010 11000001=>00010101 11000010=>00010110 11000011=>00101011 11000100=>00011010 11000101=>00101101 11000110=>00101110 11000111=>01010111 11001000=>10001010 11001001=>00110101 11001010=>00110110 11001011=>01011011 11001100=>00111010 11001101=>01011101 11001110=>01011110 11001111=>10101111 11010000=>01001010 11010001=>10010101 11010010=>10010110 11010011=>01101011 11010100=>10011010 11010101=>01101101 11010110=>01101110 11010111=>10110111 11011000=>11001010 11011001=>01110101 11011010=>01110110 11011011=>10111011 11011100=>01111010 11011101=>10111101 11011110=>10111110 11011111=>11011111 11100000=>00101010 11100001=>01010101 11100010=>01010110 11100011=>10101011 11100100=>01011010 11100101=>10101101 11100110=>10101110 11100111=>11010111 11101000=>01101010 11101001=>10110101 11101010=>10110110 11101011=>11011011 11101100=>10111010 11101101=>11011101 11101110=>11011110 11101111=>11101111 11110000=>10101010 11110001=>11010101 11110010=>11010110 11110011=>11101011 11110100=>11011010 11110101=>11101101 11110110=>11101110 11110111=>11110111 11111000=>11101010 11111001=>11110101 11111010=>11110110 11111011=>11111011 11111100=>11111010 11111101=>11111101 11111110=>11111110 11111111=>11111111 000000000=>000000000 000000001=>000000001 000000010=>100000000 000000011=>000000011 000000100=>010000000 000000101=>100000001 000000110=>110000000 000000111=>000000111 000001000=>001000000 000001001=>010000001 000001010=>011000000 000001011=>100000011 000001100=>101000000 000001101=>110000001 000001110=>111000000 000001111=>000001111 000010000=>000100000 000010001=>001000001 000010010=>001100000 000010011=>010000011 000010100=>100100000 000010101=>011000001 000010110=>011100000 000010111=>100000111 000011000=>010100000 000011001=>101000001 000011010=>101100000 000011011=>110000011 000011100=>110100000 000011101=>111000001 000011110=>111100000 000011111=>000011111 000100000=>000010000 000100001=>000100001 000100010=>000110000 000100011=>001000011 000100100=>100010000 000100101=>001100001 000100110=>001110000 000100111=>010000111 000101000=>010010000 000101001=>100100001 000101010=>100110000 000101011=>011000011 000101100=>110010000 000101101=>011100001 000101110=>011110000 000101111=>100001111 000110000=>001010000 000110001=>010100001 000110010=>010110000 000110011=>101000011 000110100=>011010000 000110101=>101100001 000110110=>101110000 000110111=>110000111 000111000=>101010000 000111001=>110100001 000111010=>110110000 000111011=>111000011 000111100=>111010000 000111101=>111100001 000111110=>111110000 000111111=>000111111 001000000=>000001000 001000001=>000010001 001000010=>000011000 001000011=>000100011 001000100=>100001000 001000101=>000110001 001000110=>000111000 001000111=>001000111 001001000=>010001000 001001001=>100010001 001001010=>100011000 001001011=>001100011 001001100=>110001000 001001101=>001110001 001001110=>001111000 001001111=>010001111 001010000=>001001000 001010001=>010010001 001010010=>010011000 001010011=>100100011 001010100=>011001000 001010101=>100110001 001010110=>100111000 001010111=>011000111 001011000=>101001000 001011001=>110010001 001011010=>110011000 001011011=>011100011 001011100=>111001000 001011101=>011110001 001011110=>011111000 001011111=>100011111 001100000=>000101000 001100001=>001010001 001100010=>001011000 001100011=>010100011 001100100=>001101000 001100101=>010110001 001100110=>010111000 001100111=>101000111 001101000=>100101000 001101001=>011010001 001101010=>011011000 001101011=>101100011 001101100=>011101000 001101101=>101110001 001101110=>101111000 001101111=>110001111 001110000=>010101000 001110001=>101010001 001110010=>101011000 001110011=>110100011 001110100=>101101000 001110101=>110110001 001110110=>110111000 001110111=>111000111 001111000=>110101000 001111001=>111010001 001111010=>111011000 001111011=>111100011 001111100=>111101000 001111101=>111110001 001111110=>111111000 001111111=>001111111 010000000=>000000100 010000001=>000001001 010000010=>000001100 010000011=>000010011 010000100=>100000100 010000101=>000011001 010000110=>000011100 010000111=>000100111 010001000=>010000100 010001001=>100001001 010001010=>100001100 010001011=>000110011 010001100=>110000100 010001101=>000111001 010001110=>000111100 010001111=>001001111 010010000=>001000100 010010001=>010001001 010010010=>010001100 010010011=>100010011 010010100=>011000100 010010101=>100011001 010010110=>100011100 010010111=>001100111 010011000=>101000100 010011001=>110001001 010011010=>110001100 010011011=>001110011 010011100=>111000100 010011101=>001111001 010011110=>001111100 010011111=>010011111 010100000=>000100100 010100001=>001001001 010100010=>001001100 010100011=>010010011 010100100=>001100100 010100101=>010011001 010100110=>010011100 010100111=>100100111 010101000=>100100100 010101001=>011001001 010101010=>011001100 010101011=>100110011 010101100=>011100100 010101101=>100111001 010101110=>100111100 010101111=>011001111 010110000=>010100100 010110001=>101001001 010110010=>101001100 010110011=>110010011 010110100=>101100100 010110101=>110011001 010110110=>110011100 010110111=>011100111 010111000=>110100100 010111001=>111001001 010111010=>111001100 010111011=>011110011 010111100=>111100100 010111101=>011111001 010111110=>011111100 010111111=>100111111 011000000=>000010100 011000001=>000101001 011000010=>000101100 011000011=>001010011 011000100=>000110100 011000101=>001011001 011000110=>001011100 011000111=>010100111 011001000=>100010100 011001001=>001101001 011001010=>001101100 011001011=>010110011 011001100=>001110100 011001101=>010111001 011001110=>010111100 011001111=>101001111 011010000=>010010100 011010001=>100101001 011010010=>100101100 011010011=>011010011 011010100=>100110100 011010101=>011011001 011010110=>011011100 011010111=>101100111 011011000=>110010100 011011001=>011101001 011011010=>011101100 011011011=>101110011 011011100=>011110100 011011101=>101111001 011011110=>101111100 011011111=>110011111 011100000=>001010100 011100001=>010101001 011100010=>010101100 011100011=>101010011 011100100=>010110100 011100101=>101011001 011100110=>101011100 011100111=>110100111 011101000=>011010100 011101001=>101101001 011101010=>101101100 011101011=>110110011 011101100=>101110100 011101101=>110111001 011101110=>110111100 011101111=>111001111 011110000=>101010100 011110001=>110101001 011110010=>110101100 011110011=>111010011 011110100=>110110100 011110101=>111011001 011110110=>111011100 011110111=>111100111 011111000=>111010100 011111001=>111101001 011111010=>111101100 011111011=>111110011 011111100=>111110100 011111101=>111111001 011111110=>111111100 011111111=>011111111 100000000=>000000010 100000001=>000000101 100000010=>000000110 100000011=>000001011 100000100=>100000010 100000101=>000001101 100000110=>000001110 100000111=>000010111 100001000=>010000010 100001001=>100000101 100001010=>100000110 100001011=>000011011 100001100=>110000010 100001101=>000011101 100001110=>000011110 100001111=>000101111 100010000=>001000010 100010001=>010000101 100010010=>010000110 100010011=>100001011 100010100=>011000010 100010101=>100001101 100010110=>100001110 100010111=>000110111 100011000=>101000010 100011001=>110000101 100011010=>110000110 100011011=>000111011 100011100=>111000010 100011101=>000111101 100011110=>000111110 100011111=>001011111 100100000=>000100010 100100001=>001000101 100100010=>001000110 100100011=>010001011 100100100=>001100010 100100101=>010001101 100100110=>010001110 100100111=>100010111 100101000=>100100010 100101001=>011000101 100101010=>011000110 100101011=>100011011 100101100=>011100010 100101101=>100011101 100101110=>100011110 100101111=>001101111 100110000=>010100010 100110001=>101000101 100110010=>101000110 100110011=>110001011 100110100=>101100010 100110101=>110001101 100110110=>110001110 100110111=>001110111 100111000=>110100010 100111001=>111000101 100111010=>111000110 100111011=>001111011 100111100=>111100010 100111101=>001111101 100111110=>001111110 100111111=>010111111 101000000=>000010010 101000001=>000100101 101000010=>000100110 101000011=>001001011 101000100=>000110010 101000101=>001001101 101000110=>001001110 101000111=>010010111 101001000=>100010010 101001001=>001100101 101001010=>001100110 101001011=>010011011 101001100=>001110010 101001101=>010011101 101001110=>010011110 101001111=>100101111 101010000=>010010010 101010001=>100100101 101010010=>100100110 101010011=>011001011 101010100=>100110010 101010101=>011001101 101010110=>011001110 101010111=>100110111 101011000=>110010010 101011001=>011100101 101011010=>011100110 101011011=>100111011 101011100=>011110010 101011101=>100111101 101011110=>100111110 101011111=>011011111 101100000=>001010010 101100001=>010100101 101100010=>010100110 101100011=>101001011 101100100=>010110010 101100101=>101001101 101100110=>101001110 101100111=>110010111 101101000=>011010010 101101001=>101100101 101101010=>101100110 101101011=>110011011 101101100=>101110010 101101101=>110011101 101101110=>110011110 101101111=>011101111 101110000=>101010010 101110001=>110100101 101110010=>110100110 101110011=>111001011 101110100=>110110010 101110101=>111001101 101110110=>111001110 101110111=>011110111 101111000=>111010010 101111001=>111100101 101111010=>111100110 101111011=>011111011 101111100=>111110010 101111101=>011111101 101111110=>011111110 101111111=>101111111 110000000=>000001010 110000001=>000010101 110000010=>000010110 110000011=>000101011 110000100=>000011010 110000101=>000101101 110000110=>000101110 110000111=>001010111 110001000=>100001010 110001001=>000110101 110001010=>000110110 110001011=>001011011 110001100=>000111010 110001101=>001011101 110001110=>001011110 110001111=>010101111 110010000=>010001010 110010001=>100010101 110010010=>100010110 110010011=>001101011 110010100=>100011010 110010101=>001101101 110010110=>001101110 110010111=>010110111 110011000=>110001010 110011001=>001110101 110011010=>001110110 110011011=>010111011 110011100=>001111010 110011101=>010111101 110011110=>010111110 110011111=>101011111 110100000=>001001010 110100001=>010010101 110100010=>010010110 110100011=>100101011 110100100=>010011010 110100101=>100101101 110100110=>100101110 110100111=>011010111 110101000=>011001010 110101001=>100110101 110101010=>100110110 110101011=>011011011 110101100=>100111010 110101101=>011011101 110101110=>011011110 110101111=>101101111 110110000=>101001010 110110001=>110010101 110110010=>110010110 110110011=>011101011 110110100=>110011010 110110101=>011101101 110110110=>011101110 110110111=>101110111 110111000=>111001010 110111001=>011110101 110111010=>011110110 110111011=>101111011 110111100=>011111010 110111101=>101111101 110111110=>101111110 110111111=>110111111 111000000=>000101010 111000001=>001010101 111000010=>001010110 111000011=>010101011 111000100=>001011010 111000101=>010101101 111000110=>010101110 111000111=>101010111 111001000=>001101010 111001001=>010110101 111001010=>010110110 111001011=>101011011 111001100=>010111010 111001101=>101011101 111001110=>101011110 111001111=>110101111 111010000=>100101010 111010001=>011010101 111010010=>011010110 111010011=>101101011 111010100=>011011010 111010101=>101101101 111010110=>101101110 111010111=>110110111 111011000=>011101010 111011001=>101110101 111011010=>101110110 111011011=>110111011 111011100=>101111010 111011101=>110111101 111011110=>110111110 111011111=>111011111 111100000=>010101010 111100001=>101010101 111100010=>101010110 111100011=>110101011 111100100=>101011010 111100101=>110101101 111100110=>110101110 111100111=>111010111 111101000=>101101010 111101001=>110110101 111101010=>110110110 111101011=>111011011 111101100=>110111010 111101101=>111011101 111101110=>111011110 111101111=>111101111 111110000=>110101010 111110001=>111010101 111110010=>111010110 111110011=>111101011 111110100=>111011010 111110101=>111101101 111110110=>111101110 111110111=>111110111 111111000=>111101010 111111001=>111110101 111111010=>111110110 111111011=>111111011 111111100=>111111010 111111101=>111111101 111111110=>111111110 111111111=>111111111 1111111110=>1111111110 1101111110=>1011111110 1011111110=>0111111110 1010111110=>1001111110 1001111110=>0011111110 1001011110=>1000111110 1000111110=>0001111110 1000101110=>1000011110 1000011110=>0000111110 1000010110=>1000001110 1000001110=>0000011110 1000001010=>1000000110 1000000110=>0000001110 1000000100=>1000000010 1000000010=>0000000110 1000000000=>0000000010 0111111111=>0111111111 0111111101=>1111111001 0111111001=>1111101001 0111110001=>1110101001 0111100001=>1010101001 0111000001=>0010101001 0110000001=>0000101001 0100000001=>0000001001 0000000001=>0000000001 0111111011=>1111110011 0111110101=>1111011001 0111101001=>1101101001 0111010001=>0110101001 0110100001=>0100101001 0101000001=>0001001001 0010000001=>0000010001 10000000000=>00000000010 10000000010=>00000000110 10000000110=>00000001110 10000001110=>00000011110 10000011110=>00000111110 10000111110=>00001111110 10001111110=>00011111110 10011111110=>00111111110 10111111110=>01111111110 11111111110=>11111111110 01111111111=>01111111111 01111111101=>11111111001 01111111001=>11111101001 01111110001=>11110101001 01111100001=>11010101001 01111000001=>01010101001 01110000001=>00010101001 01100000001=>00000101001 01000000001=>00000001001 00000000001=>00000000001
click to show experimental identities (only identities of compositions of up to three maps are shown)
Description
The inverse of Foata's bijection.
See Mp00096Foata bijection.
References
[1] Foata, D., Schützenberger, M.-P. Major index and inversion number of permutations MathSciNet:0506852
Properties
bijective, graded
Sage code
def mapping(self):
    """
    sage: all(mapping(pi.foata_bijection()) == pi for n in range(9) for pi in Words([0,1], n))
    True
    """
    self = Words([0,1])(self)
    s = self.standard_permutation()
    ordered_alphabet = sorted(self.letters(),
                              key=self.parent().sortkey_letters)
    eval_dict = self.evaluation_dict()
    weight = [eval_dict[a] for a in ordered_alphabet]
    return Words([0,1])((s.foata_bijection_inverse()).destandardize(weight, ordered_alphabet=ordered_alphabet))
Weight
21
Created
Sep 12, 2023 at 11:34 by Martin Rubey
Updated
Sep 12, 2023 at 11:34 by Martin Rubey