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

 

Logo


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. 7
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. doi:10.1089/cmb.2016.0190 arXiv:1503.05285

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+1)/C(n+2,2) if n-k is even, 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).  [Edited by Peter Luschny, Mar 24 2015]

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

EXAMPLE

Triangle begins:

  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;

  ...

MAPLE

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

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

MATHEMATICA

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

Table[T[n, k], {n, 0, 11}, {k, 0, n}] // 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+1)/binomial(n+2, 2) if is_odd(n-k-1) else 0

for n in (0..7): print [A164652(n, k) for k in (0..n)] # 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. A000217, A060593, A128174, A130534, A185259, A189507.

Row sums give A000142.

Sequence in context: A083861 A097591 A318299 * A127557 A060524 A133843

Adjacent sequences:  A164649 A164650 A164651 * A164653 A164654 A164655

KEYWORD

nonn,tabl

AUTHOR

Anthony Labarre, Aug 19 2009

EXTENSIONS

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

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 June 20 11:38 EDT 2019. Contains 324234 sequences. (Running on oeis4.)