|
%I #122 Apr 01 2024 08:27:16
%S 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,
%T 3044,0,1869,0,126,0,1,8064,0,26060,0,5985,0,210,0,1,0,193248,0,
%U 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
%N 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.
%C 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).
%C Named after the Swedish mathematician Axel Hultman. - _Amiram Eldar_, Jun 11 2021
%C 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
%D Axel Hultman, Toric permutations, Master's thesis, Department of Mathematics, KTH, Stockholm, Sweden, 1999.
%H Reinhard Zumkeller, <a href="/A164652/b164652.txt">Rows n = 0..125 of triangle, flattened</a>
%H Nikita Alexeev, Anna Pologova, and Max A. Alekseyev, <a href="https://doi.org/10.1089/cmb.2016.0190">Generalized Hultman Numbers and Cycle Structures of Breakpoint Graphs</a>, Journal of Computational Biology, Vol. 24, No. 2 (2017), pp. 93-105; <a href="http://arxiv.org/abs/1503.05285">arXiv preprint</a>, arXiv:1503.05285 [q-bio.GN], 2015-2017.
%H Nikita Alexeev and Peter Zograf, <a href="http://arxiv.org/abs/1111.3061">Hultman numbers, polygon gluings and matrix integrals</a>, arXiv preprint arXiv:1111.3061 [math.PR], 2011.
%H Nikita Alexeev and Peter Zograf, <a href="http://dx.doi.org/10.1089/cmb.2013.0066">Random matrix approach to the distribution of genomic distance</a>, Journal of Computational Biology, Vol. 21, No. 8 (2014), pp. 622-631.
%H Miklos Bona and Ryan Flynn, <a href="http://arxiv.org/abs/0811.0740">The Average Number of Block Interchanges Needed to Sort A Permutation and a recent result of Stanley</a>, arXiv:0811.0740 [math.CO], 2008.
%H Miklos Bona and Ryan Flynn, <a href="http://dx.doi.org/10.1016/j.ipl.2009.04.019">The Average Number of Block Interchanges Needed to Sort A Permutation and a recent result of Stanley</a>, Inf. Process. Lett., Vol. 109 (2009), pp. 927-931.
%H David A. Christie, <a href="http://dx.doi.org/10.1016/S0020-0190(96)00155-X">Sorting Permutations by Block-Interchanges</a>, Inf. Process. Lett., Vol. 60, No. 4 (1996), pp. 165-169.
%H Robert Cori and Gábor Hetyei, <a href="https://arxiv.org/abs/2403.19569">On reduced unicellular hypermonopoles</a>, arXiv:2403.19569 [math.CO], 2024. See at p. 4.
%H Jean-Paul Doignon and Anthony Labarre, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Doignon/doignon77.html">On Hultman Numbers</a>, J. Integer Seq., Vol. 10 (2007), Article 07.6.2, 13 pages.
%H Simona Grusea and Anthony Labarre, <a href="http://arxiv.org/abs/1104.3353">The distribution of cycles in breakpoint graphs of signed permutations</a>, arXiv:1104.3353 [cs.DM], 2011-2012.
%H Reina Ishikawa, Tsuyoshi Miezaki, and Yuuho Tanaka, <a href="/A164652/a164652_2.pdf">A new interpretation of Hultman numbers</a>.
%F 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).
%F For n > 0: T(n,k) = A128174(n+1,k) * A130534(n+1,k-1) / A000217(n+1). - _Reinhard Zumkeller_, Aug 01 2014
%F 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
%e Triangle begins:
%e n=0: 1;
%e n=1: 0, 1;
%e n=2: 1, 0, 1;
%e n=3: 0, 5, 0, 1;
%e n=4: 8, 0, 15, 0, 1;
%e n=5: 0, 84, 0, 35, 0, 1;
%e n=6: 180, 0, 469, 0, 70, 0, 1;
%e n=7: 0, 3044, 0, 1869, 0, 126, 0, 1;
%e n=8: 8064, 0, 26060, 0, 5985, 0, 210, 0, 1;
%e n=9: 0, 193248, 0, 152900, 0, 16401, 0, 330, 0, 1;
%e n=10: 604800, 0, 2286636, 0, 696905, 0, 39963, 0, 495, 0, 1;
%e ...
%e From _Jon E. Schoenfield_, May 20 2023: (Start)
%e As a right-aligned triangle:
%e 1; n=0
%e 0, 1; n=1
%e 1, 0, 1; n=2
%e 0, 5, 0, 1; n=3
%e 8, 0, 15, 0, 1; n=4
%e 0, 84, 0, 35, 0, 1; n=5
%e 180, 0, 469, 0, 70, 0, 1; n=6
%e 0, 3044, 0, 1869, 0, 126, 0, 1; n=7
%e 8064, 0, 26060, 0, 5985, 0, 210, 0, 1; n=8
%e 0, 193248, 0, 152900, 0, 16401, 0, 330, 0, 1; n=9
%e 604800, 0, 2286636, 0, 696905, 0, 39963, 0, 495, 0, 1; n=10
%e ...
%e (End)
%p A164652:= (n, k)-> `if`(n-k mod 2 = 1, -Stirling1(n+2, k)/binomial(n+2, 2), 0):
%p for n from 0 to 7 do seq(A164652(n,k),k=1..n+1) od; # _Peter Luschny_, Mar 22 2015
%t T[n_, k_] := If[OddQ[n-k], Abs[StirlingS1[n+2, k]]/Binomial[n+2, 2], 0];
%t Table[T[n, k], {n, 0, 11}, {k, 1, n+1}] // Flatten (* _Jean-François Alcover_, Aug 10 2018 *)
%o (Haskell)
%o a164652 n k = a164652_tabl !! n !! k
%o a164652_row n = a164652_tabl !! n
%o a164652_tabl = [0] : tail (zipWith (zipWith (*)) a128174_tabl $
%o zipWith (map . flip div) (tail a000217_list) (map init $ tail a130534_tabl))
%o -- _Reinhard Zumkeller_, Aug 01 2014
%o (Sage)
%o def A164652(n, k):
%o return stirling_number1(n+2,k)/binomial(n+2,2) if is_odd(n-k) else 0
%o for n in (0..7): print([A164652(n,k) for k in (1..n+1)]) # _Peter Luschny_, Mar 22 2015
%o (PARI)
%o T(n,k)= my(s=(n-k)%2); (-1)^s*s*stirling(n+2,k,1)/binomial(n+2,2);
%o concat(vector(12, n, vector(n, k, T(n-1,k)))) \\ _Gheorghe Coserea_, Jan 23 2018
%Y Cf. A000142 (row sums), A000217, A060593, A128174, A130534, A132393, A185259, A189507, A260695.
%Y Cf. A185263 (rows reversed without 0's).
%K nonn,tabl
%O 0,8
%A _Anthony Labarre_, Aug 19 2009
%E T(0,1) set to 1 by _Peter Luschny_, Mar 24 2015
%E Edited to match values of k to the range 1 to n+1. - _Max Alekseyev_, Nov 20 2020
|
