The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors 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 for n >= 0 and 1 <= k <= n+1. 13
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).
Named after the Swedish mathematician Axel Hultman. - Amiram Eldar, Jun 11 2021
a(2*n,1) is the number of spanning trees in certain graphs with 2*n+1 vertices and n*(n+1) edges (see Ishikawa, Miezaki, and Tanaka). - Tsuyoshi Miezaki, Feb 08 2023
REFERENCES
Axel Hultman, Toric permutations, Master's thesis, Department of Mathematics, KTH, Stockholm, Sweden, 1999.
LINKS
Nikita Alexeev, Anna Pologova, and Max A. Alekseyev, Generalized Hultman Numbers and Cycle Structures of Breakpoint Graphs, Journal of Computational Biology, Vol. 24, No. 2 (2017), pp. 93-105; arXiv preprint, arXiv:1503.05285 [q-bio.GN], 2015-2017.
Nikita Alexeev and Peter Zograf, Hultman numbers, polygon gluings and matrix integrals, arXiv preprint arXiv:1111.3061 [math.PR], 2011.
Nikita Alexeev and Peter Zograf, Random matrix approach to the distribution of genomic distance, Journal of Computational Biology, Vol. 21, No. 8 (2014), pp. 622-631.
Miklos Bona and Ryan Flynn, The Average Number of Block Interchanges Needed to Sort A Permutation and a recent result of Stanley, Inf. Process. Lett., Vol. 109 (2009), pp. 927-931.
David A. Christie, Sorting Permutations by Block-Interchanges, Inf. Process. Lett., Vol. 60, No. 4 (1996), pp. 165-169.
Robert Cori and Gábor Hetyei, On reduced unicellular hypermonopoles, arXiv:2403.19569 [math.CO], 2024. See at p. 4.
Jean-Paul Doignon and Anthony Labarre, On Hultman Numbers, J. Integer Seq., Vol. 10 (2007), Article 07.6.2, 13 pages.
Simona Grusea and Anthony Labarre, The distribution of cycles in breakpoint graphs of signed permutations, arXiv:1104.3353 [cs.DM], 2011-2012.
Reina Ishikawa, Tsuyoshi Miezaki, and Yuuho Tanaka, A new interpretation of Hultman numbers.
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
n-th row polynomial R(n,x) = (x/2)*( P(n+1,x) + (-1)^n * P(n+1,-x) ) / binomial(n+2,2), where P(k,x) = (x + 1)*(x + 2)*...*(x + k). - Peter Bala, May 14 2023
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;
...
From Jon E. Schoenfield, May 20 2023: (Start)
As a right-aligned triangle:
1; n=0
0, 1; n=1
1, 0, 1; n=2
0, 5, 0, 1; n=3
8, 0, 15, 0, 1; n=4
0, 84, 0, 35, 0, 1; n=5
180, 0, 469, 0, 70, 0, 1; n=6
0, 3044, 0, 1869, 0, 126, 0, 1; n=7
8064, 0, 26060, 0, 5985, 0, 210, 0, 1; n=8
0, 193248, 0, 152900, 0, 16401, 0, 330, 0, 1; n=9
604800, 0, 2286636, 0, 696905, 0, 39963, 0, 495, 0, 1; n=10
...
(End)
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. A185263 (rows reversed without 0's).
Sequence in context: A083861 A097591 A318299 * A127557 A060524 A133843
KEYWORD
nonn,tabl
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 22 21:38 EDT 2024. Contains 372758 sequences. (Running on oeis4.)