A093057 -id:A093057 - cp's OEIS frontend

A093055 Triangle T(j,k) read by rows, where T(j,k) = number of non-singleton cycles in the in-situ transposition of a rectangular j X k matrix.

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

Offset: 1

Hugo Pfoertner, Mar 19 2004

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

			Transposition of a 3 X 7 matrix, written as one-dimensional 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 -> a(17) = T(7,3) = 5, length of longest cycle: A093056(17) = 4, number of fixed elements besides first and last: A093057(17) = 1.

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

Esco G. Cate, David W. Twigg, Algorithm 513: Analysis of In-Situ Transposition, ACM Transactions on Mathematical Software, Vol. 3, No. 1, March 1977, pp. 104-110.
E. G. Cate and D. W. Twigg, ACM algorithm 513, Revision of algorithm 380.
S. Laflin, M. A. Brebner, Algorithm 380; In-situ transposition of a rectangular matrix [F1], Communications of the ACM, Vol. 13, No. 5, May 1970, pp. 324-326.
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. 47-48.

Cf. A093056 length of longest cycle, A093057 number of singleton cycles, T(n,n) = A000217(n-1) exchanges in transposition of square matrix.

A093056 Triangle T(j,k) read by rows, where T(j,k) = length of the longest cycle in the in-situ transposition of a rectangular j X k matrix.

Original entry on oeis.org

2, 4, 2, 3, 5, 2, 6, 6, 9, 2, 10, 16, 11, 14, 2, 12, 4, 9, 16, 40, 2, 4, 11, 5, 4, 23, 20, 2, 8, 3, 6, 5, 26, 15, 35, 2, 18, 28, 6, 42, 58, 22, 13, 44, 2, 6, 8, 7, 18, 12, 6, 28, 21, 108, 2, 11, 12, 23, 29, 35, 41, 12, 53, 48, 65, 2, 20, 18, 4, 16, 10, 12, 17, 14, 21, 70, 60, 2, 18, 8, 10

Offset: 1

Hugo Pfoertner, Mar 22 2004

See A093055 for details of storage, another example, references and links.

			a(7)=T(2,5)=6 because the transposition of a 2 X 5 matrix into a 5 X 2 matrix
(1 2 3 4 5)(6 7 8 9 10) -> (1 6)(2 7)(3 8)(4 9)(5 10) consists of 2 cycles, the longer 2->3->5->9->8->6(->2) having length=6.

Cf. A093055 number of non-singleton cycles, A093057 number of singleton cycles.

cp's OEIS Frontend

A093055 Triangle T(j,k) read by rows, where T(j,k) = number of non-singleton cycles in the in-situ transposition of a rectangular j X k matrix.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs