login
Number of n-node Stanley graphs without isolated nodes.
5

%I #66 Jul 25 2024 06:59:37

%S 1,0,1,2,11,72,677,8686,152191,3632916,118317913,5271781946,

%T 322549557299,27208234437984,3177021912874253,515436469519284358,

%U 116581257420399219175,36866447823471507563436,16339685138335030408029889,10170100145132835334268145362

%N Number of n-node Stanley graphs without isolated nodes.

%C For precise definition see Knuth (1997).

%C Also, the number of naturally labeled posets on [n] with height at most two and no isolated elements. - _David Bevan_, Nov 17 2023

%H Alois P. Heinz, <a href="/A323842/b323842.txt">Table of n, a(n) for n = 0..115</a>

%H David Bevan, Gi-Sang Cheon and Sergey Kitaev, <a href="https://arxiv.org/abs/2311.08023">On naturally labelled posets and permutations avoiding 12-34</a>, arXiv:2311.08023 [math.CO], 2023.

%H D. E. Knuth, <a href="/A323841/a323841.pdf">Letter to Daniel Ullman and others</a>, Apr 29 1997. [Annotated scanned copy, with permission]

%F a(n) = Sum_{j=0..n} (-1)^j * C(n,j) * A135922(n-j). - _Alois P. Heinz_, Sep 24 2019

%F 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

%F 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

%F 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

%p b:= proc(n) option remember; add(mul(

%p (2^(i+k)-1)/(2^i-1), i=1..n-k), k=0..n)

%p end:

%p g:= proc(n) option remember;

%p add(b(n-j)*binomial(n, j)*(-1)^j, j=0..n)

%p end:

%p a:= proc(n) option remember;

%p add(g(n-j)*binomial(n, j)*(-1)^j, j=0..n)

%p end:

%p seq(a(n), n=0..21); # _Alois P. Heinz_, Sep 24 2019

%t b[n_] := b[n] = Sum[Product[(2^(i+k) - 1)/(2^i - 1), {i, n-k}], {k, 0, n}];

%t g[n_] := g[n] = Sum[b[n-j] Binomial[n, j] (-1)^j, {j, 0, n}];

%t a[n_] := a[n] = Sum[g[n-j] Binomial[n, j] (-1)^j, {j, 0, n}];

%t a /@ Range[0, 21] (* _Jean-François Alcover_, May 24 2020, after _Alois P. Heinz_ *)

%o (Maxima)

%o 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)+

%o 2^k*P(n-1, k, (x+1)/2);

%o a(n):=sum(P(n-k, k, -1), k, 0, n);

%o makelist(a(n), n, 0, 10);

%o /* _Vladimir Kruchinin_, Mar 08 2020 */

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

%K nonn

%O 0,4

%A _N. J. A. Sloane_, Feb 04 2019

%E More terms from _Alois P. Heinz_, Sep 24 2019