*****************************************************************************
*       www.FindStat.org - The Combinatorial Statistic Finder               *
*                                                                           *
*       Copyright (C) 2019 The FindStatCrew <info@findstat.org>             *
*                                                                           *
*    This information is distributed in the hope that it will be useful,    *
*    but WITHOUT ANY WARRANTY; without even the implied warranty of         *
*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                   *
*****************************************************************************

-----------------------------------------------------------------------------
Statistic identifier: St000045

-----------------------------------------------------------------------------
Collection: Binary trees

-----------------------------------------------------------------------------
Description: The number of linear extensions of a binary tree. 

Also, the number of increasing / decreasing binary trees labelled by $1, \dots, n$ of this shape.

Also, the size of the sylvester class corresponding to this tree when the Tamari order is seen as a quotient poset of the right weak order on permutations. 

Also, the number of permutations which give this tree shape when inserted in a binary search tree.

Also, the number of permutations which increasing / decreasing tree is of this shape.

-----------------------------------------------------------------------------
References: [1]   Knuth, D. E. The art of computer programming. Volume 3 [[MathSciNet:0445948]]
[2]   Björner, A., Wachs, M. L. $q$-hook length formulas for forests [[MathSciNet:1022316]]
[3]   Hivert, F., Novelli, J.-C., Thibon, J.-Y. The algebra of binary search trees [[MathSciNet:2142078]] [[arXiv:math/0401089]]

-----------------------------------------------------------------------------
Code:
def hook_product(tree):
    if(not tree):
        return 1
    hl = hook_product(tree[0])
    hr = hook_product(tree[1])
    return hl*hr*tree.node_number()
    
def statistic(tree):
    return factorial(tree.node_number()-1)/hook_product(tree[0])/hook_product(tree[1])

-----------------------------------------------------------------------------
Statistic values:

