cp's OEIS Frontend

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

%I A139415 #14 Jul 04 2024 01:39:58
%S A139415 0,0,2,8,40,208,1408,12224,157312,3478528,147761664,12592434176,
%T A139415 2112188653568,680441850810368,415073848421801984,
%U A139415 476853486273606582272,1030736815796444156755968,4196432048875514376435007488,32243698461915435195120257335296
%N A139415 Number of preferential arrangements (or hierarchical orderings) on the disconnected graphs on n unlabeled nodes.
%F A139415 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).
%e A139415 For n=3 we have A139415(3) = 8 because:
%e A139415 There A000719 (3)=2 disconnected graphs for n=3 unlabeled elements:
%e A139415 Three disconnected points
%e A139415 o o o
%e A139415 and
%e A139415 one point plus a two-point chain
%e A139415 o o-o.
%e A139415 The three disconnected points give us 011782(3) = 4 arrangements:
%e A139415 o o o,
%e A139415 -----
%e A139415 o
%e A139415 o o,
%e A139415 -----
%e A139415 o o
%e A139415 o,
%e A139415 -----
%e A139415 o
%e A139415 o
%e A139415 o.
%e A139415 The point plus the two-point chain provides us with 4 arrangements:
%e A139415 o o-o,
%e A139415 -----
%e A139415 o-o
%e A139415 o,
%e A139415 -----
%e A139415 o
%e A139415 o-o,
%e A139415 -----
%e A139415 o
%e A139415 |
%e A139415 o o.
%e A139415 This gives us 8 hierarchical orderings.
%e A139415 (See A136722 for the two connected graphs for n=3, these are the three-point chain and the triangle.)
%o A139415 (Python)
%o A139415 from functools import lru_cache
%o A139415 from itertools import combinations
%o A139415 from fractions import Fraction
%o A139415 from math import prod, gcd, factorial
%o A139415 from sympy import mobius, divisors
%o A139415 from sympy.utilities.iterables import partitions
%o A139415 def A139415(n):
%o A139415     if n == 0: return 0
%o A139415     @lru_cache(maxsize=None)
%o A139415     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 A139415     @lru_cache(maxsize=None)
%o A139415     def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
%o A139415     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
%Y A139415 Cf. A136722, A000719, A000088, A011782.
%K A139415 nonn
%O A139415 0,3
%A A139415 _Thomas Wieder_, Apr 20 2008
%E A139415 Offset corrected and more terms from _Alois P. Heinz_, Apr 21 2012