sequences that are permutations. Infinite permutation matrices.

[Antti Karttunen]

First a correction to previous mail, as I wrote:

> 4) From any function f(x) proved to have any particular integral value y
>    with only finite number of integer arguments x1,x2,...,xn
>    (e.g. number theoretic functions phi and sigma), construct

Obviously I meant tau (sum of divisors), instead of sigma (number of divisors),
as already Euclid proved that there infinitely many integers n with sigma(n) = 2.

>
>    a permutation of natural numbers by first listing (in some definite
>    order) all x for which f(x) = y1 (the global minimum for f),
>    then all x for which f(x) = y2 (the nearest possible value
>    greater than y1), then all x for which f(x) = y3, etc.
>    Note that y1,y2,y3 are not necessarily consecutive.
>    Example: invphi sequence. A032447

But here's another idea I just got at lunch:

Any permutation of the natural numbers corresponds to an infinite permutation
matrix (a matrix with only 0 and 1 entries), such that any row or column will
contain exactly one 1. In chess terms this means placing infinite pieces with at
least the power of rook on infinite board, so that no piece will threaten any other.
E.g., we could do this regularly by filling our infinite board from the upper left
corner,
moving from north-east to south-west by each successive antidiagonal,
and placing a piece to first possible square not yet threatened by any of the
already set pieces.

If we use ordinary rooks, then result is not very inspiring: an identity
matrix (corresponding to identity permutation, A000027), because
all the rooks (1's) can be placed on the main diagonal.

If we use the promoted rooks ("dragons") of Shoogi (Japanese Chess),
which can move also like the king, in addition to normal rook moves,
we will instead get the following placement:
(The first promoted rook is in the corner, the second promoted rook
one row down and two columns right to it, etc.)

1//////////
//2///////
////4////
/3//////
///5///
/////6
/////
////
///
//
/

and when we collect these rooks from above, we get the following "triangular" sequence
1, 0,0, 0,0,0, 0,0,1,0, 0,1,0,0,0, 0,0,0,0,0,0, 0,0,0,0,1,0,0, 0,0,0,1,0,0,0,0,
0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,   0,0,0,0,0,1,0,0,0,0,0, ...


and viewing this as 0/1-permutation matrix (0's not shown here):

   12345678
1  1
2    1
3      1
4   1
5     1
6       1
7
8

we get the following permutation of the natural numbers:
1,3,5,2,4,6,...

or its inverse:
1,4,2,5,3,6,...


depending on which way we read the matrix.

Doing this with the queens results the same first five terms, but the sixth queen
cannot be on the main diagonal (actually, 1 will be the only fixed point in the
corresponding permutation). Maybe of some interest would be also
a sequence which tells on which antidiagonal scans we could not place
any piece at all (here 2,3,6,9,10, ... and its complement, on which
antidiagonals we could place a piece: 1,4,5,7,8,11,...)

Instead of antidiagonal scanning we could walk the board "squarely", like:

125.
436
987

etc...
or use boustrophedon walking (in both cases), add additional constraints, etc.


Terveisin,

Antti Karttunen