login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 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

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

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.

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

LINKS

Table of n, a(n) for n=1..96.

E. G. Cate and D. W. Twigg, ACM algorithm 513. Revision of algorithm 380.

P. F. Windley, Transposing Matrices in a digital computer. The Computer Journal, Volume 2, Issue 1, April 1959, pp. 47-48 [subscription required]

Dave Rusin, Problem with permutation cycles. Posting in newsgroup sci.math Oct 11, 1997

EXAMPLE

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 -> 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(n-1) 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 12 12:43 EST 2018. Contains 317109 sequences. (Running on oeis4.)