BinaryTreeParentArrays

The binary trees with $n$ nodes, each as its in-order parent array.

BinaryTreeParentArrays(n)the binary trees with

n

nodes, as parent arrays

Typed signatures

Type	Package	Applies
`(integer<0..>) -> indexed_collection<binary_tree_parent_array>`	`combinatorics`	always

Domain: Combinatorial collections

Details

Number the nodes in order; entry $k$ is the number of the $k$ -th node's parent, $0$ at the root. A node numbered below its parent is its left child, above it its right.
Listed in BinaryTrees' order: BinaryTreeParentArray of the $k$ -th tree is the $k$ -th array.
A binary search tree's values are its in-order numbers, so BinarySearchTreeParentArray lands here.

Maps

Into and out of BinaryTreeParentArray, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.

BinaryTreeBinaryTreeParentArray → BinaryTreeinverseThe binary tree an in-order parent array describes: a node below its parent goes left, above it right.

BinarySearchTreeParentArrayPermutation → BinaryTreeParentArrayThe binary search tree of σ as its parent array: entry v is the value v is inserted under, 0 for the root.
BinaryTreeParentArrayBinaryTree → BinaryTreeParentArrayinverseA binary tree as its parent array: its nodes numbered in order, entry k the number of the k-th node's parent, 0 at the root.

Basic #

$C_4$

\mathrm{Count}(\mathrm{BinaryTreeParentArrays}(4))

Out

14

The right spine: node 1 is the root, 2 its right child, 3 below that

\mathrm{BinaryTreeParentArrays}(3)[1]

Out

{\operatorname{BinaryTreeParentArray}}([0, 1, 2])

Statistics #

A Dyck path statistic, two bijections away

\mathrm{Tally}(\mathrm{CombinatorialStat}(\mathrm{BinaryTreeParentArrays}(3), \text{Returns}))

Out

\operatorname{Tuple}(\bigl\lbrack3, 2, 1\bigr\rbrack,\bigl\lbrack1, 2, 2\bigr\rbrack)

About

Examples	3