A237447 Infinite square array: row 1 is the positive integers 1, 2, 3, ..., and on any subsequent row n, n is moved to the front: n, 1, ..., n-1, n+1, n+2, ...

1, 2, 2, 3, 1, 3, 4, 3, 1, 4, 5, 4, 2, 1, 5, 6, 5, 4, 2, 1, 6, 7, 6, 5, 3, 2, 1, 7, 8, 7, 6, 5, 3, 2, 1, 8, 9, 8, 7, 6, 4, 3, 2, 1, 9, 10, 9, 8, 7, 6, 4, 3, 2, 1, 10, 11, 10, 9, 8, 7, 5, 4, 3, 2, 1, 11, 12, 11, 10, 9, 8, 7, 5, 4, 3, 2, 1, 12, 13, 12, 11, 10, 9, 8, 6, 5, 4, 3, 2, 1, 13, 14, 13, 12, 11, 10, 9, 8, 6, 5, 4, 3, 2, 1, 14, 15, 14, 13, 12, 11, 10, 9, 7, 6, 5, 4, 3, 2, 1, 15

Offset

1,2

Comments

Row n is the lexicographically earliest permutation of positive integers beginning with n. This also holds for the reverse colexicographic order, thus A007489(n-1) gives the position of n-th row of this array (which is one-based) in zero-based arrays A195663 & A055089.

The finite n X n square matrices in sequence A237265 converge towards this infinite square array.

Rows can be constructed also simply as follows: The first row is A000027 (natural numbers, also known as positive integers). For the n-th row, n=2, ..., pick n out from the terms of A000027 and move it to the front. This will create a permutation with one cycle of length n, in cycle notation: (1 n n-1 n-2 ... 3 2), which is the inverse of (1 2 ... n-1 n).

There are A000110(n) ways to choose n permutations from the n first rows of this table so that their composition is identity (counting all the different composition orders). This comment is essentially the same as my May 01 2006 comment on A000110, please see there for more information. - Antti Karttunen, Feb 10 2014

Also, for n > 1, the whole symmetric group S_n can be generated with just two rows, row 2, which is transposition (1 2), and row n, which is the inverse of cycle (1 ... n). See Rotman, p. 24, Exercise 2.9 (iii).

References

Joseph J. Rotman, An Introduction to the Theory of Groups, 4th ed., Springer-Verlag, New York, 1995. First chapter, pp. 1-19 [For a general introduction], and from chapter 2, problem 2.9, p. 24.

Links

Antti Karttunen, Table of first 144 antidiagonals of array, flattened

Index entries for sequences that are permutations of the integers

Formula

When col > row, T(row,col) = col, when 1 < col <= row, T(row,col) = col-1, and when col=1, T(row,1) = row.

a(n) = A010054(n) * A002024(n) + (1-A010054(n)) * (A004736(n) - [A002260(n) >= A004736(n)]). [This gives the formula for this entry represented as a one-dimensional sequence. Here the expression inside Iverson brackets results 1 only when the row index (A002260) is greater than or equal to the column index (A004736), otherwise zero. A010054 is the characteristic function for the triangular numbers, A000217.]

T(row,col) = A237265((A000330(max(row,col)-1)+1) + (max(row,col)*(row-1)) + (col-1)). [Takes the infinite limit of n X n matrices of A237265.]

G.f. as array: g(x,y) = (1 - 4*x*y + 3*x*y^2 + x^2*y - x*y^3)*x*y/((1-x*y)*(1-x)^2*(1-y)^2). - Robert Israel, May 09 2017

Example

The top left 9 X 9 corner of this infinite square array:
  1 2 3 4 5 6 7 8 9
  2 1 3 4 5 6 7 8 9
  3 1 2 4 5 6 7 8 9
  4 1 2 3 5 6 7 8 9
  5 1 2 3 4 6 7 8 9
  6 1 2 3 4 5 7 8 9
  7 1 2 3 4 5 6 8 9
  8 1 2 3 4 5 6 7 9
  9 1 2 3 4 5 6 7 8
Note how this is also the 9th finite subsquare of the sequence A237265, which can be picked from its terms A237265(205) .. A237265(285), where 205 = 1+A000330(9-1), the starting offset for that 9th subsquare in A237265.

Maple

T:= proc(r, c) if c > r then c elif c=1 then r else c-1 fi end proc:
seq(seq(T(r, n-r), r=1..n-1), n=1..20); # Robert Israel, May 09 2017

Mathematica

Table[Function[n, If[k == 1, n, k - Boole[k <= n]]][m - k + 1], {m, 15}, {k, m, 1, -1}] // Flatten (* Michael De Vlieger, May 09 2017 *)

Prog

(Scheme)
(define (A237447 n) (+ (* (A010054 n) (A002024 n)) (* (- 1 (A010054 n)) (- (A004736 n) (if (>= (A002260 n) (A004736 n)) 1 0)))))
;; Another variant based on Cano's A237265.
(define (A237447 n) (let* ((row (A002260 n)) (col (A004736 n)) (sss (max row col)) (sof (+ 1 (A000330 (- sss 1))))) (A237265 (+ sof (* sss (- row 1)) (- col 1)))))
(PARI) A237447(n, k=0)=if(k, if(k>1, k-(k<=n), n), A237447(A002260(n), A004736(n))) \\ Yields the element [n, k] of the matrix, or the n-th term of the "linearized" sequence if no k is given. - M. F. Hasler, Mar 09 2014

Crossrefs

Transpose: A237448.

Topmost row and the leftmost column: A000027. Second column: A054977. Central diagonal: A028310 (note the different starting offsets).

Antidiagonal sums: A074148.

This array is the infinite limit of the n X n square matrices in A237265.

Cf. also A000330, A002260, A004736, A002024, A010054, A007489, A055089, A195663.

Sequence in context: A204143 A143182 A128715 * A368053 A338573 A113881

Adjacent sequences: A237444 A237445 A237446 * A237448 A237449 A237450

Keyword

nonn,easy,tabl

Author

Antti Karttunen, Feb 10 2014

Status

approved