A209805 -id:A209805 - cp's OEIS frontend

A001246 Squares of Catalan numbers.

1, 1, 4, 25, 196, 1764, 17424, 184041, 2044900, 23639044, 282105616, 3455793796, 43268992144, 551900410000, 7152629313600, 93990019574025, 1250164827828900, 16807771574144100, 228138727737690000, 3123219182728976100, 43087676888260976400, 598598221893939680400, 8369059450146650049600

Offset: 0

N. J. A. Sloane

Also multi-component meanders.
Also, number of walks within N^2 (the first quadrant of Z^2) starting and ending at (0,0) and consisting of 2 n steps taken from {(-1, -1), (-1, 1), (1, -1), (1, 1)}. [Evans and Pugh show that this is the same sequence.] - N. J. A. Sloane, Jul 04 2014
This is probably the diagonal of A209805. In this case a(n) = number of non-crossing partitions up to rotation of [2n+1] into n+1 blocks. See "Partition related number triangles" in Links section. - Tilman Piesk, Apr 09 2012
a(n) is also the number of regular cover graphs of lattice quotients of essential lattice congruences of the weak order on the symmetric group S_{n+1}. See Table 1 in the Hoang/Mütze reference in the Links section. - Torsten Muetze, Nov 28 2019

T. D. Noe, Table of n, a(n) for n = 0..100
Andrei Asinowski, Cyril Banderier, and Sarah J. Selkirk, From Kreweras to Gessel: A walk through patterns in the quarter plane, Séminaire Lotharingien de Combinatoire, Proc. 35th Conf. Formal Power Series and Alg. Comb. (Davis, 2023) Vol. 89B, Art. #30.
Cyril Banderier, Markus Kuba, Stephan Wagner, and Michael Wallner, Composition schemes: q-enumerations and phase transitions, arXiv:2311.17226 [math.CO], 2023. See p. 6.
Mireille Bousquet-Mélou and Marni Mishna, Walks with small steps in the quarter plane, arXiv:0810.4387 [math.CO], 2008-2009.
P. Di Francesco, O. Golinelli, and E. Guitter, Meander, folding and arch statistics, arXiv:hep-th/9506030, 1995.
David E. Evans and Mathew Pugh, Spectral measures associated to rank two Lie groups and finite subgroups of GL(2,Z), arXiv preprint arXiv:1404.1877 [math.OA], 2014-2015.
O. Guibert, Stack words, standard Young tableaux, permutations with forbidden subsequences and planar maps, Discr. Math., Vol. 210, No. 1-3 (2000), pp. 71-85.
Hung Phuc Hoang and Torsten Mütze, Combinatorial generation via permutation languages. II. Lattice congruences, arXiv:1911.12078 [math.CO], 2019.
Amya Luo, Pattern Avoidance in Nonnesting Permutations, Undergraduate Thesis, Dartmouth College (2024). See p. 11.
Tilman Piesk, Partition related number triangles. (Wikiversity article)
Wikipedia, Ramanujan-Sato series.

Cf. A000108, A000356, A000891, A186264.
Row sums of triangle A008828.
Probably diagonal of A209805.

List([0..25],n->(Binomial(2*n,n)/(n+1))^2); # Muniru A Asiru, Mar 28 2018

seq((binomial(2*n,n)/(1+n))^2, n=0..18); # Zerinvary Lajos, Jun 18 2007

aux[i_Integer, j_Integer, n_Integer] := Which[Min[i, j, n] < 0 || Max[i, j] > n, 0, n == 0, KroneckerDelta[i, j, n], True, aux[i, j, n] = aux[-1 + i, -1 + j, -1 + n] + aux[-1 + i, 1 + j, -1 + n] + aux[1 + i, -1 + j, -1 + n] + aux[1 + i, 1 + j, -1 + n]]; Table[aux[0, 0, 2 n], {n, 0, 25}] (* Manuel Kauers, Nov 18 2008 *)
CatalanNumber[Range[0,30]]^2  (* Harvey P. Dale, Apr 26 2011 *)
a[ n_] := If[ n == -1, 0, CatalanNumber[ n]^2] (* Michael Somos, Jul 11 2011 *)
a[ n_] := SeriesCoefficient[ (2 EllipticE[ 16 x] - (1 - 16 x) EllipticK[ 16 x] - Pi/2) / ( 2 Pi x), {x, 0, n}] (* Michael Somos, Jul 11 2011 *)
a[ n_] := If[ n < 0, 0, (2 n)! SeriesCoefficient[ HypergeometricPFQ[ {1/2}, {2, 2}, 4 x^2], {x, 0, 2 n}]] (* Michael Somos, Jul 11 2011 *)

