login
A127911
Number of nonisomorphic partial functional graphs with n points which are not functional graphs.
0
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,3
COMMENTS
Partial functional graphs (digraphs) with at least one node of outdegree = 0.
REFERENCES
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.
LINKS
Eric Weisstein's World of Mathematics, Functional Graph.
FORMULA
a(n) = A126285(n) - A001372(n).
Euler transform of (A002861 + A000081) - Euler transform of A002861.
EXAMPLE
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.
KEYWORD
easy,nonn
AUTHOR
Jonathan Vos Post, Feb 06 2007
STATUS
approved