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

%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