0,4

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)

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 .

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.

Cf. A139263.

Sequence in context: A081279 A099110 A106393 this_sequence A029760 A026900 A016198

Adjacent sequences: A139259 A139260 A139261 this_sequence A139263 A139264 A139265

nonn

Lifoma Salaam (lifoma(AT)hotmail.com), Apr 12 2008; revised Apr 12 2008