|
|
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.
|
|
14
|
|
|
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
|
Jean-Paul Doignon and Anthony Labarre, On Hultman Numbers, J. Integer Seq., Vol. 10 (2007), Article 07.6.2, 13 pages.
|
|
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).
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;
...
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):
|
|
MATHEMATICA
|
T[n_, k_] := If[OddQ[n-k], Abs[StirlingS1[n+2, k]]/Binomial[n+2, 2], 0];
|
|
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))
(Sage)
return stirling_number1(n+2, k)/binomial(n+2, 2) if is_odd(n-k) else 0
(PARI)
T(n, k)= my(s=(n-k)%2); (-1)^s*s*stirling(n+2, k, 1)/binomial(n+2, 2);
|
|
CROSSREFS
|
Cf. A185263 (rows reversed without 0's).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Edited to match values of k to the range 1 to n+1. - Max Alekseyev, Nov 20 2020
|
|
STATUS
|
approved
|
|
|
|