|
|
A323842
|
|
Number of n-node Stanley graphs without isolated nodes.
|
|
5
|
|
|
1, 0, 1, 2, 11, 72, 677, 8686, 152191, 3632916, 118317913, 5271781946, 322549557299, 27208234437984, 3177021912874253, 515436469519284358, 116581257420399219175, 36866447823471507563436, 16339685138335030408029889, 10170100145132835334268145362
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
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:
|
|
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}];
|
|
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);
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|