A185259 -id:A185259 - cp's OEIS frontend

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.

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

Offset: 0

Anthony Labarre, Aug 19 2009

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

			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)

Axel Hultman, Toric permutations, Master's thesis, Department of Mathematics, KTH, Stockholm, Sweden, 1999.

Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened
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, arXiv:0811.0740 [math.CO], 2008.
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.

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

Cf. A185263 (rows reversed without 0's).

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

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

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

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

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

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

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

A185263 Triangle T(n,k) read by rows: coefficients (in compressed forms) in order of decreasing exponents of polynomials p_n(t) related to Hultman numbers.

Original entry on oeis.org

1, 1, 1, 1, 1, 5, 1, 15, 8, 1, 35, 84, 1, 70, 469, 180, 1, 126, 1869, 3044, 1, 210, 5985, 26060, 8064, 1, 330, 16401, 152900, 193248, 1, 495, 39963, 696905, 2286636, 604800, 1, 715, 88803, 2641925, 18128396, 19056960, 1, 1001, 183183, 8691683, 109425316, 292271616, 68428800, 1, 1365, 355355, 25537655, 539651112, 2961802480, 2699672832

Offset: 0

N. J. A. Sloane, Jan 21 2012

Row n contains floor(n/2) + 1 terms.

			Triangle begins:
  n\k| 0    1      2       3         4         5        6
-----+---------------------------------------------------
   0 | 1
   1 | 1
   2 | 1    1
   3 | 1    5
   4 | 1   15      8
   5 | 1   35     84
   6 | 1   70    469     180
   7 | 1  126   1869    3044
   8 | 1  210   5985   26060      8064
   9 | 1  330  16401  152900    193248
  10 | 1  495  39963  696905   2286636    604800
  11 | 1  715  88803 2641925  18128396  19056960
  12 | 1 1001 183183 8691683 109425316 292271616 68428800
  ...
Polynomials p_n(t):
  p_0 = t;
  p_1 = t^2;
  p_2 = t^3 +     t;
  p_3 = t^4 +   5*t^2;
  p_4 = t^5 +  15*t^3 +    8*t;
  p_5 = t^6 +  35*t^4 +   84*t^2;
  p_6 = t^7 +  70*t^5 +  469*t^3 +  180*t;
  p_7 = t^8 + 126*t^6 + 1869*t^4 + 3044*t^2;
  ...
A(x;t) = t + t^2*x/1! + (t^3 + t)*x^2/2! + (t^4 + 5*t^2)*x^3/3! + ...

Gheorghe Coserea, Rows n = 0..202, flattened
Nikita Alexeev and Peter Zograf, Hultman numbers, polygon gluings and matrix integrals, arXiv preprint arXiv:1111.3061 [math.PR], 2011.

Cf. A038720, A048994, A060593, A185259.

For uncompressed form of polynomial coefficients, in order of increasing powers, see A164652.

T[n_, k_] := Abs[StirlingS1[n+2, n-2k+1]]/Binomial[n+2, 2];
Table[T[n, k], {n, 0, 13}, {k, 0, n/2}] // Flatten (* Jean-François Alcover, Aug 12 2018 *)

seq(N) = {
  my(p=vector(N), t='t, v); p[1] = t^2; p[2] = t^3 + t;
  for (n=3, N,
    p[n] = ((2*n+1)*t*p[n-1] + (n-1)*(n^2-t^2)*p[n-2])/(n+2));
  v = vector(#p, n, vector(1+n\2, k, polcoeff(p[n], n+1-2*(k-1))));
  concat([[1]], v);
};
concat(seq(13))

N=14; x='x+O('x^(N+1));
concat(apply(p->select(a->a!=0, Vec(p)), Vec(serlaplace(((1-x)^(-t) - (1+x)^t)/x^2))))

T(n,k) = -stirling(n+2, n+1-2*k, 1)/binomial(n+2,2);
concat(1, concat(vector(13, n, vector(1+n\2, k, T(n, k-1)))))
\\ Gheorghe Coserea, Jan 29 2018

From Gheorghe Coserea, Jan 29 2018: (Start)
p(n) = Sum_{k=0..floor(n/2)} T(n,k)*t^(n+1-2*k) satisfies (n+2)*p(n) = (2*n+1)*t*p(n-1) + (n-1)*(n^2-t^2)*p(n-2), n >= 2. (th. 3, (iii))
E.g.f. A(x;t) = Sum_{n>=0} p(n)*x^n/n! = ((1-x)^(-t) - (1+x)^t)/x^2. (th. 3, (i))
T(n,k) = -Stirling1(n+2, n+1-2*k)/binomial(n+2,2), where Stirling1(n,k) is defined by A048994.
A000142(n) = p(n)(1), A052572(n) = p(n)(2) for n > 0, A060593(n) = T(2*n, n) for n > 0. (End)
n-th row polynomial R(n,x) satisfies x*R(n,x^2) = (1/2)*( P(n+1,x) - P(n+1,-x) )/ binomial(n+2,2), where P(k,x) = (1 + x)*(1 + 2*x) * ... *(1 + k*x). - Peter Bala, May 14 2023

More terms from Gheorghe Coserea, Jan 29 2018

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Sage

Formula

Extensions

A185263 Triangle T(n,k) read by rows: coefficients (in compressed forms) in order of decreasing exponents of polynomials p_n(t) related to Hultman numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

Extensions