cp's OEIS Frontend

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

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