|
| |
|
|
A004140
|
|
Number of nonempty labeled simple graphs on nodes chosen from an n-set.
|
|
1
| |
|
|
0, 1, 4, 17, 112, 1449, 40068, 2350601, 286192512, 71213783665, 35883905263780, 36419649682706465, 74221659280476136240, 303193505953871645562969, 2480118046704094643352358500
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| We are given n labeled points, we choose k (1 <= k <= n) of them and construct a simple (but not necessarily connected) graph on these k nodes in 2^C(k,2) ways.
|
|
|
FORMULA
| Sum[ k=1, k=n ]{ binomial(n, k)*2^(k(k-1)/2) }.
|
|
|
EXAMPLE
| n=2: there are 4 graphs: {o}, {o}, {o o}, {o-o}
......................... 1 .. 2 .. 1 2 .. 1 2
|
|
|
PROG
| (PARI) a(n)=sum(k=1, n, binomial(n, k)*2^((k^2-k)/2))
|
|
|
CROSSREFS
| Cf. A006896.
Sequence in context: A127676 A122940 A077386 * A206353 A032115 A054927
Adjacent sequences: A004137 A004138 A004139 * A004141 A004142 A004143
|
|
|
KEYWORD
| nonn,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), C. L. Mallows (colinm(AT)research.avayalabs.com), James D. Klein (james.klein(AT)wallawalla.edu)
|
| |
|
|
