- FindStat

Identifier

Mp00029: Dyck paths —to binary tree: left tree, up step, right tree, down step⟶ Binary trees
St000396: Binary trees ⟶ ℤ

Values

[1,0] => [.,.] => 1

[1,0,1,0] => [[.,.],.] => 1

[1,1,0,0] => [.,[.,.]] => 1

[1,0,1,0,1,0] => [[[.,.],.],.] => 1

[1,0,1,1,0,0] => [[.,.],[.,.]] => 2

[1,1,0,0,1,0] => [[.,[.,.]],.] => 1

[1,1,0,1,0,0] => [.,[[.,.],.]] => 1

[1,1,1,0,0,0] => [.,[.,[.,.]]] => 1

[1,0,1,0,1,0,1,0] => [[[[.,.],.],.],.] => 1

[1,0,1,0,1,1,0,0] => [[[.,.],.],[.,.]] => 2

[1,0,1,1,0,0,1,0] => [[[.,.],[.,.]],.] => 2

[1,0,1,1,0,1,0,0] => [[.,.],[[.,.],.]] => 2

[1,0,1,1,1,0,0,0] => [[.,.],[.,[.,.]]] => 2

[1,1,0,0,1,0,1,0] => [[[.,[.,.]],.],.] => 1

[1,1,0,0,1,1,0,0] => [[.,[.,.]],[.,.]] => 2

[1,1,0,1,0,0,1,0] => [[.,[[.,.],.]],.] => 1

[1,1,0,1,0,1,0,0] => [.,[[[.,.],.],.]] => 1

[1,1,0,1,1,0,0,0] => [.,[[.,.],[.,.]]] => 2

[1,1,1,0,0,0,1,0] => [[.,[.,[.,.]]],.] => 1

[1,1,1,0,0,1,0,0] => [.,[[.,[.,.]],.]] => 1

[1,1,1,0,1,0,0,0] => [.,[.,[[.,.],.]]] => 1

[1,1,1,1,0,0,0,0] => [.,[.,[.,[.,.]]]] => 1

[1,0,1,0,1,0,1,0,1,0] => [[[[[.,.],.],.],.],.] => 1

[1,0,1,0,1,0,1,1,0,0] => [[[[.,.],.],.],[.,.]] => 2

[1,0,1,0,1,1,0,0,1,0] => [[[[.,.],.],[.,.]],.] => 2

[1,0,1,0,1,1,0,1,0,0] => [[[.,.],.],[[.,.],.]] => 2

[1,0,1,0,1,1,1,0,0,0] => [[[.,.],.],[.,[.,.]]] => 2

[1,0,1,1,0,0,1,0,1,0] => [[[[.,.],[.,.]],.],.] => 2

[1,0,1,1,0,0,1,1,0,0] => [[[.,.],[.,.]],[.,.]] => 2

[1,0,1,1,0,1,0,0,1,0] => [[[.,.],[[.,.],.]],.] => 2

[1,0,1,1,0,1,0,1,0,0] => [[.,.],[[[.,.],.],.]] => 2

[1,0,1,1,0,1,1,0,0,0] => [[.,.],[[.,.],[.,.]]] => 2

[1,0,1,1,1,0,0,0,1,0] => [[[.,.],[.,[.,.]]],.] => 2

[1,0,1,1,1,0,0,1,0,0] => [[.,.],[[.,[.,.]],.]] => 2

[1,0,1,1,1,0,1,0,0,0] => [[.,.],[.,[[.,.],.]]] => 2

[1,0,1,1,1,1,0,0,0,0] => [[.,.],[.,[.,[.,.]]]] => 2

[1,1,0,0,1,0,1,0,1,0] => [[[[.,[.,.]],.],.],.] => 1

[1,1,0,0,1,0,1,1,0,0] => [[[.,[.,.]],.],[.,.]] => 2

[1,1,0,0,1,1,0,0,1,0] => [[[.,[.,.]],[.,.]],.] => 2

[1,1,0,0,1,1,0,1,0,0] => [[.,[.,.]],[[.,.],.]] => 2

[1,1,0,0,1,1,1,0,0,0] => [[.,[.,.]],[.,[.,.]]] => 2

[1,1,0,1,0,0,1,0,1,0] => [[[.,[[.,.],.]],.],.] => 1

[1,1,0,1,0,0,1,1,0,0] => [[.,[[.,.],.]],[.,.]] => 2

