***************************************************************************** * www.FindStat.org - The Combinatorial Statistic Finder * * * * Copyright (C) 2019 The FindStatCrew * * * * 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