A274644 -id:A274644 - cp's OEIS frontend

A066357 Number of ordered (i.e., planar) trees on 2n edges with every subtree at the root having an even number of edges.

1, 1, 6, 53, 554, 6362, 77580, 986253, 12927170, 173452334, 2370742868, 32892031042, 462030186916, 6557906929108, 93909078262808, 1355087936016957, 19684187540818866, 287612514032460070, 4224238030616082948, 62329883931236020470, 923519220367120779820

Offset: 0

Louis Shapiro, Feb 01 2002

Row sums of A078990. First column of A079513.
a(n) is the number of walks from (0,0) to (2n,2n) using steps (0,1) and (1,0) which never stray below the line y=x and which avoid the points (m,m) m odd. - Paul Boddington, Mar 14 2003
Series reversion of Sum_{n>0} -a(n)(-x)^n is g.f. of A005900.
a(n) is the number of linear extensions of the one-level grid poset G[(0^n), (1^(n-1)), (1^(n-1))]. The definition of a one-level grid poset can be found in the Pan links. - Ran Pan, Jul 05 2016
These numbers have the same parity as the Catalan numbers C(n), that is, a(n) is even except when n has the form 2^m - 1. This follows immediately from the formula a(n) = C(2*n+1) + 2*C(2*n) - 2^(2*n + 1)*C(n) given below by Callan. We conjecture that a(n) and C(n) have the same 2-adic valuation (checked up to n = 100). - Peter Bala, Aug 02 2016

Vincenzo Librandi, Table of n, a(n) for n = 0..200
C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.
Nantel Bergeron, Cesar Ceballos, Vincent Pilaud, Hopf dreams, arXiv:1807.03044 [math.CO], 2018. See p. 17.
A. de Mier and M. Noy, A solution to the tennis ball problem, arXiv:math/0311242 [math.CO], 2003.
J.-G. Luque and J.-Y. Thibon, Noncommutative Symmetric Functions Associated with a Code, Lazard Elimination and Witt Vectors, arXiv:math/0607254 [math.CO], 2006; Discrete Math. Theor. Comput. Sci. 9 (2007), no. 2, 59-72.
D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344 (p. 333).
Ran Pan, Problem 1, Project P.
Ran Pan, Algorithmic Solution to Problem 1 (and linear extensions of general one-level grid-like posets), Project P.
A. Regev, Enumerating triangulations by parallel diagonals, arXiv:1208.3915 [math.CO], 2012, J. Int. Seq. 15 (2012) #12.8.5

Cf. A078990, A079513, A001448, A005900, A079489, A274644, A274763.

[1] cat [(&+[Binomial(4*n,k)*Binomial(3*n-k-2,n-k-1)/n: k in [0..n]]): n in [1..30]]; // G. C. Greubel, Jan 15 2019

gf := (1-sqrt(1-4*z)-sqrt(1+4*z)+sqrt(1-16*z^2))/(z*(sqrt(1-4*z)-sqrt(1+4*z))):s := series(gf, z, 80): for i from 0 to 50 by 2 do printf(`%d,`,coeff(s,z,i)) od: # James Sellers, Feb 11 2002
a := n -> `if`(n=0,1,binomial(3*n-2,n-1)*hypergeom([1-n,-4*n],[2-3*n], -1)/n): seq(simplify(a(n)),n=0..20); # Peter Luschny, Oct 15 2015

