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

Author

Antti Karttunen, Feb 10 2014

Keywords

• nonn
• easy
• tabl

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

Examples

			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.
		

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

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.

Programs

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 *)

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

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)))))

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