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

1, 1, 2, 8, 48, 336, 3584, 54592, 1422976, 66836480, 5998884352, 1030861378560, 335994532814848, 206175878632321024, 237596569295651315712, 514414692643000188272640, 2096154545790162572944244736, 16113456361117058761983824232448, 234269143891823701379016369973493760

Offset

0,3

Links

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

Formula

a(n)=A001349(n)*A011782(n).

Example

There are A001349(3)=2 connected graphs for n=3 unlabeled elements:
The chain
o-o-o
and the triangle
. o
/..\
o - o.
There are a(3)=8 hierarchical orders on these two graphs.
The chain gives us 6 orderings:
o-o-o
o
|
o-o
. o
/..\
o . o
o . o
.\./
. o
o-o
|
o
o
|
o
|
o
The triangle gives us two orderings:
. o
/..\
o - o
o - o
\../
. o

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 A136722(n):
    if n == 0: return 1
    @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 sum(mobius(n//d)*c(d) for d in divisors(n, generator=True))//n<<n-1 # Chai Wah Wu, Jul 03 2024

Crossrefs

Cf. A001349, A011782, A136723, A034691, A075729.

Sequence in context: A007170 A355488 A171455 * A085615 A054726 A003576

Adjacent sequences: A136719 A136720 A136721 * A136723 A136724 A136725

Keyword

easy,nonn

Author

Thomas Wieder, Jan 19 2008

Extensions

More terms from Alois P. Heinz, Apr 21 2012

Status

approved