A237265 Irregular table: n X n matrices (n=1,2,3,...), read by rows filled with numbers 1..n, with k moved to the front in the k-th row.

1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 3, 3, 1, 2, 1, 2, 3, 4, 2, 1, 3, 4, 3, 1, 2, 4, 4, 1, 2, 3, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 3, 1, 2, 4, 5, 4, 1, 2, 3, 5, 5, 1, 2, 3, 4, 1, 2, 3, 4, 5, 6, 2, 1, 3, 4, 5, 6, 3, 1, 2, 4, 5, 6, 4, 1, 2, 3, 5, 6, 5, 1, 2, 3, 4, 6, 6, 1, 2, 3, 4, 5

Offset: 1

Author

R. J. Cano, Feb 09 2014

Keywords

• nonn
• easy
• tabf

Comments

Cases of enumeration in ascending order for the first m positive integers when one of them, j, is previously excluded (m=1,2,3,..., 1 <= j <= m).

Table of the k initial permutations, one per block, when all the k! permutations in lexicographic ascending order are split uniformly into k blocks. Such table read by rows for k=1,2,3,... .

These permutations might be considered the initial inputs for a parallel/distributed variant of the Narayana Pandita's algorithm. Such variant would deliver to each thread/core/host one or more of the mentioned inputs, then the remaining permutations can be obtained with (k-1)!-1 executions of the classic Narayana Pandita's algorithm for the next permutation in lexical order.

The terms of A237450 give the positions of rows of this table among the rows of A030298. The finite n X n square matrices converge towards the infinite square array A237447. Please see further comments there. - Antti Karttunen, Feb 10 2014

Alternative way to express this is that each row k=1..n of each n X n matrix contains the lexicographically earliest n-letter permutation beginning with number k, or equally, that each of the n X n square matrices contain in their n rows those n-letter permutations of the symmetric group S_n that correspond to the inverses of cycles (1), (1 2), (1 2 3), ..., (1 2 ... n). Please see the Example section. - Antti Karttunen, Feb 12 2014

Examples

			By excluding 2, the natural numbers between 1 and 4 are 1,3,4, then the second row of the corresponding matrix must be [2,1,3,4] and a(22)=4; that is, when reading by rows, a(22) must be placed at the 4th matrix since 22 is greater than the sum of elements there in the preceding matrices and it is smaller than the next of such sums: 14 = (1 + 2^2 + 3^2) <= (22) <= (1 + 2^2 + 3^2 + 4^2) = 30. Therefore 14 is subtracted from 22 leaving 8. This means that a(22) is the 8th element in the fourth matrix read by rows, so a(22) = A(4)[2,4] (see formula).
The irregular table starts consists of successively larger squares (beginning with a 1 X 1 square {1}), where each larger (n+1) X (n+1) square contains the previous n X n square in its upper left corner, with the first n rows followed by n+1, and the last row consisting of (n+1) followed by the first row of the previous n X n square (i.e., terms 1, 2, ..., n):
Permutation  In cycle notation.  Inverse in cycle notation
1;           ( )                 ( )    [Note: ( ) stands for identity]
1,2;         ( )                 ( )
2,1;         (1 2)               (1 2)
1,2,3;       ( )                 ( )
2,1,3;       (1 2)               (1 2)
3,1,2;       (1 3 2)             (1 2 3)
1,2,3,4;     ( )                 ( )
2,1,3,4;     (1 2)               (1 2)
3,1,2,4;     (1 3 2)             (1 2 3)
4,1,2,3;     (1 4 3 2)           (1 2 3 4)
1,2,3,4,5;   ( )                 ( )
2,1,3,4,5;   (1 2)               (1 2)
3,1,2,4,5;   (1 3 2)             (1 2 3)
4,1,2,3,5;   (1 4 3 2)           (1 2 3 4)
5,1,2,3,4;   (1 5 4 3 2)         (1 2 3 4 5)
...
The table starts with 1 since the definition must be read in the mathematical sense of its statement. If we have N elements and one of them must be excluded, there are no elements available to exclude when N=1.
		

References

• Donald Knuth, The Art of Computer Programming, Volume 4: "Generating All Tuples and Permutations" Fascicle 2, first printing. Addison-Wesley, 2005. ISBN 0-201-85393-0.

Links

• R. J. Cano, Table of n, a(n) for n = 1..10000
• R. J. Cano, Additional information.
• R. J. Cano, Illustration of the recursive algorithm defining this sequence.
• R. J. Cano, Recursive and iterative algorithms for A237265, OEIS wiki.

Crossrefs

Cf. A237447, A030298, A000330, A074279, A237450, A237451, A237452.

Programs

PARI

a(n,k=0)=if(k,if(k>1,k-(k<=n),n),a(A238013(n),A121997(n))) \\ M. F. Hasler, Feb 16 2014

PARI

A237265_mth_matrix(m,zeroless=1)={my(c=Vec(numtoperm(m,0))-!zeroless*vector(m,i,1),M=matrix(m,m,i,j,0));for(j=1,m,M[j,]=concat([j-!zeroless],concat(c[1..j-1],c[j+1..m])));M}
a(n)=my(p,q,r,s); while(sA237265_mth_matrix(p,1)[q[1],q[2]] \\ R. J. Cano, May 08 2017

Scheme

;; Implemented as a recurrence: (uses memoization macro definec from Antti Karttunen's IntSeq-library)
(definec (A237265 n) (cond ((zero? (A237452 (+ n (A074279 n)))) (+ (A237451 n) (if (zero? (A237451 n)) (A074279 n) 0))) ((zero? (A237451 (+ n 1))) (A074279 n)) (else (A237265 (+ 1 (A000330 (- (A074279 n) 2)) (* (- (A074279 n) 1) (A237452 n)) (A237451 n))))))
;; Version which uses the array A237447:
(define (A237265 n) (let ((col (A237451 n)) (row (A237452 n))) (A237447 (+ 1 (/ (+ (expt (+ col row) 2) col (* 3 row)) 2)))))
;; Antti Karttunen, Feb 08-10 2014

Formula

a(n) = A237447(1 + ((1/2) * ((col+row)^2 + col + 3*row)))[where col = A237451(n) and row = A237452(n)] = A237447bi(A237452(n),A237451(n)) [where A237447bi(row,col) is square array A237447 considered as a bivariate function]. - Antti Karttunen, Feb 10-12 2014

Extensions

Name changed and more terms added by Antti Karttunen, Feb 10 2014

Further edits by M. F. Hasler, Mar 09 2014