combinat::dyckWords::count(n)^2 $ n = 0..18 // Zerinvary Lajos, Feb 15 2007

a(n)=(binomial(2*n,n)/(n+1))^2 \\ Charles R Greathouse IV, Jul 16 2011

[catalan_number(i)^2 for i in range(0,19)] # Zerinvary Lajos, May 17 2009

G.f.: -1/(4*x)+1/2*(16*x-1)/x * EllipticK(4*x^(1/2))/Pi + 1/x*EllipticE(4*x^(1/2))/Pi. - Vladeta Jovovic, Oct 12 2003
G.f.: 3F2( (1, 1/2, 1/2); (2, 2); 16x) = (-1 + 2F1( (-1/2, -1/2); (1); 16x))/(4*x) - Olivier Gérard, Feb 16 2011
E.g.f.: hypergeom([1/2], [2, 2], 4*x^2) = 2*BesselI(0, 2*x)^2-BesselI(0, 2*x)*BesselI(1, 2*x)/x-2*BesselI(1, 2*x)^2. - Vladeta Jovovic, Jun 04 2005
D-finite with recurrence (n+1)^2*a(n) -4*(2*n-1)^2*a(n-1)=0. - R. J. Mathar, Jan 04 2013
From Ilya Gutkovskiy, Mar 23 2017: (Start)
a(n) ~ 16^n/(Pi*n^3).
Sum_{n>=0} 1/a(n) = 3F2(1,2,2; 1/2,1/2; 1/16) = 2.295732295098655... (End)
Sum {n>=0} a(n)*(n+1)/16^n = 4/Pi. This is a kind of Ramanujan-Sato series. - Ralf Steiner, Mar 23 2017
From Peter Bala, Mar 28 2018: (Start)
a(n) = 1/(2*n + 1)*f(2*n)/(f(n)*f(n)), where f(n) = n!*(n+1)!. Cf. Catalan(n) = 1/(n + 1)*(2*n)!/(n!*n!).
a(n) = 1/(2*n + 1)*A000891(n).
a(n) = (n + 2)/(2*n + 1)*A000356(n).
a(n) = (n + 2)/3*A186264(n-1). (End)
From Amiram Eldar, Mar 27 2022: (Start)
a(n) = A000108(n)^2.
Sum_{n>=0} a(n)/16^n = 16/Pi - 4. (End)

As a result of the work of Evans and Pugh, it was possible to merge A151342 with this sequence. - N. J. A. Sloane, Jul 04 2014

A054357 Number of unlabeled 2-ary cacti having n polygons. Also number of bicolored plane trees with n edges.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 28, 63, 190, 546, 1708, 5346, 17428, 57148, 191280, 646363, 2210670, 7626166, 26538292, 93013854, 328215300, 1165060668, 4158330416, 14915635378, 53746119972, 194477856100, 706437056648, 2575316704200, 9419571138368

Offset: 0

Simon Plouffe

nonn

a(n) = the number of inequivalent non-crossing partitions of n points (equally spaced) on a circle, under rotations of the circle. This may be considered the number of non-crossing partitions of n unlabeled points on a circle, so this sequence has the same relation to the Catalan numbers (A000108) as the number of partitions of an integer (A000041) has to the Bell numbers (A000110). - Len Smiley, Sep 06 2005

