OFFSET
0,4
COMMENTS
For precise definition see Knuth (1997).
Also, the number of naturally labeled posets on [n] with height at most two and no isolated elements. - David Bevan, Nov 17 2023
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..115
David Bevan, Gi-Sang Cheon and Sergey Kitaev, On naturally labelled posets and permutations avoiding 12-34, arXiv:2311.08023 [math.CO], 2023.
D. E. Knuth, Letter to Daniel Ullman and others, Apr 29 1997. [Annotated scanned copy, with permission]
FORMULA
a(n) = Sum_{j=0..n} (-1)^j * C(n,j) * A135922(n-j). - Alois P. Heinz, Sep 24 2019
a(n) = Sum_{k=0..n} P(n-k, k, -1), where P(n, k, x) = x*P(n, k-1, x) + 2^k*P(n-1, k, (x+1)/2). - Vladimir Kruchinin, Mar 09 2020
G.f.: g(1,0), where g(u,v) = 1 + x*((v-1)*g(u,v) + g(2*u,u+v)). - David Bevan, Jul 28 2022
G.f.: 1/(1+z) * Sum_{k>=0} (z^k / Prod_{i=2..k} (1 - (2^i-2)*z)). - David Bevan, Nov 17 2023; simplified on Jul 25 2024
MAPLE
b:= proc(n) option remember; add(mul(
(2^(i+k)-1)/(2^i-1), i=1..n-k), k=0..n)
end:
g:= proc(n) option remember;
add(b(n-j)*binomial(n, j)*(-1)^j, j=0..n)
end:
a:= proc(n) option remember;
add(g(n-j)*binomial(n, j)*(-1)^j, j=0..n)
end:
seq(a(n), n=0..21); # Alois P. Heinz, Sep 24 2019
MATHEMATICA
b[n_] := b[n] = Sum[Product[(2^(i+k) - 1)/(2^i - 1), {i, n-k}], {k, 0, n}];
g[n_] := g[n] = Sum[b[n-j] Binomial[n, j] (-1)^j, {j, 0, n}];
a[n_] := a[n] = Sum[g[n-j] Binomial[n, j] (-1)^j, {j, 0, n}];
a /@ Range[0, 21] (* Jean-François Alcover, May 24 2020, after Alois P. Heinz *)
PROG
(Maxima)
P(n, k, x):=if k<0 or n<0 then 0 else if k=0 then 1 else x*P(n, k-1, x)+
2^k*P(n-1, k, (x+1)/2);
a(n):=sum(P(n-k, k, -1), k, 0, n);
makelist(a(n), n, 0, 10);
/* Vladimir Kruchinin, Mar 08 2020 */
CROSSREFS
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Feb 04 2019
EXTENSIONS
More terms from Alois P. Heinz, Sep 24 2019
STATUS
approved