login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 for n >= 0 and 1 <= k <= n+1. 8
1, 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, 0, 18128396, 0, 2641925, 0, 88803, 0, 715, 0, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,8

COMMENTS

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

LINKS

Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened

N. Alexeev, A. Pologova, M. A. Alekseyev, Generalized Hultman Numbers and Cycle Structures of Breakpoint Graphs, Journal of Computational Biology 24:2 (2017), 93-105; arXiv, arXiv:1503.05285 [q-bio.GN], 2015-2017.

N. Alexeev, P. Zograf, Hultman numbers, polygon gluings and matrix integrals, arXiv preprint arXiv:1111.3061 [math.PR], 2011.

N. Alexeev, P. Zograf, Random matrix approach to the distribution of genomic distance, Journal of Computational Biology 21:8 (2014), 622-631.

M. Bona and R. Flynn, The Average Number of Block Interchanges Needed to Sort A Permutation and a recent result of Stanley, arXiv:0811.0740 [math.CO], 2008.

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.

Simona Grusea and Anthony Labarre, The distribution of cycles in breakpoint graphs of signed permutations, arXiv:1104.3353 [cs.DM], 2011-2012.

FORMULA

T(n,k) = S1(n+2,k)/C(n+2,2) if n-k is odd, and 0 otherwise. Here S1(n,k) are the unsigned Stirling numbers of the first kind A132393 and C(n,k) is the binomial coefficient (see Bona and Flynn).

For n > 0: T(n,k) = A128174(n+1,k) * A130534(n+1,k-1) / A000217(n+1). - Reinhard Zumkeller, Aug 01 2014

EXAMPLE

Triangle begins:

n=0:  1;

n=1:  0, 1;

n=2:  1, 0, 1;

n=3:  0, 5, 0, 1;

n=4:  8, 0, 15, 0, 1;

n=5:  0, 84, 0, 35, 0, 1;

n=6:  180, 0, 469, 0, 70, 0, 1;

n=7:  0, 3044, 0, 1869, 0, 126, 0, 1;

n=8:  8064, 0, 26060, 0, 5985, 0, 210, 0, 1;

n=9:  0, 193248, 0, 152900, 0, 16401, 0, 330, 0, 1;

n=10: 604800, 0, 2286636, 0, 696905, 0, 39963, 0, 495, 0, 1;

  ...

MAPLE

A164652:= (n, k)-> `if`(n-k mod 2 = 1, -Stirling1(n+2, k)/binomial(n+2, 2), 0):

for n from 0 to 7 do seq(A164652(n, k), k=1..n+1) od; # Peter Luschny, Mar 22 2015

MATHEMATICA

T[n_, k_] := If[OddQ[n-k], Abs[StirlingS1[n+2, k]]/Binomial[n+2, 2], 0];

Table[T[n, k], {n, 0, 11}, {k, 1, n+1}] // Flatten (* Jean-Fran├žois Alcover, Aug 10 2018 *)

PROG

(Haskell)

a164652 n k = a164652_tabl !! n !! k

a164652_row n = a164652_tabl !! n

a164652_tabl = [0] : tail (zipWith (zipWith (*)) a128174_tabl $

   zipWith (map . flip div) (tail a000217_list) (map init $ tail a130534_tabl))

-- Reinhard Zumkeller, Aug 01 2014

(Sage)

def A164652(n, k):

    return stirling_number1(n+2, k)/binomial(n+2, 2) if is_odd(n-k) else 0

for n in (0..7): print([A164652(n, k) for k in (1..n+1)]) # Peter Luschny, Mar 22 2015

(PARI)

T(n, k)= my(s=(n-k)%2); (-1)^s*s*stirling(n+2, k, 1)/binomial(n+2, 2);

concat(vector(12, n, vector(n, k, T(n-1, k)))) \\ Gheorghe Coserea, Jan 23 2018

CROSSREFS

Cf. A000142 (row sums), A000217, A060593, A128174, A130534, A185259, A189507, A260695.

Sequence in context: A083861 A097591 A318299 * A127557 A060524 A133843

Adjacent sequences:  A164649 A164650 A164651 * A164653 A164654 A164655

KEYWORD

nonn,tabl,changed

AUTHOR

Anthony Labarre, Aug 19 2009

EXTENSIONS

T(0,1) set to 1 by Peter Luschny, Mar 24 2015

Edited to match values of k to the range 1 to n+1. - Max Alekseyev, Nov 20 2020

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 29 19:26 EST 2020. Contains 338769 sequences. (Running on oeis4.)