[.,[.,[.,.]]]             => 1
[.,[[.,.],.]]             => 1
[[.,.],[.,.]]             => 2
[[.,[.,.]],.]             => 1
[[[.,.],.],.]             => 1
[.,[.,[.,[.,.]]]]         => 1
[.,[.,[[.,.],.]]]         => 1
[.,[[.,.],[.,.]]]         => 2
[.,[[.,[.,.]],.]]         => 1
[.,[[[.,.],.],.]]         => 1
[[.,.],[.,[.,.]]]         => 3
[[.,.],[[.,.],.]]         => 3
[[.,[.,.]],[.,.]]         => 3
[[[.,.],.],[.,.]]         => 3
[[.,[.,[.,.]]],.]         => 1
[[.,[[.,.],.]],.]         => 1
[[[.,.],[.,.]],.]         => 2
[[[.,[.,.]],.],.]         => 1
[[[[.,.],.],.],.]         => 1
[.,[.,[.,[.,[.,.]]]]]     => 1
[.,[.,[.,[[.,.],.]]]]     => 1
[.,[.,[[.,.],[.,.]]]]     => 2
[.,[.,[[.,[.,.]],.]]]     => 1
[.,[.,[[[.,.],.],.]]]     => 1
[.,[[.,.],[.,[.,.]]]]     => 3
[.,[[.,.],[[.,.],.]]]     => 3
[.,[[.,[.,.]],[.,.]]]     => 3
[.,[[[.,.],.],[.,.]]]     => 3
[.,[[.,[.,[.,.]]],.]]     => 1
[.,[[.,[[.,.],.]],.]]     => 1
[.,[[[.,.],[.,.]],.]]     => 2
[.,[[[.,[.,.]],.],.]]     => 1
[.,[[[[.,.],.],.],.]]     => 1
[[.,.],[.,[.,[.,.]]]]     => 4
[[.,.],[.,[[.,.],.]]]     => 4
[[.,.],[[.,.],[.,.]]]     => 8
[[.,.],[[.,[.,.]],.]]     => 4
[[.,.],[[[.,.],.],.]]     => 4
[[.,[.,.]],[.,[.,.]]]     => 6
[[.,[.,.]],[[.,.],.]]     => 6
[[[.,.],.],[.,[.,.]]]     => 6
[[[.,.],.],[[.,.],.]]     => 6
[[.,[.,[.,.]]],[.,.]]     => 4
[[.,[[.,.],.]],[.,.]]     => 4
[[[.,.],[.,.]],[.,.]]     => 8
[[[.,[.,.]],.],[.,.]]     => 4
[[[[.,.],.],.],[.,.]]     => 4
[[.,[.,[.,[.,.]]]],.]     => 1
[[.,[.,[[.,.],.]]],.]     => 1
[[.,[[.,.],[.,.]]],.]     => 2
[[.,[[.,[.,.]],.]],.]     => 1
[[.,[[[.,.],.],.]],.]     => 1
[[[.,.],[.,[.,.]]],.]     => 3
[[[.,.],[[.,.],.]],.]     => 3
[[[.,[.,.]],[.,.]],.]     => 3
[[[[.,.],.],[.,.]],.]     => 3
[[[.,[.,[.,.]]],.],.]     => 1
[[[.,[[.,.],.]],.],.]     => 1
[[[[.,.],[.,.]],.],.]     => 2
[[[[.,[.,.]],.],.],.]     => 1
[[[[[.,.],.],.],.],.]     => 1
[.,[.,[.,[.,[.,[.,.]]]]]] => 1
[.,[.,[.,[.,[[.,.],.]]]]] => 1
[.,[.,[.,[[.,.],[.,.]]]]] => 2
[.,[.,[.,[[.,[.,.]],.]]]] => 1
[.,[.,[.,[[[.,.],.],.]]]] => 1
[.,[.,[[.,.],[.,[.,.]]]]] => 3
[.,[.,[[.,.],[[.,.],.]]]] => 3
[.,[.,[[.,[.,.]],[.,.]]]] => 3
[.,[.,[[[.,.],.],[.,.]]]] => 3
[.,[.,[[.,[.,[.,.]]],.]]] => 1
[.,[.,[[.,[[.,.],.]],.]]] => 1
[.,[.,[[[.,.],[.,.]],.]]] => 2
[.,[.,[[[.,[.,.]],.],.]]] => 1
[.,[.,[[[[.,.],.],.],.]]] => 1
[.,[[.,.],[.,[.,[.,.]]]]] => 4
[.,[[.,.],[.,[[.,.],.]]]] => 4
[.,[[.,.],[[.,.],[.,.]]]] => 8
[.,[[.,.],[[.,[.,.]],.]]] => 4
[.,[[.,.],[[[.,.],.],.]]] => 4
[.,[[.,[.,.]],[.,[.,.]]]] => 6
[.,[[.,[.,.]],[[.,.],.]]] => 6
[.,[[[.,.],.],[.,[.,.]]]] => 6
[.,[[[.,.],.],[[.,.],.]]] => 6
[.,[[.,[.,[.,.]]],[.,.]]] => 4
[.,[[.,[[.,.],.]],[.,.]]] => 4
[.,[[[.,.],[.,.]],[.,.]]] => 8
[.,[[[.,[.,.]],.],[.,.]]] => 4
[.,[[[[.,.],.],.],[.,.]]] => 4
[.,[[.,[.,[.,[.,.]]]],.]] => 1
[.,[[.,[.,[[.,.],.]]],.]] => 1
[.,[[.,[[.,.],[.,.]]],.]] => 2
[.,[[.,[[.,[.,.]],.]],.]] => 1
[.,[[.,[[[.,.],.],.]],.]] => 1
[.,[[[.,.],[.,[.,.]]],.]] => 3
[.,[[[.,.],[[.,.],.]],.]] => 3
[.,[[[.,[.,.]],[.,.]],.]] => 3
[.,[[[[.,.],.],[.,.]],.]] => 3
[.,[[[.,[.,[.,.]]],.],.]] => 1
[.,[[[.,[[.,.],.]],.],.]] => 1
[.,[[[[.,.],[.,.]],.],.]] => 2
[.,[[[[.,[.,.]],.],.],.]] => 1
[.,[[[[[.,.],.],.],.],.]] => 1
[[.,.],[.,[.,[.,[.,.]]]]] => 5
[[.,.],[.,[.,[[.,.],.]]]] => 5
[[.,.],[.,[[.,.],[.,.]]]] => 10
[[.,.],[.,[[.,[.,.]],.]]] => 5
[[.,.],[.,[[[.,.],.],.]]] => 5
[[.,.],[[.,.],[.,[.,.]]]] => 15
[[.,.],[[.,.],[[.,.],.]]] => 15
[[.,.],[[.,[.,.]],[.,.]]] => 15
[[.,.],[[[.,.],.],[.,.]]] => 15
[[.,.],[[.,[.,[.,.]]],.]] => 5
[[.,.],[[.,[[.,.],.]],.]] => 5
[[.,.],[[[.,.],[.,.]],.]] => 10
[[.,.],[[[.,[.,.]],.],.]] => 5
[[.,.],[[[[.,.],.],.],.]] => 5
[[.,[.,.]],[.,[.,[.,.]]]] => 10
[[.,[.,.]],[.,[[.,.],.]]] => 10
[[.,[.,.]],[[.,.],[.,.]]] => 20
[[.,[.,.]],[[.,[.,.]],.]] => 10
[[.,[.,.]],[[[.,.],.],.]] => 10
[[[.,.],.],[.,[.,[.,.]]]] => 10
[[[.,.],.],[.,[[.,.],.]]] => 10
[[[.,.],.],[[.,.],[.,.]]] => 20
[[[.,.],.],[[.,[.,.]],.]] => 10
[[[.,.],.],[[[.,.],.],.]] => 10
[[.,[.,[.,.]]],[.,[.,.]]] => 10
[[.,[.,[.,.]]],[[.,.],.]] => 10
[[.,[[.,.],.]],[.,[.,.]]] => 10
[[.,[[.,.],.]],[[.,.],.]] => 10
[[[.,.],[.,.]],[.,[.,.]]] => 20
[[[.,.],[.,.]],[[.,.],.]] => 20
[[[.,[.,.]],.],[.,[.,.]]] => 10
[[[.,[.,.]],.],[[.,.],.]] => 10
[[[[.,.],.],.],[.,[.,.]]] => 10
[[[[.,.],.],.],[[.,.],.]] => 10
[[.,[.,[.,[.,.]]]],[.,.]] => 5
[[.,[.,[[.,.],.]]],[.,.]] => 5
[[.,[[.,.],[.,.]]],[.,.]] => 10
[[.,[[.,[.,.]],.]],[.,.]] => 5
[[.,[[[.,.],.],.]],[.,.]] => 5
[[[.,.],[.,[.,.]]],[.,.]] => 15
[[[.,.],[[.,.],.]],[.,.]] => 15
[[[.,[.,.]],[.,.]],[.,.]] => 15
[[[[.,.],.],[.,.]],[.,.]] => 15
[[[.,[.,[.,.]]],.],[.,.]] => 5
[[[.,[[.,.],.]],.],[.,.]] => 5
[[[[.,.],[.,.]],.],[.,.]] => 10
[[[[.,[.,.]],.],.],[.,.]] => 5
[[[[[.,.],.],.],.],[.,.]] => 5
[[.,[.,[.,[.,[.,.]]]]],.] => 1
[[.,[.,[.,[[.,.],.]]]],.] => 1
[[.,[.,[[.,.],[.,.]]]],.] => 2
[[.,[.,[[.,[.,.]],.]]],.] => 1
[[.,[.,[[[.,.],.],.]]],.] => 1
[[.,[[.,.],[.,[.,.]]]],.] => 3
[[.,[[.,.],[[.,.],.]]],.] => 3
[[.,[[.,[.,.]],[.,.]]],.] => 3
[[.,[[[.,.],.],[.,.]]],.] => 3
[[.,[[.,[.,[.,.]]],.]],.] => 1
[[.,[[.,[[.,.],.]],.]],.] => 1
[[.,[[[.,.],[.,.]],.]],.] => 2
[[.,[[[.,[.,.]],.],.]],.] => 1
[[.,[[[[.,.],.],.],.]],.] => 1
[[[.,.],[.,[.,[.,.]]]],.] => 4
[[[.,.],[.,[[.,.],.]]],.] => 4
[[[.,.],[[.,.],[.,.]]],.] => 8
[[[.,.],[[.,[.,.]],.]],.] => 4
[[[.,.],[[[.,.],.],.]],.] => 4
[[[.,[.,.]],[.,[.,.]]],.] => 6
[[[.,[.,.]],[[.,.],.]],.] => 6
[[[[.,.],.],[.,[.,.]]],.] => 6
[[[[.,.],.],[[.,.],.]],.] => 6
[[[.,[.,[.,.]]],[.,.]],.] => 4
[[[.,[[.,.],.]],[.,.]],.] => 4
[[[[.,.],[.,.]],[.,.]],.] => 8
[[[[.,[.,.]],.],[.,.]],.] => 4
[[[[[.,.],.],.],[.,.]],.] => 4
[[[.,[.,[.,[.,.]]]],.],.] => 1
[[[.,[.,[[.,.],.]]],.],.] => 1
[[[.,[[.,.],[.,.]]],.],.] => 2
[[[.,[[.,[.,.]],.]],.],.] => 1
[[[.,[[[.,.],.],.]],.],.] => 1
[[[[.,.],[.,[.,.]]],.],.] => 3
[[[[.,.],[[.,.],.]],.],.] => 3
[[[[.,[.,.]],[.,.]],.],.] => 3
[[[[[.,.],.],[.,.]],.],.] => 3
[[[[.,[.,[.,.]]],.],.],.] => 1
[[[[.,[[.,.],.]],.],.],.] => 1
[[[[[.,.],[.,.]],.],.],.] => 2
[[[[[.,[.,.]],.],.],.],.] => 1
[[[[[[.,.],.],.],.],.],.] => 1

-----------------------------------------------------------------------------
Created: Mar 12, 2013 at 19:04 by Viviane Pons

-----------------------------------------------------------------------------
Last Updated: Oct 17, 2015 at 10:47 by Christian Stump