A318974 Total number of valid hook configurations of permutations of [n].

1, 1, 2, 6, 22, 99, 520, 3126, 21164, 159226, 1318000, 11902268, 116444668, 1226878267, 13849980752, 166773534726, 2133706472788, 28904542964982, 413312731986464, 6221110588709700, 98321023508946088, 1627902016045648206, 28178332753660846304

Offset: 1

Author

Colin Defant, Sep 06 2018

Keywords

• easy
• nonn

Comments

a(n) = -k_{n+1}(-1), where k_m(lambda) is the cumulant of the free Poisson law with rate lambda. This is usually defined for lambda > 0, but there is a natural extension to lambda <= 0.

a(n) is the number of pairs (rho,r), where rho is a set partition of {0,...,n} and r is an acyclic orientation of the crossing graph of rho in which the block containing 0 is the only source (see the Josuat-Verges paper or the Defant-Engen-Miller paper for definitions).

Links

• Colin Defant, Michael Engen, and Jordan A. Miller, Stack-sorting, set partitions, and Lassalle's sequence, arXiv:1809.01340 [math.CO], 2018.
• Matthieu Josuat-Verges, Cumulants of the q-semicircular law, Tutte polynomials, and heaps, arXiv:1203.3157 [math.CO], 2012.

Crossrefs

Cf. A001263, A180874.

Programs

Mathematica

Table[(-(m + 1)!) SeriesCoefficient[Log[1 + Sum[Sum[(1/n) Binomial[n, k] Binomial[n, k - 1] (-1)^k (z^n/n!), {k, 1, n}], {n, 1, 100}]], {z, 0, m + 1}], {m, 1, 10}]

Formula

Let m_n(lambda) = Sum_{k=1..n} lambda^k * A001263(n,k). If we define k_n(lambda) by Sum_{n>=1} k_n(lambda) * z^n/n! = log(1 + Sum_{n>=1} m_n(lambda) * z^n/n!), then a(n) = -k_{n+1}(-1).

Define E(m,n) by E(n,n) = 1 and E(m,n) = Sum_{j=1..m} Sum_{i=1.. n-m-1} binomial(n-m-1,i-1) * F_j(i+j-1) * F_{m-j}(n-j-i) for 0 <= m < n, where F_m(n) = Sum_{j=m..n} E_j(n). Then a(n) = F_0(n).