login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 24 18:42 EDT 2017. Contains 292433 sequences.