A139415 - OEIS

%I #14 Jul 04 2024 01:39:58

%S 0,0,2,8,40,208,1408,12224,157312,3478528,147761664,12592434176,

%T 2112188653568,680441850810368,415073848421801984,

%U 476853486273606582272,1030736815796444156755968,4196432048875514376435007488,32243698461915435195120257335296

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

%F 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 For n=3 we have A139415(3) = 8 because:

%e There A000719 (3)=2 disconnected graphs for n=3 unlabeled elements:

%e Three disconnected points

%e o o o

%e and

%e one point plus a two-point chain

%e o o-o.

%e The three disconnected points give us 011782(3) = 4 arrangements:

%e o o o,

%e -----

%e o

%e o o,

%e -----

%e o o

%e o,

%e -----

%e o

%e o

%e o.

%e The point plus the two-point chain provides us with 4 arrangements:

%e o o-o,

%e -----

%e o-o

%e o,

%e -----

%e o

%e o-o,

%e -----

%e o

%e |

%e o o.

%e This gives us 8 hierarchical orderings.

%e (See A136722 for the two connected graphs for n=3, these are the three-point chain and the triangle.)

%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 A139415(n):

%o     if n == 0: return 0

%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 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 Cf. A136722, A000719, A000088, A011782.

%K nonn

%O 0,3

%A _Thomas Wieder_, Apr 20 2008

%E Offset corrected and more terms from _Alois P. Heinz_, Apr 21 2012