

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: AddisonWesley, pp. 164165, 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, A127909A127915.
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



