A323842 Number of n-node Stanley graphs without isolated nodes.

1, 0, 1, 2, 11, 72, 677, 8686, 152191, 3632916, 118317913, 5271781946, 322549557299, 27208234437984, 3177021912874253, 515436469519284358, 116581257420399219175, 36866447823471507563436, 16339685138335030408029889, 10170100145132835334268145362

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/(1+z))^k / Prod_{i=1..k} (1 - (2^i-1)*z/(1+z)) - David Bevan, Nov 17 2023

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

Cf. A135922, A323841, A323843, A323502, A356111.

Sequence in context: A154887 A371518 A363389 * A049671 A074609 A299786

Adjacent sequences: A323839 A323840 A323841 * A323843 A323844 A323845

Keyword

nonn

Author

N. J. A. Sloane, Feb 04 2019

Extensions

More terms from Alois P. Heinz, Sep 24 2019

Status

approved