|
%I #60 Jun 03 2020 10:01:43
%S 0,0,1,8,47,244,1186,5536,25147,112028,491870,2135440,9188406,
%T 39249768,166656772,704069248,2961699667,12412521388,51854046982,
%U 216013684528,897632738722,3721813363288,15401045060572,63616796642368,262357557683422,1080387930269464,4443100381114156
%N Total number of two-element anti-chains over all ordered trees on n edges.
%C From _Miklos Bona_, Mar 04 2009: (Start)
%C 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.
%C 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.
%C (End)
%C Appears to be a shifted version of A029760. - _R. J. Mathar_, Mar 30 2014
%C 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
%H Robert Israel, <a href="/A139262/b139262.txt">Table of n, a(n) for n = 0..1650</a>
%H Miklós Bóna, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i1p62">Surprising Symmetries in Objects Counted by Catalan Numbers</a>, Electronic J. Combin., 19 (2012), #P62, eq. (2).
%H Ran Pan, Jeffrey B. Remmel, <a href="http://arxiv.org/abs/1601.07988">Paired patterns in lattice paths</a>, arXiv:1601.07988 [math.CO], 2016.
%H Lifoma Salaam, <a href="https://search.proquest.com/docview/193997569">Combinatorial statistics on phylogenetic trees</a>, Ph.D. Dissertation, Howard University, Washington D.C., 2008.
%H Sittipong Thamrongpairoj, <a href="https://escholarship.org/uc/item/7j561211">Dowling Set Partitions, and Positional Marked Patterns</a>, Ph. D. Dissertation, University of California-San Diego (2019).
%F 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.
%F 2*a(n) = (n+1)*A000984(n) - 4^n. - _J. M. Bergot_, Feb 02 2013
%F 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
%F The above conjecture follows easily from the formula by J. M. Bergot. - _Robert Israel_, Feb 02 2016
%F a(n) = Sum_{k=0..n^2} (n^2-k)/2 * A129182(n,k). - _Alois P. Heinz_, Mar 31 2018
%e 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.
%p 0, seq((n+1)*(2*n-1)!/(n!*(n-1)!) - 2^(2*n-1), n=1..30); # _Robert Israel_, Feb 02 2016
%t a[0] = 0; a[n_] := (n+1)(2n-1)!/(n! (n-1)!) - 2^(2n-1);
%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Aug 19 2018, from Maple *)
%Y Cf. A129182, A139263.
%K nonn
%O 0,4
%A _Lifoma Salaam_, Apr 12 2008
%E Terms beyond a(9) added by _Joerg Arndt_, Dec 30 2012
|
