A127909
Number of different digraphs on n unlabeled nodes which are not graphs.
Original entry on oeis.org
0, 0, 1, 12, 207, 9574, 1540788, 882032396, 1793359180502, 13027956824124884, 341260431952960575184, 32522909385055885092199576, 11366745430825400574268802831632, 14669085692712929869037045573284852976, 70315656615234999521385506526925748433982432
Offset: 0
a(2) = 1 because with two points a and b, either there are no edges connecting them, or there is one directed edge between them, or there is a bidirectional pair of edges between them; only the case with one directed edge is the unique 2-point digraph which is not a graph.
-
from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A127909(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))) # Chai Wah Wu, Jul 05 2024
A127911
Number of nonisomorphic partial functional graphs with n points which are not functional graphs.
Original entry on oeis.org
0, 1, 3, 9, 26, 74, 208, 586, 1647, 4646, 13135, 37247, 105896, 301880, 862498, 2469480, 7083690, 20353886, 58571805, 168780848, 486958481, 1406524978, 4066735979, 11769294050, 34090034328, 98820719105, 286672555274
Offset: 0
a(0) = 0 because the null graph is trivially both partial functional and functional.
a(1) = 1 because there are two partial functional graphs on one point: the point with, or without, a loop; the point with loop is the identity function, but without a loop the naked point is the unique merely partial functional case.
a(2) = 3 because there are A126285(2) enumerates the 6 partial functional graphs on 2 points, of which 3 are functional, 6 - 3 = 3.
a(3) = A126285(3) - A001372(3) = 16 - 7 = 9.
a(4) = 45 - 19 = 26.
a(5) = 121 - 47 = 74.
a(6) = 338 - 130 = 208.
a(7) = 929 - 343 = 586.
a(8) = 2598 - 951 = 1647.
a(9) = 7261 - 2615 = 4646.
a(10) = 20453 - 7318 = 13135.
- S. Skiena, "Functional Graphs." Section 4.5.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 164-165, 1990.
A127912
Number of nonisomorphic disconnected mappings (or mapping patterns) from n points to themselves; number of disconnected endofunctions.
Original entry on oeis.org
0, 1, 3, 10, 27, 79, 218, 622, 1753, 5007, 14274, 40954, 117548, 338485, 975721, 2817871, 8146510, 23581381, 68322672, 198138512, 575058726, 1670250623, 4854444560, 14117859226, 41081418963, 119606139728
Offset: 0
a(0) = 0, as the null digraph is formally neither connected nor disconnected.
a(1) = 0, as the unique endofunction on one point is the identity function on one value and is connected.
a(2) = 1, as there are 3 endofunctions on two points, two of which are "prime endofunctions" and one of which is the direct sum of two copies of the unique endofunction on one point, namely two points-with-loops, or the identity function on two values; 3 - 2 = 1.
a(3) = A001372(3) - A002861(3) = 7 - 4 = 3.
a(4) = A001372(4) - A002861(4) = 19 - 9 = 10.
a(5) = A001372(5) - A002861(5) = 47 - 20 = 27.
a(6) = 130 - 51 = 79.
a(7) = 343 - 125 = 218.
a(8) = 951 - 329 = 622.
a(9) = 2615 - 862 = 1753.
a(10) = 7318 - 2311 = 5007.
- Steven R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.6.
- R. A. Fisher, Contributions to Mathematical Statistics, Wiley, 1950, 41.399 and 41.401.
Showing 1-3 of 3 results.
Comments