A376544 a(n) is the number of singleton commuting ordered set partitions.

1, 1, 2, 8, 40, 242, 1784, 15374, 151008, 1669010, 20503768, 277049126, 4083693200, 65211041690, 1121435565384, 20662801363790, 406100030507200, 8480197575505442, 187500501495191480, 4376026842424336886, 107506303414618515696, 2773174380946415844266

Offset: 0

Author

Raul Penaguiao, Sep 27 2024

Keywords

• nonn

Comments

a(n) is also the dimension of the span of chromatic quasi-symmetric invariants of generalized permutahedra.

Examples

			a(2) = 2 because the ordered set partitions 1|2 and 2|1 are counted only once.
a(3) = 8, all ordered set partitions with length 3 (e.g. 1|2|3) are counted only once.
a(4) = 40 counts 1|34|2 separately to 2|34|1, but treats 1|2|34 as the same as 2|1|34 since only adjacent singletons can commute.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..435
• Vladimir Grujić, Counting faces of graphical zonotopes, Ars Math. Contemp., 13(1), 2017; arXiv preprint, arXiv:1604.06931 [math.CO], 2017.
• Raul Penaguiao, The kernel of chromatic quasisymmetric functions on graphs and hypergraphic polytopes, Journal of Combinatorial Theory, Series A, 175, 105258, 2020.

Crossrefs

Corresponds to a subset of elements counted in A000670.

Cf. A005840, A113059, A307389, A358623.

Programs

Maple

b:= proc(n, p) option remember; `if`(n=0, 1/p!, add(
      b(n-j, 0)*binomial(n, j)/p!, j=2..n)+b(n-1, p+1)*n)
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..21);  # Alois P. Heinz, Nov 19 2024

PARI

\\ here B(n,k) is A008299 or A358623.
B(n, k) = {sum(i=0, k, (-1)^i * binomial(n, i) * stirling(n-i, k-i, 2) ); }
a(n)={sum(k=0, n, binomial(n,k)*sum(j=0, k\2, B(k,j)*j!*(j+1)^(n-k)))} \\ Andrew Howroyd, Sep 27 2024

PARI

seq(n)=my(g=exp(x + O(x*x^n))); Vec(serlaplace(g/(1 - g*(g-x-1)))) \\ Andrew Howroyd, Sep 27 2024

Formula

Asymptotic growth: a(n) = n! * b^(-n) * c, where b is the unique positive root of exp(2*x) = 1 + e^x + x*e^x, and c is 0.722487... .

From Andrew Howroyd, Sep 27 2024: (Start)

a(n) = Sum_{k=0..n} Sum_{j=0..floor(k/2)} binomial(n,k)*A358623(k,j)*j!*(j+1)^(n-k).

E.g.f.: exp(x)/(1 - exp(x)*(exp(x)-x-1)). (End)

In the notation above, c = 1/(b*(2*exp(b) - b - 2)). - Vaclav Kotesovec, Nov 21 2024

Extensions

a(10) onwards from Andrew Howroyd, Sep 27 2024