A139262 - OEIS

This site is supported by donations to The OEIS Foundation.

A139262

Total number of two-element anti-chains over all ordered trees on n edges.

0, 0, 1, 8, 47, 244, 1186, 5536, 25147, 112028 (list; graph; refs; listen; history; internal format)

	OFFSET	`0,4`
	COMMENTS	`Contribution from Miklos Bona (bona(AT)math.ufl.edu), Mar 04 2009: (Start)` `This is the same as the total number of inversions in all 132-avoiding` `permutations of length n by the well-known bijection between ordered trees` `on n edges and such permutations.` `For example there are five permutations of length three that avoid 132,` `namely 123, 213, 231, 312, and 321. Their numbers of inversions are,` `respectively, 0,1,2,2, and 3, for a total of eight inversions.` `(End)`
	FORMULA	`A = x^2(B^3)(C^2), where B is the generating function for the central binomial coefficients and C is the generating function for the Catalan numbers. Thus A = x^2 (1/sqrt(1-4x))^3 ((1-sqrt(1-4x))/2x)^2 .`
	MAPLE	`a(3) = 8 because there are 5 ordered trees on 3 edges and two of the trees have 2 two-elemnt anti-chain each, one of the trees has three two element anti-chains, one of the trees has one two element anti-chain and the last tree does not have any two-element anti-chains. Hence in ordered trees on 3 edges there are a total of (2)(2)+1(3)+1(1) = 8 two element anti-chains.`
	CROSSREFS	`Cf. A139263.` `Sequence in context: A081279 A099110 A106393 * A029760 A026900 A016198` `Adjacent sequences: A139259 A139260 A139261 * A139263 A139264 A139265`
	KEYWORD	`nonn`
	AUTHOR	`Lifoma Salaam (lifoma(AT)hotmail.com), Apr 12 2008; revised Apr 12 2008`

Content is available under The OEIS End-User License Agreement .

Last modified February 16 16:39 EST 2012. Contains 205938 sequences.