|
|
A139262
|
|
Total number of two-element anti-chains 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
|
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(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
|
|
|
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.
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
|
|
MATHEMATICA
|
a[0] = 0; a[n_] := (n+1)(2n-1)!/(n! (n-1)!) - 2^(2n-1);
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|