A065410 Number of labeled, rooted, binary trees with internal nodes labeled from {1, ...,n} and leaves labeled from {0,1} such that 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.

2, 6, 74, 16430, 1079779602, 5829619944476392022, 203906812182221592008725937367751490906, 291045916380210542889328709144540300448800843154329245652913718353100604905854

Offset

0,1

Comments

A rooted tree is binary if each internal node has two children, a left child and a right child.

Links

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

Jan A. Bergstra, Alban Ponse, Daan J. C. Staudt, Propositional logic with short-circuit evaluation: a non-commutative and a commutative variant, arXiv:1810.02142 [cs.LO], 2018.

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} ]
RecurrenceTable[{a[0]==2, a[n]==n*a[n-1]^2+2}, a, {n, 7}] (* Harvey P. Dale, Dec 18 2015 *)

Crossrefs

Sequence in context: A218058 A207136 A304641 * A000721 A262279 A327052

Adjacent sequences: A065407 A065408 A065409 * 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, Nov 15 2001

Status

approved