Permutation of the nonnegative integers

This article page is a stub, please help by expanding it.

A permutation of the nonnegative integers is a sequence in which each of the nonnegative integers (the members of $\scriptstyle \{0\}\,\cup \,\mathbb {Z} ^{+}\,=\,\{0,\,1,\,2,\,3,\,4,\,5,\,6,\,7,\,...\}\,$) occurs exactly once, generally in a position other than its usual position in ascending order. The identity permutation of the nonnegative integers is given by A001477.

A001477 The nonnegative integers.

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, ...}

Cardinality of the set of sequences of permutations of nonnegative integers

The cardinality of the set $S$ of sequences of permutations of nonnegative integers is

${\rm {card}}(S)={\aleph _{0}}!={\aleph _{0}}^{\aleph _{0}}=c={\rm {card}}(\mathbb {R} )=2^{\aleph _{0}},$

where $\aleph _{0}$ is the cardinality of the set of natural numbers, $c={\rm {card}}(\mathbb {R} )$ is the cardinality of the continuum (the real number line), equal to the cardinality of the power set of the natural numbers ($2^{\aleph _{0}}$), the smallest (assuming the continuum hypothesis) uncountably infinite set. There are as many permutation sequences as there are real numbers, so we cannot list (enumerate) them.

Blockwise permutation of the nonnegative integers

A blockwise permutation of the nonnegative integers is a permutation of the nonnegative integers consisting of consecutive blocks of nonnegative integers, which are then blockwise permuted.

Blocks of size 2 and 3

The simplest blockwise permutations are obtained by acting on blocks of fixed size, always with the same permutation. Depending on the order of that permutation, the sequence is its own inverse (for transpositions), or there are several permutations obtained by taking powers of the sequence (in the sense of composition), until its inverse is reached.

A103889: Odd and even positive integers swapped,

{2, 1, 4, 3, 6, 5, 8, 7, 10, 9, 12, 11, 14, 13, 16, 15, 18, 17, 20, 19, 22, 21, 24, 23, 26, 25, 28, 27, 30, 29, 32, 31, 34, 33, 36, 35, 38, 37, 40, 39, 42, ...}

Here, the blocks are pairs of two consecutive integers (2n-1,2n), on which acts the only nontrivial permutation of these two, mapping it to (2n,2n-1).

A113655: Invert blocks of three in the sequence of natural numbers:

{3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10, 15, 14, 13, 18, 17, 16, 21, 20, 19, 24, 23, 22, 27, 26, 25, 30, 29, 28, 33, 32, 31, 36, 35, 34, 39, 38, 37, 42, ...}

Here, the title says it all... But there are several other permutations of groups of three:

A080782: a(1)=1, a(n)=a(n-1)-1 if n is already in the sequence, a(n)=a(n-1)+2 otherwise.

{1, 3, 2, 4, 6, 5, 7, 9, 8, 10, 12, 11, 13, 15, 14, 16, 18, 17, 19, 21, 20, 22, 24, 23, 25, 27, 26, 28, 30, 29, 31, 33, 32, 34, 36, 35, 37, 39, 38, 40, ...}

Here, it is the transposition τ_2,3 which is acting on groups of three, (3n-2,3n-1,3n) $\mapsto$ (3n-2,3n,3n-1).

The following sequence is defined on N={0,1,2,3,...} but its restriction to N*={1,2,3,...} yields another variant:

A064429: a(n) = floor(n / 3) * 3 + sign(n mod 3) * (3 - n mod 3).

{0, 2, 1, 3, 5, 4, 6, 8, 7, 9, 11, 10, 12, 14, 13, 15, 17, 16, 18, 20, 19, 21, 23, 22, 24, 26, 25, 27, 29, 28, 30, 32, 31, 33, 35, 34, 36, 38, 37, 39, 41, 40, 42, ...}

Finally, there are the two cyclic permutations acting on blocks of three,

A130508: a(1)=2. a(2)=3. a(3)=1. a(n+3) = 3 + a(n), for all positive integers n.

{2, 3, 1, 5, 6, 4, 8, 9, 7, 11, 12, 10, 14, 15, 13, 17, 18, 16, 20, 21, 19, 23, 24, 22, 26, 27, 25, 29, 30, 28, 32, 33, 31, 35, 36, 34, 38, 39, 37, 41, ...}

and its inverse,

A130509: a(1)=3. a(2)=1. a(3)=2. a(n+3) = 3 + a(n), for all positive integers n.

{3, 1, 2, 6, 4, 5, 9, 7, 8, 12, 10, 11, 15, 13, 14, 18, 16, 17, 21, 19, 20, 24, 22, 23, 27, 25, 26, 30, 28, 29, 33, 31, 32, 36, 34, 35, 39, 37, 38, 42, 40, ...}

A105027

A105027 Write numbers in binary under each other; to get the next block of $2^{k}$ $(k>=0)$ terms of the sequence, start at $2^{k}$, read diagonals in upward direction and convert to decimal.

{0, 1, 3, 2, 6, 5, 4, 7, 15, 10, 9, 8, 11, 14, 13, 12, 28, 23, 18, 17, 16, 19, 22, 21, 20, 31, 26, 25, 24, 27, 30, 29, 61, 44, 39, 34, 33, 32, 35, 38, 37, 36, 47, 42, 41, 40, ...}

This is a permutation of the nonnegative integers (and for $n>0$, a permutation of the positive integers). Furthermore, for each block of numbers with $k$ binary digits, we have a permutation of this block.

{0} ∪ {1} ∪ {3, 2} ∪ {6, 5, 4, 7} ∪ {15, 10, 9, 8, 11, 14, 13, 12} ∪ {28, 23, 18, 17, 16, 19, 22, 21, 20, 31, 26, 25, 24, 27, 30, 29} ∪ ...

........0
........1
......1 0    <- Starting here, the upward diagonals
......1 1    read 11, 10 giving the block 3, 2. 
....1 0 0    <- Starting here, the upward diagonals
....1 0 1    read 110, 101, 100, 111, 
....1 1 0    giving the block 6, 5, 4, 7.
....1 1 1
..1 0 0 0    
..1 0 0 1    
..1 0 1 0
..1 0 1 1
..1 1 0 0
..1 1 0 1
..1 1 1 0
..1 1 1 1

Permutation of the nonnegative integers (conjectured)

(...)

Permutation of the nonnegative integers (open problem)

(...)