login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A139262 Total number of two-element anti-chains over all ordered trees on n edges. 2
0, 0, 1, 8, 47, 244, 1186, 5536, 25147, 112028, 491870, 2135440, 9188406, 39249768, 166656772, 704069248, 2961699667, 12412521388, 51854046982, 216013684528, 897632738722, 3721813363288, 15401045060572, 63616796642368, 262357557683422, 1080387930269464, 4443100381114156 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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)

Apperears to be a shifted version of A029760. - R. J. Mathar, Mar 30 2014

a(n) is the number of total East steps below y = x-1 of all North-East paths from (0,0) to (n,n). Details can be found in Section 3.1 and Section 5 in Pan and Remmel's link. - Ran Pan, Feb 01 2016

LINKS

Robert Israel, Table of n, a(n) for n = 0..1650

Miklós Bóna, Surprising Symmetries in Objects Counted by Catalan Numbers, Electronic J. Combin., 19 (2012), #P62, eq. (2).

Ran Pan, Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 2016.

FORMULA

G.f.: (up to offset): 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-4*x))^3*((1-sqrt(1-4*x))/2*x)^2.

2*a(n) = (n+1)*A000984(n) - 4^n. - J. M. Bergot, Feb 02 2013

Conjecture: n*(n-2)*a(n) +2*(-4*n^2+9*n-3)*a(n-1) +8*(n-1)*(2*n-3)*a(n-2)=0. - R. J. Mathar, Feb 03 2013

The above conjecture follows easily from the formula by J. M. Bergot. - Robert Israel, Feb 02 2016

EXAMPLE

a(3) = 8 because there are 5 ordered trees on 3 edges and two of the trees have 2 two-element 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.

MAPLE

0, seq((n+1)*(2*n-1)!/(n!*(n-1)!) - 2^(2*n-1), n=1..30); # Robert Israel, Feb 02 2016

CROSSREFS

Cf. A139263.

Sequence in context: A099110 A106393 A029760 * A026900 A016198 A270495

Adjacent sequences:  A139259 A139260 A139261 * A139263 A139264 A139265

KEYWORD

nonn

AUTHOR

Lifoma Salaam, Apr 12 2008

EXTENSIONS

Terms beyond a(9) added by Joerg Arndt, Dec 30 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 11 21:15 EST 2017. Contains 295919 sequences.