|
| |
|
|
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.
|
|
7
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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)
;; Version which uses the array A237447:
(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
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