[1,1,0,1,0,1,0,0,1,0] => [[.,[[[.,.],.],.]],.] => 1

[1,1,0,1,0,1,0,1,0,0] => [.,[[[[.,.],.],.],.]] => 1

[1,1,0,1,0,1,1,0,0,0] => [.,[[[.,.],.],[.,.]]] => 2

[1,1,0,1,1,0,0,0,1,0] => [[.,[[.,.],[.,.]]],.] => 2

[1,1,0,1,1,0,0,1,0,0] => [.,[[[.,.],[.,.]],.]] => 2

[1,1,0,1,1,0,1,0,0,0] => [.,[[.,.],[[.,.],.]]] => 2

[1,1,0,1,1,1,0,0,0,0] => [.,[[.,.],[.,[.,.]]]] => 2

[1,1,1,0,0,0,1,0,1,0] => [[[.,[.,[.,.]]],.],.] => 1

[1,1,1,0,0,0,1,1,0,0] => [[.,[.,[.,.]]],[.,.]] => 2

[1,1,1,0,0,1,0,0,1,0] => [[.,[[.,[.,.]],.]],.] => 1

[1,1,1,0,0,1,0,1,0,0] => [.,[[[.,[.,.]],.],.]] => 1

[1,1,1,0,0,1,1,0,0,0] => [.,[[.,[.,.]],[.,.]]] => 2

[1,1,1,0,1,0,0,0,1,0] => [[.,[.,[[.,.],.]]],.] => 1

[1,1,1,0,1,0,0,1,0,0] => [.,[[.,[[.,.],.]],.]] => 1

[1,1,1,0,1,0,1,0,0,0] => [.,[.,[[[.,.],.],.]]] => 1

[1,1,1,0,1,1,0,0,0,0] => [.,[.,[[.,.],[.,.]]]] => 2

[1,1,1,1,0,0,0,0,1,0] => [[.,[.,[.,[.,.]]]],.] => 1

[1,1,1,1,0,0,0,1,0,0] => [.,[[.,[.,[.,.]]],.]] => 1

[1,1,1,1,0,0,1,0,0,0] => [.,[.,[[.,[.,.]],.]]] => 1

[1,1,1,1,0,1,0,0,0,0] => [.,[.,[.,[[.,.],.]]]] => 1

[1,1,1,1,1,0,0,0,0,0] => [.,[.,[.,[.,[.,.]]]]] => 1

[1,0,1,0,1,0,1,0,1,0,1,0] => [[[[[[.,.],.],.],.],.],.] => 1

[1,0,1,0,1,0,1,0,1,1,0,0] => [[[[[.,.],.],.],.],[.,.]] => 2

[1,0,1,0,1,0,1,1,0,0,1,0] => [[[[[.,.],.],.],[.,.]],.] => 2

[1,0,1,0,1,0,1,1,0,1,0,0] => [[[[.,.],.],.],[[.,.],.]] => 2

[1,0,1,0,1,0,1,1,1,0,0,0] => [[[[.,.],.],.],[.,[.,.]]] => 2

[1,0,1,0,1,1,0,0,1,0,1,0] => [[[[[.,.],.],[.,.]],.],.] => 2

[1,0,1,0,1,1,0,0,1,1,0,0] => [[[[.,.],.],[.,.]],[.,.]] => 2

[1,0,1,0,1,1,0,1,0,0,1,0] => [[[[.,.],.],[[.,.],.]],.] => 2

[1,0,1,0,1,1,0,1,0,1,0,0] => [[[.,.],.],[[[.,.],.],.]] => 2

[1,0,1,0,1,1,0,1,1,0,0,0] => [[[.,.],.],[[.,.],[.,.]]] => 2

[1,0,1,0,1,1,1,0,0,0,1,0] => [[[[.,.],.],[.,[.,.]]],.] => 2

[1,0,1,0,1,1,1,0,0,1,0,0] => [[[.,.],.],[[.,[.,.]],.]] => 2

[1,0,1,0,1,1,1,0,1,0,0,0] => [[[.,.],.],[.,[[.,.],.]]] => 2

[1,0,1,0,1,1,1,1,0,0,0,0] => [[[.,.],.],[.,[.,[.,.]]]] => 2

[1,0,1,1,0,0,1,0,1,0,1,0] => [[[[[.,.],[.,.]],.],.],.] => 2

