|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Partial functional graphs (digraphs) with at least one node of outdegree = 0. A001372 Number of mappings (or mapping patterns) from n points to themselves; number of endofunctions. A126285 Number of partial mappings (or mapping patterns) from n points to themselves; number of partial endofunctions. If an endofunction is partial, then some points may be unmapped (or mapped to "undefined").
|
|
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
|
Table of n, a(n) for n=0..26.
Eric Weisstein's World of Mathematics, Functional Graph.
|
|
FORMULA
|
a(n) = A126285(n) - A001372(n). a(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.
|
|
CROSSREFS
|
Cf. A000081, A000273, A001372, A002861, A003027, A003085, A062738, A116950, A126285, A127909-A127915.
Sequence in context: A234270 A258911 A268093 * A116423 A077845 A291000
Adjacent sequences: A127908 A127909 A127910 * A127912 A127913 A127914
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Jonathan Vos Post, Feb 06 2007
|
|
STATUS
|
approved
|
|
|
|