A275854 Number of labeled directed graphs on n nodes (allowing self loops) such that the out-degree of each node is at most 2.

1, 2, 16, 343, 14641, 1048576, 113379904, 17249876309, 3512479453921, 922190162669056, 303305489096114176, 122130132904968017083, 59091511031674153381441, 33825307664249166246182912, 22609039557544243501245546496, 17449402268886407318558803753801

Offset

0,2

Comments

As n goes to infinity, the probability that a node in such a graph has in-degree = 0 is 1/e^2. More generally, for 0<=k<=n, the probability that a node has in-degree = 0 in such a graph where the out-degree is restricted to be at most k is 1/e^k. Cf. A000169 where k=1 (partial functions) and A002416 where k=n.

Links

Table of n, a(n) for n=0..15.

Formula

a(n) = (Sum_{j=0..2} binomial(n,j))^n.

More generally, the number of labeled digraphs on n nodes with out-degree restricted to be at most k, 0<=k<=n, is given by: [Sum_{0<=j<=k} binomial(n,j)]^n.

From Ilya Gutkovskiy, Aug 11 2016: (Start)

a(n) = 2^(-n)*(n^2 + n + 2)^n.

a(n) = A000124(n)^n. (End)

Mathematica

Table[Sum[Binomial[n, j], {j, 0, 2}]^n, {n, 0, 15}]

Crossrefs

Cf. A000124, A000169, A002416.

Sequence in context: A009100 A009109 A268560 * A299907 A012610 A012721

Adjacent sequences: A275851 A275852 A275853 * A275855 A275856 A275857

Keyword

nonn

Author

Geoffrey Critzer, Aug 11 2016

Status

approved