- FindStat

edit this statistic or download as text // json

Identifier

St000385: Binary trees ⟶ ℤ

Values

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

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

[.,[.,[.,.]]] => 2

[.,[[.,.],.]] => 2

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

[[.,[.,.]],.] => 2

[[[.,.],.],.] => 2

[.,[.,[.,[.,.]]]] => 3

[.,[.,[[.,.],.]]] => 3

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

[.,[[.,[.,.]],.]] => 3

[.,[[[.,.],.],.]] => 3

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

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

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

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

[[.,[.,[.,.]]],.] => 3

[[.,[[.,.],.]],.] => 3

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

[[[.,[.,.]],.],.] => 3

[[[[.,.],.],.],.] => 3

[.,[.,[.,[.,[.,.]]]]] => 4

[.,[.,[.,[[.,.],.]]]] => 4

[.,[.,[[.,.],[.,.]]]] => 2

[.,[.,[[.,[.,.]],.]]] => 4

[.,[.,[[[.,.],.],.]]] => 4

[.,[[.,.],[.,[.,.]]]] => 2

[.,[[.,.],[[.,.],.]]] => 2

[.,[[.,[.,.]],[.,.]]] => 2

[.,[[[.,.],.],[.,.]]] => 2

[.,[[.,[.,[.,.]]],.]] => 4

[.,[[.,[[.,.],.]],.]] => 4

[.,[[[.,.],[.,.]],.]] => 2

[.,[[[.,[.,.]],.],.]] => 4

[.,[[[[.,.],.],.],.]] => 4

[[.,.],[.,[.,[.,.]]]] => 2

[[.,.],[.,[[.,.],.]]] => 2

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

[[.,.],[[.,[.,.]],.]] => 2

[[.,.],[[[.,.],.],.]] => 2

[[.,[.,.]],[.,[.,.]]] => 2

[[.,[.,.]],[[.,.],.]] => 2

[[[.,.],.],[.,[.,.]]] => 2

[[[.,.],.],[[.,.],.]] => 2

[[.,[.,[.,.]]],[.,.]] => 2

[[.,[[.,.],.]],[.,.]] => 2

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

[[[.,[.,.]],.],[.,.]] => 2

[[[[.,.],.],.],[.,.]] => 2

[[.,[.,[.,[.,.]]]],.] => 4

[[.,[.,[[.,.],.]]],.] => 4

[[.,[[.,.],[.,.]]],.] => 2

[[.,[[.,[.,.]],.]],.] => 4

[[.,[[[.,.],.],.]],.] => 4

[[[.,.],[.,[.,.]]],.] => 2

[[[.,.],[[.,.],.]],.] => 2

[[[.,[.,.]],[.,.]],.] => 2

[[[[.,.],.],[.,.]],.] => 2

[[[.,[.,[.,.]]],.],.] => 4

[[[.,[[.,.],.]],.],.] => 4

[[[[.,.],[.,.]],.],.] => 2

[[[[.,[.,.]],.],.],.] => 4

[[[[[.,.],.],.],.],.] => 4

[.,[.,[.,[.,[.,[.,.]]]]]] => 5

[.,[.,[.,[.,[[.,.],.]]]]] => 5

[.,[.,[.,[[.,.],[.,.]]]]] => 3

[.,[.,[.,[[.,[.,.]],.]]]] => 5

[.,[.,[.,[[[.,.],.],.]]]] => 5

[.,[.,[[.,.],[.,[.,.]]]]] => 3

[.,[.,[[.,.],[[.,.],.]]]] => 3

[.,[.,[[.,[.,.]],[.,.]]]] => 3

[.,[.,[[[.,.],.],[.,.]]]] => 3

[.,[.,[[.,[.,[.,.]]],.]]] => 5

[.,[.,[[.,[[.,.],.]],.]]] => 5

[.,[.,[[[.,.],[.,.]],.]]] => 3

[.,[.,[[[.,[.,.]],.],.]]] => 5

[.,[.,[[[[.,.],.],.],.]]] => 5

[.,[[.,.],[.,[.,[.,.]]]]] => 3

[.,[[.,.],[.,[[.,.],.]]]] => 3

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

[.,[[.,.],[[.,[.,.]],.]]] => 3

[.,[[.,.],[[[.,.],.],.]]] => 3

[.,[[.,[.,.]],[.,[.,.]]]] => 3

[.,[[.,[.,.]],[[.,.],.]]] => 3

[.,[[[.,.],.],[.,[.,.]]]] => 3

[.,[[[.,.],.],[[.,.],.]]] => 3

[.,[[.,[.,[.,.]]],[.,.]]] => 3

[.,[[.,[[.,.],.]],[.,.]]] => 3

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

[.,[[[.,[.,.]],.],[.,.]]] => 3

[.,[[[[.,.],.],.],[.,.]]] => 3

[.,[[.,[.,[.,[.,.]]]],.]] => 5

[.,[[.,[.,[[.,.],.]]],.]] => 5

[.,[[.,[[.,.],[.,.]]],.]] => 3

[.,[[.,[[.,[.,.]],.]],.]] => 5

[.,[[.,[[[.,.],.],.]],.]] => 5

[.,[[[.,.],[.,[.,.]]],.]] => 3

[.,[[[.,.],[[.,.],.]],.]] => 3

[.,[[[.,[.,.]],[.,.]],.]] => 3

[.,[[[[.,.],.],[.,.]],.]] => 3

[.,[[[.,[.,[.,.]]],.],.]] => 5

>>> 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

Description

The number of vertices with out-degree 1 in a binary tree.
See the references for several connections of this statistic.
In particular, the number $T(n,k)$ of binary trees with $n$ vertices and $k$ out-degree $1$ vertices is given by $T(n,k) = 0$ for $n-k$ odd and
$$T(n,k)=\frac{2^k}{n+1}\binom{n+1}{k}\binom{n+1-k}{(n-k)/2}$$
for $n-k$ is even.

References

[1] Triangle read by rows: T(n,k) is the number of binary trees with n edges and having k vertices of outdegree 1 (n>=0, k>=0). A binary tree is a rooted tree in which each vertex has at most two children and each child of a vertex is designated as its left or right child. OEIS:A121448
[2] Copeland, T. Has anyone seen these binary trees (Catalan-type related to the Gegenbauer polynomials and Motzkin paths)? MathOverflow:230714

Code

def statistic(tree):
    return tree.graph(with_leaves=False).out_degree_sequence().count(1)

Created

Feb 10, 2016 at 09:37 by Christian Stump

Updated

Feb 10, 2016 at 09:57 by Christian Stump