A136723
Number of preferential arrangements (or hierarchical orderings) on the connected graphs on n labeled nodes.
Original entry on oeis.org
1, 1, 3, 52, 2850, 393848, 125054832, 88260845008, 137304025714320, 469859118159233792, 3527181890877230433408, 57833314494643038031674112, 2060645597746315164145860149760, 158727775101107953869596632383822848, 26301662700662611321804753231934678909952
Offset: 0
There is A001187(2)=1 connected graph for n=2 labeled elements: The chain 1-2.
The chain gives us 3 hierarchical orderings:
1-2
1
|
2
2
|
1
A139415
Number of preferential arrangements (or hierarchical orderings) on the disconnected graphs on n unlabeled nodes.
Original entry on oeis.org
0, 0, 2, 8, 40, 208, 1408, 12224, 157312, 3478528, 147761664, 12592434176, 2112188653568, 680441850810368, 415073848421801984, 476853486273606582272, 1030736815796444156755968, 4196432048875514376435007488, 32243698461915435195120257335296
Offset: 0
For n=3 we have A139415(3) = 8 because:
There A000719 (3)=2 disconnected graphs for n=3 unlabeled elements:
Three disconnected points
o o o
and
one point plus a two-point chain
o o-o.
The three disconnected points give us 011782(3) = 4 arrangements:
o o o,
-----
o
o o,
-----
o o
o,
-----
o
o
o.
The point plus the two-point chain provides us with 4 arrangements:
o o-o,
-----
o-o
o,
-----
o
o-o,
-----
o
|
o o.
This gives us 8 hierarchical orderings.
(See A136722 for the two connected graphs for n=3, these are the three-point chain and the triangle.)
-
from functools import lru_cache
from itertools import combinations
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A139415(n):
if n == 0: return 0
@lru_cache(maxsize=None)
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)))
@lru_cache(maxsize=None)
def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
return b(n)-sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n<Chai Wah Wu, Jul 03 2024
Showing 1-2 of 2 results.
Comments