|
Search: id:A065410
|
|
|
| A065410 |
|
Number of labeled, rooted, binary trees with internal nodes labeled from {1, ...,n} and leaves labeled from {0,1} such for any path from the root to a leaf, the internal nodes receive distinct labels. In other words, the number of decision trees on n boolean variables. |
|
+0
1
|
|
| 2, 6, 74, 16430, 1079779602, 5829619944476392022, 203906812182221592008725937367751490906, 291045916380210542889328709144540300448800843154329245652913718353100604905854
(list; graph; listen)
|
|
|
OFFSET
|
0,1
|
|
|
COMMENT
|
A rooted tree is binary if each internal node has two children, a left child and a right child.
|
|
LINKS
|
H. Buhrman and R. de Wolf, Complexity Measures and Decision Tree Complexity: A Survey, Theoretical Computer Science, Vol. 288, no. 1 (2002), 21-43.
|
|
FORMULA
|
a(n) = n*(a(n-1))^2 + 2
|
|
MATHEMATICA
|
a[0] = 2; a[n_] := n*a[n - 1]^2 + 2; Table[ a[n], {n, 0, 8} ]
|
|
CROSSREFS
|
Sequence in context: A085865 A061296 A019993 this_sequence A000721 A136306 A076146
Adjacent sequences: A065407 A065408 A065409 this_sequence A065411 A065412 A065413
|
|
KEYWORD
|
easy,nice,nonn
|
|
AUTHOR
|
Clifford Smyth (csmyth(AT)ias.edu), Nov 14 2001
|
|
EXTENSIONS
|
One more term from Robert G. Wilson v (rgwv(AT)rgwv.com), Nov 15 2001
|
|
|
Search completed in 0.002 seconds
|