Indranil Ghosh, Table of n, a(n) for n = 0..1000
Miklos Bona, Michel Bousquet, Gilbert Labelle, and Pierre Leroux, Enumeration of m-ary cacti, Advances in Applied Mathematics, 24 (2000), 22-56.
Tilman Piesk, Partition related number triangles
Index entries for sequences related to cacti

Column k=2 of A303912.
Row sums of A209805.
Cf. A002995, A054358, A111275.

a[n_] := If[n == 0, 1, (Binomial[2*n, n]/(n + 1) + DivisorSum[n, Binomial[2*#, #]*EulerPhi[n/#]*Boole[# < n] & ])/n]; Table[a[n], {n, 0, 28}] (* Jean-François Alcover, Jul 17 2017 *)

a(n)=if(n==0, 1, (binomial(2*n, n)/(n + 1) + sumdiv(n, d, binomial(2*d, d)*eulerphi(n/d)*(dIndranil Ghosh, Jul 17 2017

a(n) = if(n==0, 1, sumdiv(n, d, eulerphi(n/d)*binomial(2*d, d))/n - binomial(2*n, n)/(n+1)) \\ Andrew Howroyd, May 02 2018

from sympy import binomial, divisors, totient
def a(n): return 1 if n==0 else (binomial(2*n, n)//(n + 1) + sum(binomial(2*d, d)*totient(n//d)*(dIndranil Ghosh, Jul 17 2017

a(n) = (1/n)*(Sum_{d|n} phi(n/d)*binomial(2*d, d)) - binomial(2*n, n)/(n+1) for n > 0. - Andrew Howroyd, May 02 2018

a(n) ~ 2^(2*n) / (sqrt(Pi) * n^(5/2)). - Vaclav Kotesovec, Jul 17 2017

More terms from Len Smiley, Sep 06 2005

More terms from Vladeta Jovovic, Oct 04 2007

A303694 Array read by antidiagonals: T(n,k) is the number of noncrossing partitions up to rotation composed of n blocks of size k.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 3, 1, 1, 1, 1, 3, 7, 6, 1, 1, 1, 1, 3, 11, 19, 14, 1, 1, 1, 1, 4, 17, 52, 86, 34, 1, 1, 1, 1, 4, 25, 102, 307, 372, 95, 1, 1, 1, 1, 5, 33, 187, 811, 1936, 1825, 280, 1, 1, 1, 1, 5, 43, 300, 1772, 6626, 13207, 9143, 854, 1

Offset: 0

Andrew Howroyd, Apr 28 2018

Also, the number of unlabeled planar k-gonal cacti having n polygons.

The number of noncrossing partitions counted distinctly is given by A070914(n,k-1).

			Array begins:
==================================================================
n\k| 1   2    3     4      5       6       7        8        9
---+--------------------------------------------------------------
0  | 1   1    1     1      1       1       1        1        1 ...
1  | 1   1    1     1      1       1       1        1        1 ...
2  | 1   1    1     1      1       1       1        1        1 ...
3  | 1   2    2     3      3       4       4        5        5 ...
4  | 1   3    7    11     17      25      33       43       55 ...
5  | 1   6   19    52    102     187     300      463      663 ...
6  | 1  14   86   307    811    1772    3412     5993     9821 ...
7  | 1  34  372  1936   6626   17880   40770    82887   154079 ...
8  | 1  95 1825 13207  58385  191967  518043  1213879  2558305 ...
9  | 1 280 9143 93496 532251 2141232 6830545 18471584 44121134 ...
...

Andrew Howroyd, Table of n, a(n) for n = 0..1274
Miklos Bona, Michel Bousquet, Gilbert Labelle, Pierre Leroux, Enumeration of m-ary cacti, arXiv:math/9804119 [math.CO], Apr 1998.
Wikipedia, Cactus graph
Wikipedia, Noncrossing partition
Index entries for sequences related to cacti

Columns 2..7 are A002995(n+1), A054423, A054362, A054365, A054368, A054371.

Cf. A070914, A209805, A303864, A303929.

T[0, _] = 1;
T[n_, k_] := (DivisorSum[n, EulerPhi[n/#] Binomial[k #, #]&] + DivisorSum[ GCD[n-1, k], EulerPhi[#] Binomial[n k/#, (n-1)/#]&])/(k n) - Binomial[k n, n]/(n (k-1) + 1);
Table[T[n-k, k], {n, 0, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, May 22 2018 *)

T(n,k)={if(n==0, 1, (sumdiv(n,d,eulerphi(n/d)*binomial(k*d,d)) + sumdiv(gcd(n-1,k), d, eulerphi(d)*binomial(n*k/d, (n-1)/d)))/(k*n) - binomial(k*n,n)/(n*(k-1)+1))}

T(n,k) = ((Sum_{d|n} phi(n/d)*binomial(k*d,d)) + (Sum_{d|gcd(n-1,k)} phi(d) * binomial(n*k/d, (n-1)/d)))/(k*n) - binomial(k*n,n)/(n*(k-1)+1) for n > 0.

T(n,k) ~ A070914(n,k-1)/(n*k) for fixed k > 1.

A209612 Triangle read by rows: T(n,k) is the number of k-block noncrossing partitions of n-set up to rotations and reflections.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 4, 2, 1, 1, 3, 8, 8, 3, 1, 1, 3, 12, 17, 12, 3, 1, 1, 4, 19, 41, 41, 19, 4, 1, 1, 4, 27, 78, 116, 78, 27, 4, 1, 1, 5, 38, 148, 298, 298, 148, 38, 5, 1, 1, 5, 50, 250, 680, 932, 680, 250, 50, 5, 1

Offset: 1

Tilman Piesk, Mar 10 2012

Like the Narayana triangle A001263 (and unlike A152176) this triangle is symmetric.

			Triangle begins:
1;
1,  1;
1,  1,  1;
1,  2,  2,  1;
1,  2,  4,  2,  1;
1,  3,  8,  8,  3,  1;
1,  3, 12, 17, 12,  3,  1;
1,  4, 19, 41, 41, 19,  4,  1;
1,  4, 27, 78,116, 78, 27,  4,  1;
1,  5, 38,148,298,298,148, 38,  5,  1

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Tilman Piesk, Partition related number triangles

Cf. A111275 (row sums)

Cf. A088855, A209805.

b[n_, k_] := Binomial[n - 1, n - k]*Binomial[n, n - k];
T[n_, k_] := (n*Binomial[Quotient[n - 1, 2], Quotient[k - 1, 2]]*Binomial[ Quotient[n, 2], Quotient[k, 2]] + DivisorSum[GCD[n, k], EulerPhi[#]* b[n/#, k/#]&] + DivisorSum[GCD[n, k - 1], EulerPhi[#]*b[n/#, (n + 1 - k)/#]&] - k*Binomial[n, k]^2/(n - k + 1))/(2*n);
Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 30 2018, after Andrew Howroyd *)

b(n,k)=binomial(n-1,n-k)*binomial(n,n-k);
T(n,k)=(n*binomial((n-1)\2, (k-1)\2)*binomial(n\2, k\2) + sumdiv(gcd(n,k), d, eulerphi(d)*b(n/d,k/d)) + sumdiv(gcd(n,k-1), d, eulerphi(d)*b(n/d,(n+1-k)/d)) - k*binomial(n,k)^2/(n-k+1))/(2*n); \\ Andrew Howroyd, Nov 15 2017

T(n,k) = (A088855(n,k) + A209805(n,k))/2. - Andrew Howroyd, Nov 15 2017

cp's OEIS Frontend

A001246 Squares of Catalan numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Maple

Mathematica

MuPAD

PARI

Sage

Formula

Extensions

A054357 Number of unlabeled 2-ary cacti having n polygons. Also number of bicolored plane trees with n edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

Extensions

A303694 Array read by antidiagonals: T(n,k) is the number of noncrossing partitions up to rotation composed of n blocks of size k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A209612 Triangle read by rows: T(n,k) is the number of k-block noncrossing partitions of n-set up to rotations and reflections.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula