

A093055


Triangle T(j,k) read by rows, where T(j,k) = number of nonsingleton cycles in the insitu transposition of a rectangular j X k matrix.


3



1, 1, 3, 2, 2, 6, 2, 2, 2, 10, 1, 1, 2, 2, 15, 1, 5, 4, 2, 1, 21, 4, 2, 6, 10, 2, 4, 28, 2, 8, 8, 8, 2, 4, 2, 36, 1, 1, 6, 2, 1, 3, 6, 2, 45, 5, 7, 6, 6, 5, 19, 4, 8, 1, 55, 2, 4, 2, 2, 2, 2, 10, 2, 4, 2, 66, 2, 2, 12, 8, 10, 14, 6, 8, 6, 2, 4, 78, 3, 5, 8, 4, 1, 1, 10, 6, 3, 7, 2, 4, 91, 1, 7, 2, 2, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

The first row and the first column are excluded, i.e. j>=k, k>1. a(1)=T(2,2), a(2)=T(3,2),a(3)=T(3,3), a(4)=T(4,2),a(5)=T(4,3),a(6)=T(4,4), a(7)=T(5,2),.......


REFERENCES

D. E. Knuth, The Art of Computer Programming, Vol. 1 (3rd ed.). Fundamental Algorithms. AddisonWesley 1997. Ch. 1.3.3 Exercise 12: Transposing a rectangular matrix. p. 182, answer p. 523.


LINKS

Table of n, a(n) for n=1..96.
Esco G. Cate, David W. Twigg, Algorithm 513: Analysis of InSitu Transposition, ACM Transactions on Mathematical Software, Vol. 3, No. 1, March 1977, pp. 104110.
E. G. Cate and D. W. Twigg, ACM algorithm 513, Revision of algorithm 380.
S. Laflin, M. A. Brebner, Algorithm 380; Insitu transposition of a rectangular matrix [F1], Communications of the ACM, Vol. 13, No. 5, May 1970, pp. 324326.
Dave Rusin, Problem with permutation cycles, Posting in newsgroup sci.math Oct 11, 1997.
P. F. Windley, Transposing Matrices in a digital computer, The Computer Journal, Volume 2, Issue 1, April 1959, pp. 4748.


EXAMPLE

Transposition of a 3 X 7 matrix, written as onedimensional vector: first line: before transposition, 2nd line: after transposition
(1.2..3..4.5..6..7)(8..9.10.11.12.13.14)(15.16.17.18.19.20.21)
(1.8.15)(2.9.16)(3.10.17)(4.11.18)(5.12..19)(6.13.20)(7.14.21)
The following exchange cycles have to be performed: 2>4>10>8, 3>7>19>15, 5>13>17>9, 6>16, 12>14>20>18;
11 remains fixed.
4 cycles of length 4 + 1 cycle of length 2 > A093055(17)=T(7,3)=5, length of longest cycle: A093056(17)=4, number of fixed elements besides first and last: A093057(17)=1.


CROSSREFS

Cf. A093056 length of longest cycle, A093057 number of singleton cycles, T(n, n)=A000217(n1) exchanges in transposition of square matrix.
Sequence in context: A021035 A259967 A007567 * A285733 A106335 A218698
Adjacent sequences: A093052 A093053 A093054 * A093056 A093057 A093058


KEYWORD

nonn,tabl


AUTHOR

Hugo Pfoertner, Mar 19 2004


STATUS

approved



