%I #10 Jul 04 2024 01:46:10
%S 1,1,2,8,48,336,3584,54592,1422976,66836480,5998884352,1030861378560,
%T 335994532814848,206175878632321024,237596569295651315712,
%U 514414692643000188272640,2096154545790162572944244736,16113456361117058761983824232448,234269143891823701379016369973493760
%N Number of preferential arrangements (or hierarchical orderings) on the connected graphs on n unlabeled nodes.
%F a(n)=A001349(n)*A011782(n).
%e There are A001349(3)=2 connected graphs for n=3 unlabeled elements:
%e The chain
%e o-o-o
%e and the triangle
%e . o
%e /..\
%e o - o.
%e There are a(3)=8 hierarchical orders on these two graphs.
%e The chain gives us 6 orderings:
%e o-o-o
%e o
%e |
%e o-o
%e . o
%e /..\
%e o . o
%e o . o
%e .\./
%e . o
%e o-o
%e |
%e o
%e o
%e |
%e o
%e |
%e o
%e The triangle gives us two orderings:
%e . o
%e /..\
%e o - o
%e o - o
%e \../
%e . o
%o (Python)
%o from functools import lru_cache
%o from itertools import combinations
%o from fractions import Fraction
%o from math import prod, gcd, factorial
%o from sympy import mobius, divisors
%o from sympy.utilities.iterables import partitions
%o def A136722(n):
%o if n == 0: return 1
%o @lru_cache(maxsize=None)
%o 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)))
%o @lru_cache(maxsize=None)
%o def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
%o return sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n<<n-1 # _Chai Wah Wu_, Jul 03 2024
%Y Cf. A001349, A011782, A136723, A034691, A075729.
%K easy,nonn
%O 0,3
%A _Thomas Wieder_, Jan 19 2008
%E More terms from _Alois P. Heinz_, Apr 21 2012