0,2

Let A be a finite set of size n. Then a(n) is the number of binary relations on A that are also functions. Note that a(n)=sum(binomial(n,k)*n^k, k=0..n)=(n+1)^n, where binomial(n,k) is the number of ways to select a domain D of size k from A and n^k is the number of functions from D to A. - Dennis P. Walsh (dwalsh(AT)mtsu.edu), Mar 13 2006

For example, a(2)=9 because there are exactly 9 binary relations on A={1, 2} that are functions, namely: {}, {(1,1)}, {(1,2)}, {(2,1)}, {(2,2)}, {(1,1),(2,1)}, {(1,1),(2,2)}, {(1,2),(2,1)} and {(1,2),(2,2)}. - Dennis P. Walsh (dwalsh(AT)mtsu.edu), Mar 13 2006

L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (14) with r = 5.

Index entries for sequences related to rooted trees

a(n)=sum(binomial(n,k)*n^k,k=0..n)=(n+1)^n - Dennis P. Walsh (dwalsh(AT)mtsu.edu), Mar 13 2006

Sequence in context: A128577 A052514 A036776 this_sequence A000169 A055860 A152917

Adjacent sequences: A036774 A036775 A036776 this_sequence A036778 A036779 A036780

nonn

N. J. A. Sloane (njas(AT)research.att.com).