

A139262


Total number of twoelement antichains over all ordered trees on n edges.


4



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, Mar 04 2009: (Start)
This is the same as the total number of inversions in all 132avoiding permutations of length n by the wellknown 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)
Appears to be a shifted version of A029760.  R. J. Mathar, Mar 30 2014
a(n) is the number of total East steps below y = x1 of all NorthEast 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.
Lifoma Salaam, Combinatorial statistics on phylogenetic trees, Ph.D. Dissertation, Howard University, Washington D.C., 2008.
Sittipong Thamrongpairoj, Dowling Set Partitions, and Positional Marked Patterns, Ph. D. Dissertation, University of CaliforniaSan Diego (2019).


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(14*x))^3*((1sqrt(14*x))/2*x)^2.
2*a(n) = (n+1)*A000984(n)  4^n.  J. M. Bergot, Feb 02 2013
Conjecture: n*(n2)*a(n) +2*(4*n^2+9*n3)*a(n1) +8*(n1)*(2*n3)*a(n2)=0.  R. J. Mathar, Feb 03 2013
The above conjecture follows easily from the formula by J. M. Bergot.  Robert Israel, Feb 02 2016
a(n) = Sum_{k=0..n^2} (n^2k)/2 * A129182(n,k).  Alois P. Heinz, Mar 31 2018


EXAMPLE

a(3) = 8 because there are 5 ordered trees on 3 edges and two of the trees have 2 twoelement antichain each, one of the trees has three two element antichains, one of the trees has one two element antichain and the last tree does not have any twoelement antichains. Hence in ordered trees on 3 edges there are a total of (2)(2)+1(3)+1(1) = 8 two element antichains.


MAPLE

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


MATHEMATICA

a[0] = 0; a[n_] := (n+1)(2n1)!/(n! (n1)!)  2^(2n1);
Table[a[n], {n, 0, 30}] (* JeanFrançois Alcover, Aug 19 2018, from Maple *)


CROSSREFS

Cf. A129182, A139263.
Sequence in context: A106393 A300167 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