CoefficientList[Series[2/(1 + 4 Sqrt[x]/(Sqrt[1 + 4 Sqrt[x]] - Sqrt[1 - 4 Sqrt[x]])), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 21 2014 *)

a(n)=local(A); if(n<1,n==0,A=sqrt(1+4*x+O(x^(2*n+2))); A-=subst(A,x,-x); polcoeff(((2*A-8*x)/A^2)^2,2*n))

vector (100, n, n--; if(n<1, 1, sum(k=0, n, binomial(4*n,k)*binomial(3*n-k-2,n-k-1)/n))) \\ Altug Alkan, Oct 07 2015

[1] + [sum(binomial(4*n,k)*binomial(3*n-k-2,n-k-1)/n for k in (0..n)) for n in (1..30)] # G. C. Greubel, Jan 15 2019

For n>0, a(n) = Sum_{r=1..n} C(2*r-1)*a(n-r). Here C(2*r-1) is a Catalan number (A000108). - Paul Boddington, Mar 14 2003
G.f.: 2/(1+4*sqrt(x)/(sqrt(1+4*sqrt(x))-sqrt(1-4*sqrt(x)))).
D-finite with recurrence a(n)*(2*n-1)*(n+1)n = a(n-1)*(32*n^2 - 64*n + 39)*2*n - a(n-2)*(2*n-3)*(4*n-5)*(4*n-7)*16, n>1.
a(0) = 1,a(n) = (1/n)*Sum_{k=0..n} C(4*n,k)*C(3*n-k-2,n-k-1), n>1. - Paul Barry, Apr 09 2007
a(n) = ((2^(4*n))/Gamma(1/2)) * ((6*(2*n+1)*Gamma(2*n+1/2)/Gamma(2*n+3))-2*Gamma(n+1/2)/Gamma(n+2)). - David Dickson (dcmd(AT)unimelb.edu.au), Nov 10 2009
Convolution of A079489 with itself: (1, 6, 53, 554, ...) = (1, 3, 22, 211, ...)*(1, 3, 22, 211, ...).
Proof. Working with Dyck paths, we must show that Dyck paths of size (semilength) 2n, all of whose components (constituent primitive Dyck paths) have even size, are equinumerous with ordered pairs of nonempty Dyck paths of total size 2n in each of which the first component is of odd size and all other components (if any) are of even size. Given a Dyck path P of the former class, use the first return decomposition to write P (uniquely) as the concatenation of U A_1 A_2 ... A_j O E D Q where U denotes upstep, D denotes downstep, A_1,...,A_j are all primitive Dyck paths of even size with j>=0, O is a primitive Dyck path of odd size, E is a Dyck path of even size, and Q is a Dyck path in which all components are of even size. Then P -> (O A_1 A_2 ... A_j, U E D Q) is the desired bijection. QED - David Callan, Apr 11 2012
a(n) = C(2*n+1) + 2*C(2*n) - 2^(2*n+1)*C(n), where C(n) is the Catalan number A000108. This formula can be obtained by manipulating generating functions. The equivalence of this formula and the Barry (Apr 09 2007) sum can be established by the WZ method with a second-order operator. A combinatorial interpretation of the Barry sum would be nice. - David Callan, Apr 10 2012
a(n) ~ (3-2*sqrt(2)) * 2^(4*n) / (n^(3/2) * sqrt(2*Pi)). - Vaclav Kotesovec, Mar 21 2014
exp( Sum_{n >= 1} binomial(4*n,2*n)*x^n/n ) = 1 + 6*x + 53*x^2 + 554*x^3 + ... is an o.g.f. for this sequence omitting the initial term. See A001448. - Peter Bala, Oct 02 2015
a(n) = binomial(3*n-2,n-1)*hypergeom([1-n,-4*n],[2-3*n],-1)/n for n>=1. - Peter Luschny, Oct 15 2015
a(n) = 3*(2*n+1) /(2*n+2) /(4*n+1) *binomial(4*n+2,2*n+1) -4^n /(2*n+1) *binomial(2*n+2,n+1) [Merlini et al F_n formula] - R. J. Mathar, Oct 01 2021

A274763 Number of linear extensions of the one-level grid poset G[(1^n), (1^(n-1)), (0^(n-1))].

Original entry on oeis.org

1, 10, 215, 7200, 328090, 18914190, 1318595475, 107813147200, 10112867995550, 1070215246700100, 126122386636230950, 16378717184245443000, 2323753119238888045500, 357594668486650175355750, 59323244552378848484536875, 10553747415214416889115286000, 2004246729406751177924041663750, 404685181230584369889138573637500, 86569650968075614116679243211951250, 19558042902565983702641321883519060000

Offset: 1

Ran Pan, Jul 05 2016

nonn

The definition of a one-level grid poset can be found in the Pan links. The number of linear extensions of the one-level grid poset G[(0^n), (0^(n-1)), (0^(n-1))] is given by Catalan number A000108(n) and the number of linear extensions of the one-level grid poset G[(1^n), (0^(n-1)), (0^(n-1))] is given by A274644(n).

Cyril Banderier and Michael Wallner, Young Tableaux with Periodic Walls: Counting with the Density Method, Séminaire Lotharingien de Combinatoire, 85B (2021), Art. 47, 12 pp.
Ran Pan, Problem 1, Project P.
Ran Pan, Algorithmic Solution to Problem 1 (and linear extensions of general one-level grid-like posets), Project P.

Cf. A000108, A274644.

N := 100;
ff[1] := y-x;
for n from 1 to N-1 do
   ff[n+1] := simplify((y-x)*int(int((x-u)*subs(x=u,y=v,ff[n]),v=u..y),u=0..x));
end:
for n from 1 to N do
   a[n] := factorial(4*n-1)*int(int(ff[n],x=0..y),y=0..1);
end:
seq(a[n],n=1..10);
# Michael Wallner, Feb 14 2024

a(n) = (4*n-1)!*Integral_{y=0..1} Integral_{x=0..y} f_{n}(x,y) dx dy where f_{n+1}(x,y) = (y-x)*Integral_{u=0..x} Integral_{v=u..y} (x-u)*f_{n}(u,v) dv du for n>=1 and f_{1}(x,y) = y-x (Derived using the density method; see [Banderier, Wallner 2021]). - Michael Wallner, Feb 14 2024

Corrected and extended by Michael Wallner, Feb 14 2024

A274645 Number of linear extensions of the one-level grid poset G[(2^n), (0^(n-1)), (0^(n-1))].

Original entry on oeis.org

1, 20, 1301, 177260, 41385102, 14760468600, 7465847167005, 5083351577582300, 4483012419041095680, 4971032496120058085376, 6769339545226095791964160, 11105730970797793499164966912, 21604722570792867452576610648064

Offset: 1

Ran Pan, Jun 30 2016

nonn

The definition of a one-level grid poset can be found in the Pan links. The number of linear extensions of the one-level grid poset G[(0^n), (0^(n-1)), (0^(n-1))] is given by the Catalan number A000108(n) and the number of linear extensions of the one-level grid poset G[(1^n), (0^(n-1)), (0^(n-1))] is given by A274644(n).

Ran Pan, Problem 1, Project P.
Ran Pan, Algorithmic Solution to Problem 1 (and linear extensions of general one-level grid-like posets), Project P.

Cf. A000108, A274644.

A274646 Number of linear extensions of the one-level grid poset G[(3^n), (0^(n-1)), (0^(n-1))].

Original entry on oeis.org

1, 70, 26599, 29609650, 72574079902, 332014782982540, 2545213373338499072, 30302687687176712355840, 529556871638491591748878336, 13004213964445490176628310933504, 433440210434110194677894532074307584

Offset: 1

Ran Pan, Jun 30 2016

nonn

The definition of a one-level grid poset can be found in the Pan links. The number of linear extensions of one-level grid poset G[(0^n), (0^(n-1)), (0^(n-1))] is given by Catalan number A000108(n), the number of linear extensions of the one-level grid poset G[(1^n), (0^(n-1)), (0^(n-1))] is given by A274644(n) and number of linear extensions of the one-level grid poset G[(2^n), (0^(n-1)), (0^(n-1))] is given by A274645(n).

Ran Pan, Problem 1, Project P.
Ran Pan, Algorithmic Solution to Problem 1 (and linear extensions of general one-level grid-like posets), Project P.

Cf. A000108, A274644, A274645.

A274764 Number of linear extensions of the one-level grid poset G[(1^n), (1^(n-1)), (1^(n-1))].

Original entry on oeis.org

1, 20, 962, 75080, 8133732, 1127589120, 190416834360, 37902843124640, 8686847271179984, 2252403871470920960, 651771144516905730048, 208193858907016903262208, 72758882836839703611703296, 27613191886304138293279719424, 11308972154842887758316960743424, 4971172331379604809443266242019328

Offset: 1

Ran Pan, Jul 05 2016

nonn

The definition of a one-level grid poset can be found in the Pan links. The number of linear extensions of the one-level grid poset G[(0^n), (0^(n-1)), (0^(n-1))] is given by Catalan number A000108(n), the number of linear extensions of the one-level grid poset G[(1^n), (0^(n-1)), (0^(n-1))] is given by A274644(n) and the number of linear extensions of the one-level grid poset G[(1^n), (1^(n-1)), (0^(n-1))] is given by A274763(n).

Ran Pan, Problem 1, Project P.
Ran Pan, Algorithmic Solution to Problem 1 (and linear extensions of general one-level grid-like posets), Project P.

Cf. A000108, A274644, A274763.

cp's OEIS Frontend

A066357 Number of ordered (i.e., planar) trees on 2n edges with every subtree at the root having an even number of edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

A274763 Number of linear extensions of the one-level grid poset G[(1^n), (1^(n-1)), (0^(n-1))].

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

Extensions

A274645 Number of linear extensions of the one-level grid poset G[(2^n), (0^(n-1)), (0^(n-1))].

Views

Author

Keywords

Comments

Links

Crossrefs

A274646 Number of linear extensions of the one-level grid poset G[(3^n), (0^(n-1)), (0^(n-1))].

Views

Author

Keywords

Comments

Links

Crossrefs

A274764 Number of linear extensions of the one-level grid poset G[(1^n), (1^(n-1)), (1^(n-1))].

Views

Author

Keywords

Comments

Links

Crossrefs