|
Search: id:A164652
|
|
|
| A164652 |
|
Triangle read by rows: Hultman numbers: a(n,k) is the number of permutations of n elements whose cycle graph (as defined by Bafna and Pevzner) contains k cycles. |
|
+0
1
|
|
| 0, 0, 1, 1, 0, 1, 0, 5, 0, 1, 8, 0, 15, 0, 1, 0, 84, 0, 35, 0, 1, 180, 0, 469, 0, 70, 0, 1, 0, 3044, 0, 1869, 0, 126, 0, 1, 8064, 0, 26060, 0, 5985, 0, 210, 0, 1, 0, 193248, 0, 152900, 0, 16401, 0, 330, 0, 1, 604800, 0, 2286636, 0, 696905, 0, 39963, 0, 495, 0, 1, 0, 19056960
(list; table; graph; listen)
|
|
|
OFFSET
|
0,8
|
|
|
COMMENT
|
a(n,k) is also the number of ways to express a given (n+1)-cycle as the product of an (n+1)-cycle and a permutation with k cycles (see Doignon and Labarre). a(n,n+1-2k) is the number of permutations of n elements whose block-interchange distance is k (see Christie, Doignon and Labarre).
|
|
REFERENCES
|
M. Bona and R. Flynn, The Average Number of Block Interchanges Needed to Sort A Permutation and a recent result of Stanley, Inf. Process. Lett., 109 (2009), 927-931
D. A. Christie, Sorting Permutations by Block-Interchanges. Inf. Process. Lett. 60 (1996), 165-169
J.-P. Doignon and A. Labarre, On Hultman Numbers, J. Integer Seq., 10 (2007), 13 pages.
|
|
LINKS
|
J.-P. Doignon and A. Labarre, On HultmanNumbers, J. Integer Seq., 10 (2007), 13 pages.
|
|
FORMULA
|
a(n,k)=S(n+2,k)/binom(n+2,2) if n-k is odd, and 0 otherwise. Here, S(n,k) is the Stirling number of the first kind, and binom(n,k) is the binomial coefficient (see Bona and Flynn).
|
|
CROSSREFS
|
Sequence in context: A060081 A083861 A097591 this_sequence A127557 A060524 A133843
Adjacent sequences: A164649 A164650 A164651 this_sequence A164653 A164654 A164655
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Anthony Labarre (alabarre(AT)ulb.ac.be), Aug 19 2009
|
|
|
Search completed in 0.005 seconds
|
