|
Search: id:A004140
|
|
|
| A004140 |
|
Number of nonempty labeled simple graphs on nodes chosen from an n-set. |
|
+0
2
|
|
| 0, 1, 4, 17, 112, 1449, 40068, 2350601, 286192512, 71213783665, 35883905263780, 36419649682706465, 74221659280476136240, 303193505953871645562969, 2480118046704094643352358500
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
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
|
|
PROGRAM
|
(PARI) a(n)=sum(k=1, n, binomial(n, k)*2^((k^2-k)/2))
|
|
CROSSREFS
|
Cf. A006896.
Sequence in context: A127676 A122940 A077386 this_sequence A032115 A054927 A071138
Adjacent sequences: A004137 A004138 A004139 this_sequence 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 (kleiji(AT)wwc.edu)
|
|
|
Search completed in 0.002 seconds
|
