OFFSET
0,3
FORMULA
EXAMPLE
For n=3 we have A139415(3) = 8 because:
There A000719 (3)=2 disconnected graphs for n=3 unlabeled elements:
Three disconnected points
o o o
and
one point plus a two-point chain
o o-o.
The three disconnected points give us 011782(3) = 4 arrangements:
o o o,
-----
o
o o,
-----
o o
o,
-----
o
o
o.
The point plus the two-point chain provides us with 4 arrangements:
o o-o,
-----
o-o
o,
-----
o
o-o,
-----
o
|
o o.
This gives us 8 hierarchical orderings.
(See A136722 for the two connected graphs for n=3, these are the three-point chain and the triangle.)
PROG
(Python)
from functools import lru_cache
from itertools import combinations
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A139415(n):
if n == 0: return 0
@lru_cache(maxsize=None)
def b(n): return int(sum(Fraction(1<<sum(p[r]*p[s]*gcd(r, s) for r, s in combinations(p.keys(), 2))+sum((q>>1)*r+(q*r*(r-1)>>1) for q, r in p.items()), prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n)))
@lru_cache(maxsize=None)
def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1, n))
return b(n)-sum(mobius(n//d)*c(d) for d in divisors(n, generator=True))//n<<n-1 # Chai Wah Wu, Jul 03 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Thomas Wieder, Apr 20 2008
EXTENSIONS
Offset corrected and more terms from Alois P. Heinz, Apr 21 2012
STATUS
approved