# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/ Search: id:a139415 Showing 1-1 of 1 %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<>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<