OFFSET
1,3
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
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, Recursive and iterative algorithms for A237265, OEIS wiki.
FORMULA
EXAMPLE
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.
PROG
(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
(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:vec=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(s<n, r=s; s+=(p++)^2); q=divrem(n-r, p); if(!q[2], q[2]=p, q[1]++); A237265_mth_matrix(p, 1)[q[1], q[2]] \\ R. J. Cano, May 08 2017
CROSSREFS
KEYWORD
nonn,easy,tabf
AUTHOR
R. J. Cano, Feb 09 2014
EXTENSIONS
Name changed and more terms added by Antti Karttunen, Feb 10 2014
Further edits by M. F. Hasler, Mar 09 2014
STATUS
approved