A139415 Number of preferential arrangements (or hierarchical orderings) on the disconnected graphs on n unlabeled nodes.

0, 0, 2, 8, 40, 208, 1408, 12224, 157312, 3478528, 147761664, 12592434176, 2112188653568, 680441850810368, 415073848421801984, 476853486273606582272, 1030736815796444156755968, 4196432048875514376435007488, 32243698461915435195120257335296

Offset

0,3

Links

Table of n, a(n) for n=0..18.

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

Cf. A136722, A000719, A000088, A011782.

Sequence in context: A154626 A003305 A076625 * A119817 A025570 A227081

Adjacent sequences: A139412 A139413 A139414 * A139416 A139417 A139418

Keyword

nonn

Author

Thomas Wieder, Apr 20 2008

Extensions

Offset corrected and more terms from Alois P. Heinz, Apr 21 2012

Status

approved