VOOZH about

URL: https://oeis.org/A139415

⇱ A139415 - OEIS

login
A139415
Number of preferential arrangements (or hierarchical orderings) on the disconnected graphs on n unlabeled nodes.
1
0, 0, 2, 8, 40, 208, 1408, 12224, 157312, 3478528, 147761664, 12592434176, 2112188653568, 680441850810368, 415073848421801984, 476853486273606582272, 1030736815796444156755968, 4196432048875514376435007488, 32243698461915435195120257335296
OFFSET
0,3
FORMULA
a(n) = A000719(n)*A011782(n). Also A000088(n) = A001349(n) + A000719(n) and therefore A000088(n)*A011782(n) = A001349(n)*A011782(n) + A000719(n)*A011782(n) = A136722(n) + a(n).
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