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
Keywords
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
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
Comments