[1,0,1,1,0,0,1,0,1,1,0,0] => [[[[.,.],[.,.]],.],[.,.]] => 2

[1,0,1,1,0,0,1,1,0,0,1,0] => [[[[.,.],[.,.]],[.,.]],.] => 2

[1,0,1,1,0,0,1,1,0,1,0,0] => [[[.,.],[.,.]],[[.,.],.]] => 2

[1,0,1,1,0,0,1,1,1,0,0,0] => [[[.,.],[.,.]],[.,[.,.]]] => 2

[1,0,1,1,0,1,0,0,1,0,1,0] => [[[[.,.],[[.,.],.]],.],.] => 2

[1,0,1,1,0,1,0,0,1,1,0,0] => [[[.,.],[[.,.],.]],[.,.]] => 2

[1,0,1,1,0,1,0,1,0,0,1,0] => [[[.,.],[[[.,.],.],.]],.] => 2

[1,0,1,1,0,1,0,1,0,1,0,0] => [[.,.],[[[[.,.],.],.],.]] => 2

[1,0,1,1,0,1,0,1,1,0,0,0] => [[.,.],[[[.,.],.],[.,.]]] => 2

[1,0,1,1,0,1,1,0,0,0,1,0] => [[[.,.],[[.,.],[.,.]]],.] => 2

[1,0,1,1,0,1,1,0,0,1,0,0] => [[.,.],[[[.,.],[.,.]],.]] => 2

[1,0,1,1,0,1,1,0,1,0,0,0] => [[.,.],[[.,.],[[.,.],.]]] => 2

[1,0,1,1,0,1,1,1,0,0,0,0] => [[.,.],[[.,.],[.,[.,.]]]] => 2

[1,0,1,1,1,0,0,0,1,0,1,0] => [[[[.,.],[.,[.,.]]],.],.] => 2

[1,0,1,1,1,0,0,0,1,1,0,0] => [[[.,.],[.,[.,.]]],[.,.]] => 2

[1,0,1,1,1,0,0,1,0,0,1,0] => [[[.,.],[[.,[.,.]],.]],.] => 2

[1,0,1,1,1,0,0,1,0,1,0,0] => [[.,.],[[[.,[.,.]],.],.]] => 2

[1,0,1,1,1,0,0,1,1,0,0,0] => [[.,.],[[.,[.,.]],[.,.]]] => 2

[1,0,1,1,1,0,1,0,0,0,1,0] => [[[.,.],[.,[[.,.],.]]],.] => 2

[1,0,1,1,1,0,1,0,0,1,0,0] => [[.,.],[[.,[[.,.],.]],.]] => 2

[1,0,1,1,1,0,1,0,1,0,0,0] => [[.,.],[.,[[[.,.],.],.]]] => 2

[1,0,1,1,1,0,1,1,0,0,0,0] => [[.,.],[.,[[.,.],[.,.]]]] => 2

>>> Load all 1200 entries. <<<

search for individual values

searching the database for the individual values of this statistic

/ search for generating function

searching the database for statistics with the same generating function

click to show known generating functions

$F_{1} = q$

$F_{2} = 2\ q$

$F_{3} = 4\ q + q^{2}$

$F_{4} = 8\ q + 6\ q^{2}$

$F_{5} = 16\ q + 26\ q^{2}$

$F_{6} = 32\ q + 100\ q^{2}$

$F_{7} = 64\ q + 364\ q^{2} + q^{3}$

Description

The register function (or Horton-Strahler number) of a binary tree.
This is different from the dimension of the associated poset for the tree

$[[[.,.],[.,.]],[[.,.],[.,.]]]$ : its register function is 3, whereas the dimension of the associated poset is 2.

Map

to binary tree: left tree, up step, right tree, down step

Description

Return the binary tree corresponding to the Dyck path under the transformation left tree - up step - right tree - down step.
A Dyck path

$D$ of semilength

$n$ with

$n > 1$ may be uniquely decomposed into

$L 1 R 0$ for Dyck paths

$L,R$ of respective semilengths

$n_1,n_2$ with

$n_1+n_2 = n-1$ .
This map sends

$D$ to the binary tree

$T$ consisting of a root node with a left child according to

$L$ and a right child according to

$R$ and then recursively proceeds.
The base case of the unique Dyck path of semilength

$1$ is sent to a single node.
This map may also be described as the unique map sending the Tamari orders on Dyck paths to the Tamari order on binary trees.