Identifier
-
Mp00199:
Dyck paths
—prime Dyck path⟶
Dyck paths
Mp00034: Dyck paths —to binary tree: up step, left tree, down step, right tree⟶ Binary trees
St000204: Binary trees ⟶ ℤ
Values
[1,0] => [1,1,0,0] => [[.,.],.] => 0
[1,0,1,0] => [1,1,0,1,0,0] => [[.,[.,.]],.] => 1
[1,1,0,0] => [1,1,1,0,0,0] => [[[.,.],.],.] => 0
[1,0,1,0,1,0] => [1,1,0,1,0,1,0,0] => [[.,[.,[.,.]]],.] => 2
[1,0,1,1,0,0] => [1,1,0,1,1,0,0,0] => [[.,[[.,.],.]],.] => 2
[1,1,0,0,1,0] => [1,1,1,0,0,1,0,0] => [[[.,.],[.,.]],.] => 1
[1,1,0,1,0,0] => [1,1,1,0,1,0,0,0] => [[[.,[.,.]],.],.] => 1
[1,1,1,0,0,0] => [1,1,1,1,0,0,0,0] => [[[[.,.],.],.],.] => 0
[1,0,1,0,1,0,1,0] => [1,1,0,1,0,1,0,1,0,0] => [[.,[.,[.,[.,.]]]],.] => 3
[1,0,1,0,1,1,0,0] => [1,1,0,1,0,1,1,0,0,0] => [[.,[.,[[.,.],.]]],.] => 3
[1,0,1,1,0,0,1,0] => [1,1,0,1,1,0,0,1,0,0] => [[.,[[.,.],[.,.]]],.] => 3
[1,0,1,1,0,1,0,0] => [1,1,0,1,1,0,1,0,0,0] => [[.,[[.,[.,.]],.]],.] => 3
[1,0,1,1,1,0,0,0] => [1,1,0,1,1,1,0,0,0,0] => [[.,[[[.,.],.],.]],.] => 3
[1,1,0,0,1,0,1,0] => [1,1,1,0,0,1,0,1,0,0] => [[[.,.],[.,[.,.]]],.] => 2
[1,1,0,0,1,1,0,0] => [1,1,1,0,0,1,1,0,0,0] => [[[.,.],[[.,.],.]],.] => 2
[1,1,0,1,0,0,1,0] => [1,1,1,0,1,0,0,1,0,0] => [[[.,[.,.]],[.,.]],.] => 2
[1,1,0,1,0,1,0,0] => [1,1,1,0,1,0,1,0,0,0] => [[[.,[.,[.,.]]],.],.] => 2
[1,1,0,1,1,0,0,0] => [1,1,1,0,1,1,0,0,0,0] => [[[.,[[.,.],.]],.],.] => 2
[1,1,1,0,0,0,1,0] => [1,1,1,1,0,0,0,1,0,0] => [[[[.,.],.],[.,.]],.] => 1
[1,1,1,0,0,1,0,0] => [1,1,1,1,0,0,1,0,0,0] => [[[[.,.],[.,.]],.],.] => 1
[1,1,1,0,1,0,0,0] => [1,1,1,1,0,1,0,0,0,0] => [[[[.,[.,.]],.],.],.] => 1
[1,1,1,1,0,0,0,0] => [1,1,1,1,1,0,0,0,0,0] => [[[[[.,.],.],.],.],.] => 0
[1,0,1,0,1,0,1,0,1,0] => [1,1,0,1,0,1,0,1,0,1,0,0] => [[.,[.,[.,[.,[.,.]]]]],.] => 4
[1,0,1,0,1,0,1,1,0,0] => [1,1,0,1,0,1,0,1,1,0,0,0] => [[.,[.,[.,[[.,.],.]]]],.] => 4
[1,0,1,0,1,1,0,0,1,0] => [1,1,0,1,0,1,1,0,0,1,0,0] => [[.,[.,[[.,.],[.,.]]]],.] => 4
[1,0,1,0,1,1,0,1,0,0] => [1,1,0,1,0,1,1,0,1,0,0,0] => [[.,[.,[[.,[.,.]],.]]],.] => 4
[1,0,1,0,1,1,1,0,0,0] => [1,1,0,1,0,1,1,1,0,0,0,0] => [[.,[.,[[[.,.],.],.]]],.] => 4
[1,0,1,1,0,0,1,0,1,0] => [1,1,0,1,1,0,0,1,0,1,0,0] => [[.,[[.,.],[.,[.,.]]]],.] => 4
[1,0,1,1,0,0,1,1,0,0] => [1,1,0,1,1,0,0,1,1,0,0,0] => [[.,[[.,.],[[.,.],.]]],.] => 4
[1,0,1,1,0,1,0,0,1,0] => [1,1,0,1,1,0,1,0,0,1,0,0] => [[.,[[.,[.,.]],[.,.]]],.] => 4
[1,0,1,1,0,1,0,1,0,0] => [1,1,0,1,1,0,1,0,1,0,0,0] => [[.,[[.,[.,[.,.]]],.]],.] => 4
[1,0,1,1,0,1,1,0,0,0] => [1,1,0,1,1,0,1,1,0,0,0,0] => [[.,[[.,[[.,.],.]],.]],.] => 4
[1,0,1,1,1,0,0,0,1,0] => [1,1,0,1,1,1,0,0,0,1,0,0] => [[.,[[[.,.],.],[.,.]]],.] => 4
[1,0,1,1,1,0,0,1,0,0] => [1,1,0,1,1,1,0,0,1,0,0,0] => [[.,[[[.,.],[.,.]],.]],.] => 4
[1,0,1,1,1,0,1,0,0,0] => [1,1,0,1,1,1,0,1,0,0,0,0] => [[.,[[[.,[.,.]],.],.]],.] => 4
[1,0,1,1,1,1,0,0,0,0] => [1,1,0,1,1,1,1,0,0,0,0,0] => [[.,[[[[.,.],.],.],.]],.] => 4
[1,1,0,0,1,0,1,0,1,0] => [1,1,1,0,0,1,0,1,0,1,0,0] => [[[.,.],[.,[.,[.,.]]]],.] => 3
[1,1,0,0,1,0,1,1,0,0] => [1,1,1,0,0,1,0,1,1,0,0,0] => [[[.,.],[.,[[.,.],.]]],.] => 3
[1,1,0,0,1,1,0,0,1,0] => [1,1,1,0,0,1,1,0,0,1,0,0] => [[[.,.],[[.,.],[.,.]]],.] => 3
[1,1,0,0,1,1,0,1,0,0] => [1,1,1,0,0,1,1,0,1,0,0,0] => [[[.,.],[[.,[.,.]],.]],.] => 3
[1,1,0,0,1,1,1,0,0,0] => [1,1,1,0,0,1,1,1,0,0,0,0] => [[[.,.],[[[.,.],.],.]],.] => 3
[1,1,0,1,0,0,1,0,1,0] => [1,1,1,0,1,0,0,1,0,1,0,0] => [[[.,[.,.]],[.,[.,.]]],.] => 3
[1,1,0,1,0,0,1,1,0,0] => [1,1,1,0,1,0,0,1,1,0,0,0] => [[[.,[.,.]],[[.,.],.]],.] => 3
[1,1,0,1,0,1,0,0,1,0] => [1,1,1,0,1,0,1,0,0,1,0,0] => [[[.,[.,[.,.]]],[.,.]],.] => 3
[1,1,0,1,0,1,0,1,0,0] => [1,1,1,0,1,0,1,0,1,0,0,0] => [[[.,[.,[.,[.,.]]]],.],.] => 3
[1,1,0,1,0,1,1,0,0,0] => [1,1,1,0,1,0,1,1,0,0,0,0] => [[[.,[.,[[.,.],.]]],.],.] => 3
[1,1,0,1,1,0,0,0,1,0] => [1,1,1,0,1,1,0,0,0,1,0,0] => [[[.,[[.,.],.]],[.,.]],.] => 3
[1,1,0,1,1,0,0,1,0,0] => [1,1,1,0,1,1,0,0,1,0,0,0] => [[[.,[[.,.],[.,.]]],.],.] => 3
[1,1,0,1,1,0,1,0,0,0] => [1,1,1,0,1,1,0,1,0,0,0,0] => [[[.,[[.,[.,.]],.]],.],.] => 3
[1,1,0,1,1,1,0,0,0,0] => [1,1,1,0,1,1,1,0,0,0,0,0] => [[[.,[[[.,.],.],.]],.],.] => 3
[1,1,1,0,0,0,1,0,1,0] => [1,1,1,1,0,0,0,1,0,1,0,0] => [[[[.,.],.],[.,[.,.]]],.] => 2
[1,1,1,0,0,0,1,1,0,0] => [1,1,1,1,0,0,0,1,1,0,0,0] => [[[[.,.],.],[[.,.],.]],.] => 2
[1,1,1,0,0,1,0,0,1,0] => [1,1,1,1,0,0,1,0,0,1,0,0] => [[[[.,.],[.,.]],[.,.]],.] => 2
[1,1,1,0,0,1,0,1,0,0] => [1,1,1,1,0,0,1,0,1,0,0,0] => [[[[.,.],[.,[.,.]]],.],.] => 2
[1,1,1,0,0,1,1,0,0,0] => [1,1,1,1,0,0,1,1,0,0,0,0] => [[[[.,.],[[.,.],.]],.],.] => 2
[1,1,1,0,1,0,0,0,1,0] => [1,1,1,1,0,1,0,0,0,1,0,0] => [[[[.,[.,.]],.],[.,.]],.] => 2
[1,1,1,0,1,0,0,1,0,0] => [1,1,1,1,0,1,0,0,1,0,0,0] => [[[[.,[.,.]],[.,.]],.],.] => 2
[1,1,1,0,1,0,1,0,0,0] => [1,1,1,1,0,1,0,1,0,0,0,0] => [[[[.,[.,[.,.]]],.],.],.] => 2
[1,1,1,0,1,1,0,0,0,0] => [1,1,1,1,0,1,1,0,0,0,0,0] => [[[[.,[[.,.],.]],.],.],.] => 2
[1,1,1,1,0,0,0,0,1,0] => [1,1,1,1,1,0,0,0,0,1,0,0] => [[[[[.,.],.],.],[.,.]],.] => 1
[1,1,1,1,0,0,0,1,0,0] => [1,1,1,1,1,0,0,0,1,0,0,0] => [[[[[.,.],.],[.,.]],.],.] => 1
[1,1,1,1,0,0,1,0,0,0] => [1,1,1,1,1,0,0,1,0,0,0,0] => [[[[[.,.],[.,.]],.],.],.] => 1
[1,1,1,1,0,1,0,0,0,0] => [1,1,1,1,1,0,1,0,0,0,0,0] => [[[[[.,[.,.]],.],.],.],.] => 1
[1,1,1,1,1,0,0,0,0,0] => [1,1,1,1,1,1,0,0,0,0,0,0] => [[[[[[.,.],.],.],.],.],.] => 0
[1,0,1,0,1,0,1,0,1,0,1,0] => [1,1,0,1,0,1,0,1,0,1,0,1,0,0] => [[.,[.,[.,[.,[.,[.,.]]]]]],.] => 5
[1,0,1,0,1,0,1,0,1,1,0,0] => [1,1,0,1,0,1,0,1,0,1,1,0,0,0] => [[.,[.,[.,[.,[[.,.],.]]]]],.] => 5
[1,0,1,0,1,0,1,1,0,0,1,0] => [1,1,0,1,0,1,0,1,1,0,0,1,0,0] => [[.,[.,[.,[[.,.],[.,.]]]]],.] => 5
[1,0,1,0,1,0,1,1,0,1,0,0] => [1,1,0,1,0,1,0,1,1,0,1,0,0,0] => [[.,[.,[.,[[.,[.,.]],.]]]],.] => 5
[1,0,1,0,1,0,1,1,1,0,0,0] => [1,1,0,1,0,1,0,1,1,1,0,0,0,0] => [[.,[.,[.,[[[.,.],.],.]]]],.] => 5
[1,0,1,0,1,1,0,0,1,0,1,0] => [1,1,0,1,0,1,1,0,0,1,0,1,0,0] => [[.,[.,[[.,.],[.,[.,.]]]]],.] => 5
[1,0,1,0,1,1,0,0,1,1,0,0] => [1,1,0,1,0,1,1,0,0,1,1,0,0,0] => [[.,[.,[[.,.],[[.,.],.]]]],.] => 5
[1,0,1,0,1,1,0,1,0,0,1,0] => [1,1,0,1,0,1,1,0,1,0,0,1,0,0] => [[.,[.,[[.,[.,.]],[.,.]]]],.] => 5
[1,0,1,0,1,1,0,1,0,1,0,0] => [1,1,0,1,0,1,1,0,1,0,1,0,0,0] => [[.,[.,[[.,[.,[.,.]]],.]]],.] => 5
[1,0,1,0,1,1,0,1,1,0,0,0] => [1,1,0,1,0,1,1,0,1,1,0,0,0,0] => [[.,[.,[[.,[[.,.],.]],.]]],.] => 5
[1,0,1,0,1,1,1,0,0,0,1,0] => [1,1,0,1,0,1,1,1,0,0,0,1,0,0] => [[.,[.,[[[.,.],.],[.,.]]]],.] => 5
[1,0,1,0,1,1,1,0,0,1,0,0] => [1,1,0,1,0,1,1,1,0,0,1,0,0,0] => [[.,[.,[[[.,.],[.,.]],.]]],.] => 5
[1,0,1,0,1,1,1,0,1,0,0,0] => [1,1,0,1,0,1,1,1,0,1,0,0,0,0] => [[.,[.,[[[.,[.,.]],.],.]]],.] => 5
[1,0,1,0,1,1,1,1,0,0,0,0] => [1,1,0,1,0,1,1,1,1,0,0,0,0,0] => [[.,[.,[[[[.,.],.],.],.]]],.] => 5
[1,0,1,1,0,0,1,0,1,0,1,0] => [1,1,0,1,1,0,0,1,0,1,0,1,0,0] => [[.,[[.,.],[.,[.,[.,.]]]]],.] => 5
[1,0,1,1,0,0,1,0,1,1,0,0] => [1,1,0,1,1,0,0,1,0,1,1,0,0,0] => [[.,[[.,.],[.,[[.,.],.]]]],.] => 5
[1,0,1,1,0,0,1,1,0,0,1,0] => [1,1,0,1,1,0,0,1,1,0,0,1,0,0] => [[.,[[.,.],[[.,.],[.,.]]]],.] => 5
[1,0,1,1,0,0,1,1,0,1,0,0] => [1,1,0,1,1,0,0,1,1,0,1,0,0,0] => [[.,[[.,.],[[.,[.,.]],.]]],.] => 5
[1,0,1,1,0,0,1,1,1,0,0,0] => [1,1,0,1,1,0,0,1,1,1,0,0,0,0] => [[.,[[.,.],[[[.,.],.],.]]],.] => 5
[1,0,1,1,0,1,0,0,1,0,1,0] => [1,1,0,1,1,0,1,0,0,1,0,1,0,0] => [[.,[[.,[.,.]],[.,[.,.]]]],.] => 5
[1,0,1,1,0,1,0,0,1,1,0,0] => [1,1,0,1,1,0,1,0,0,1,1,0,0,0] => [[.,[[.,[.,.]],[[.,.],.]]],.] => 5
[1,0,1,1,0,1,0,1,0,0,1,0] => [1,1,0,1,1,0,1,0,1,0,0,1,0,0] => [[.,[[.,[.,[.,.]]],[.,.]]],.] => 5
[1,0,1,1,0,1,0,1,0,1,0,0] => [1,1,0,1,1,0,1,0,1,0,1,0,0,0] => [[.,[[.,[.,[.,[.,.]]]],.]],.] => 5
[1,0,1,1,0,1,0,1,1,0,0,0] => [1,1,0,1,1,0,1,0,1,1,0,0,0,0] => [[.,[[.,[.,[[.,.],.]]],.]],.] => 5
[1,0,1,1,0,1,1,0,0,0,1,0] => [1,1,0,1,1,0,1,1,0,0,0,1,0,0] => [[.,[[.,[[.,.],.]],[.,.]]],.] => 5
[1,0,1,1,0,1,1,0,0,1,0,0] => [1,1,0,1,1,0,1,1,0,0,1,0,0,0] => [[.,[[.,[[.,.],[.,.]]],.]],.] => 5
[1,0,1,1,0,1,1,0,1,0,0,0] => [1,1,0,1,1,0,1,1,0,1,0,0,0,0] => [[.,[[.,[[.,[.,.]],.]],.]],.] => 5
[1,0,1,1,0,1,1,1,0,0,0,0] => [1,1,0,1,1,0,1,1,1,0,0,0,0,0] => [[.,[[.,[[[.,.],.],.]],.]],.] => 5
[1,0,1,1,1,0,0,0,1,0,1,0] => [1,1,0,1,1,1,0,0,0,1,0,1,0,0] => [[.,[[[.,.],.],[.,[.,.]]]],.] => 5
[1,0,1,1,1,0,0,0,1,1,0,0] => [1,1,0,1,1,1,0,0,0,1,1,0,0,0] => [[.,[[[.,.],.],[[.,.],.]]],.] => 5
[1,0,1,1,1,0,0,1,0,0,1,0] => [1,1,0,1,1,1,0,0,1,0,0,1,0,0] => [[.,[[[.,.],[.,.]],[.,.]]],.] => 5
[1,0,1,1,1,0,0,1,0,1,0,0] => [1,1,0,1,1,1,0,0,1,0,1,0,0,0] => [[.,[[[.,.],[.,[.,.]]],.]],.] => 5
[1,0,1,1,1,0,0,1,1,0,0,0] => [1,1,0,1,1,1,0,0,1,1,0,0,0,0] => [[.,[[[.,.],[[.,.],.]],.]],.] => 5
[1,0,1,1,1,0,1,0,0,0,1,0] => [1,1,0,1,1,1,0,1,0,0,0,1,0,0] => [[.,[[[.,[.,.]],.],[.,.]]],.] => 5
[1,0,1,1,1,0,1,0,0,1,0,0] => [1,1,0,1,1,1,0,1,0,0,1,0,0,0] => [[.,[[[.,[.,.]],[.,.]],.]],.] => 5
[1,0,1,1,1,0,1,0,1,0,0,0] => [1,1,0,1,1,1,0,1,0,1,0,0,0,0] => [[.,[[[.,[.,[.,.]]],.],.]],.] => 5
[1,0,1,1,1,0,1,1,0,0,0,0] => [1,1,0,1,1,1,0,1,1,0,0,0,0,0] => [[.,[[[.,[[.,.],.]],.],.]],.] => 5
>>> Load all 197 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
Description
The number of internal nodes of a binary tree.
That is, the total number of nodes of the tree minus St000203The number of external nodes of a binary tree.. A counting formula for the total number of internal nodes across all binary trees of size $n$ is given in [1]. This is equivalent to the number of internal triangles in all triangulations of an $(n+1)$-gon.
That is, the total number of nodes of the tree minus St000203The number of external nodes of a binary tree.. A counting formula for the total number of internal nodes across all binary trees of size $n$ is given in [1]. This is equivalent to the number of internal triangles in all triangulations of an $(n+1)$-gon.
Map
to binary tree: up step, left tree, down step, right tree
Description
Return the binary tree corresponding to the Dyck path under the transformation up step - left tree - down step - right tree.
A Dyck path $D$ of semilength $n$ with $ n > 1$ may be uniquely decomposed into $1L0R$ 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.
A Dyck path $D$ of semilength $n$ with $ n > 1$ may be uniquely decomposed into $1L0R$ 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.
Map
prime Dyck path
Description
Return the Dyck path obtained by adding an initial up and a final down step.
searching the database
Sorry, this statistic was not found in the database
or
add this statistic to the database – it's very simple and we need your support!