A002995 -id:A002995 - cp's OEIS frontend

A073201 Array of cycle count sequences for the table A073200.

1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 7, 4, 1, 1, 1, 22, 11, 3, 1, 1, 1, 66, 31, 7, 2, 1, 1, 1, 217, 96, 22, 4, 3, 1, 1, 1, 715, 305, 66, 11, 7, 2, 1, 1, 1, 2438, 1007, 217, 30, 22, 4, 2, 2, 1, 1, 8398, 3389, 715, 93, 66, 11, 3, 5, 1, 1, 1, 29414, 11636, 2438, 292, 217, 30, 6, 14, 2, 2, 1, 1

Offset: 0

Antti Karttunen, Jun 25 2002

Each row of this table gives the counts of separate orbits/cycles to which the Catalan bijection given in the corresponding row of A073200 partitions each A000108(n) structures encoded in the range [A014137(n-1)..A014138(n-1)] of the sequence A014486/A063171.

Note that for involutions (self-inverse Catalan bijections) this is always (A000108(n)+Affffff(n))/2, where Affffff is the corresponding "fix-count sequence" from the table A073202.

A. Karttunen, Gatomorphisms (With the complete source and explanation)

Only the first known occurrence(s) given (marked with ? if not yet proved/unclear): rows 0, 2, 4, etc.: A007595, Row 1: A073191, Rows 6 (& 8): A073431, Row 7: A000108, Rows 12, 14, 20, ...: A057513, Rows 16, 18, ...: A003239, Row 57, ..., 164: A007123, Row 168: A073193, Row 261: A002995, Row 2614: A057507, Row 2618 (?), row 17517: A001683.

A002996 a(n) = Sum_{k|n} mu(k)*Catalan(n/k) (mu = Moebius function A008683).

Original entry on oeis.org

1, 1, 4, 12, 41, 126, 428, 1416, 4857, 16753, 58785, 207868, 742899, 2674010, 9694799, 35356240, 129644789, 477633711, 1767263189, 6564103612, 24466266587, 91482504853, 343059613649, 1289903937896, 4861946401410, 18367352329251, 69533550911142, 263747949075908, 1002242216651367

Offset: 1

N. J. A. Sloane

Moebius transform of A000108.

A. Errera, Analysis situs - Un problème d'énumération, Mémoires Acad. Bruxelles, Classe des sciences, Série 2, Vol. XI, Fasc. 6, No. 1421 (1931), 26 pp.
A. Errera, De quelques problèmes d'analysis situs, Comptes Rend. Congr. Nat. Sci. Bruxelles, (1930), 106-110.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=1..200
A. Errera, Analysis situs. Un problème d'énumération.
A. Errera, Reviews of two articles on Analysis Situs, from Fortschritte [Annotated scanned copy]

Cf. A002995, A027750.

a002996 n = sum $ zipWith (*) (map a008683 divs) (map a000108 $ reverse divs)
   where divs = a027750_row n
-- Reinhard Zumkeller, Dec 22 2013

Table[Sum[MoebiusMu[k] CatalanNumber[n/k],{k,Divisors[n]}],{n,30}] (* Harvey P. Dale, Oct 07 2014 *)

a(n)=sumdiv(n, d, moebius(n/d)*binomial(2*d,d)/(d+1)); \\ Joerg Arndt, Jun 15 2013

G.f.: 1 + Sum_{n>=1} a(n)*x^n/(1 - x^n) = 1/(1 - x/(1 - x/(1 - x/(1 - ...)))). - Ilya Gutkovskiy, May 06 2017

More terms from James Sellers, Sep 08 2000

References corrected by M. F. Hasler, Aug 24 2012

A006082 Number of labeled projective plane trees (or "flat" trees) with n nodes.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 12, 27, 65, 175, 490, 1473, 4588, 14782, 48678, 163414, 555885, 1913334, 6646728, 23278989, 82100014, 291361744, 1039758962, 3729276257, 13437206032, 48620868106, 176611864312, 643834562075, 2354902813742, 8640039835974, 31791594259244

Offset: 1

N. J. A. Sloane

nonn

Also, the number of noncrossing partitions up to rotation and reflection composed of n-1 blocks of size 2. - Andrew Howroyd, May 03 2018

R. W. Robinson, personal communication.
R. W. Robinson, Efficiency of power series operations for graph counting, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1982.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..500
David Feldman, Counting plane trees, Unpublished manuscript, 1992. (Annotated scanned copy)
Richard Kapolnai, Gabor Domokos, and Timea Szabo, Generating spherical multiquadrangulations by restricted vertex splittings and the reducibility of equilibrium classes, Periodica Polytechnica Electrical Engineering, 56(1):11-10, 2012. Also arXiv:1206.1698 [cs.DM], 2012. See row 2 of Table 1.
T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352-360. [The sequence is mentioned on page 355, but because of a miscalculation it is given, incorrectly, as 1, 1, 1, 2, 3, 6, 12, 25. Thanks to _David Broadhurst_ for this information. - _N. J. A. Sloane_, Apr 06 2022]
Feng Rong, A note on the topological classification of complex polynomial differential equations with only centre singularities, Journal of Difference Equations and Applications, Volume 18, Issue 11, 2012. - From _N. J. A. Sloane_, Dec 27 2012
P. K. Stockmeyer, The charm bracelet problem and its applications, pp. 339-349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.
P. J. Stockmeyer, The charm bracelet problem and its applications, pp. 339-349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974. [Scanned annotated and corrected copy]
Index entries for sequences related to trees

Column k=2 of A302828 and A303929.
Cf. A006079, A006080, A006081.
Cf. A002995 (noncrossing partitions into pairs up to rotations only), A126120, A001405, A185100.

u[n_, k_, r_] := (r*Binomial[k*n + r, n]/(k*n + r));
e[n_, k_] := Sum[ u[j, k, 1 + (n - 2*j)*k/2], {j, 0, n/2}]
c[n_, k_] := If[n == 0, 1, (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)];
T[n_, k_] := (1/2)*(c[n, k] + If[n == 0, 1, If[OddQ[k], If[OddQ[n], 2*u[ Quotient[n, 2], k, (k + 1)/2], u[n/2, k, 1] + u[n/2 - 1, k, k]], e[n, k] + If[OddQ[n], u[Quotient[n, 2], k, k/2]]]/2]) /. Null -> 0;
a[n_] := T[n, 2];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jun 14 2018, after Andrew Howroyd and A303929 *)

\\ from David Broadhurst, Apr 06 2022, added by N. J. A. Sloane, Apr 06 2022
{A006082(n)=my(c(n)=binomial(2*n,n));
if(n<2,1,n--;(c(n)+if(n%2,2*n*(n+2),(n+1)^2)*c(n\2)
+(n+1)*sumdiv(n,d,if(d>2,eulerphi(d)*c(n/d))))/(4*n*(n+1)));}

a(n) = A006080(n) - A006081(n) + A126120(n-2). [Stockmeyer] [Corrected by Andrey Zabolotskiy, Apr 06 2021]
a(n) = (2 * A002995(n) + A126120(n-2) + A001405(n-1)) / 4 for n > 1. - Andrey Zabolotskiy, May 24 2018
There is a compact formula from David Broadhurst - see the Pari code - N. J. A. Sloane, Apr 06 2022.
a(n) ~ 2^(2*n-4) / (sqrt(Pi) * n^(5/2)). - Vaclav Kotesovec, Jun 01 2022

a(25) and a(26) from Robert W. Robinson, Oct 17 2006

a(27) and beyond from Andrew Howroyd, May 03 2018

A064640 Positions of non-crossing fixed-point-free involutions (encoded by A014486) in A055089, sorted to ascending order.

Original entry on oeis.org

0, 1, 7, 23, 127, 143, 415, 659, 719, 5167, 5183, 5455, 5699, 5759, 16687, 16703, 26815, 28495, 36899, 36959, 38579, 40031, 40319, 368047, 368063, 368335, 368579, 368639, 379567, 379583, 389695, 391375, 399779, 399839, 401459, 402911, 403199

Offset: 0

Antti Karttunen, Oct 02 2001

nonn

These permutations belong to the interpretation (kk) of the exercise 19 in the sixth chapter "Exercises on Catalan and Related Numbers" of Enumerative Combinatorics, Vol. 2, 1999 by R. P. Stanley, Wadsworth, Vol. 1, 1986: Fixed-point-free involutions w of [2n] such that if i < j < k < l and w(i) = k, then w(j) <> l.

From this, it follows that when they are subjected to the same automorphism as used in A061417 and A064636, one gets A002995.

			The first eight such permutations (after the identity) are in positions 1, 7, 23, 127, 143, 415, 659, 719 of A055089: 21, 2143, 4321, 214365, 432165, 216543, 632541, 654321 which written as disjoint cycles are (1 2), (1 2)(3 4), (1 4)(2 3), (1 2)(3 4)(5 6), (1 4)(2 3)(5 6), (1 2)(3 6)(4 5), (1 6)(2 3)(4 5), (1 6)(2 5)(3 4).

R. P. Stanley, Exercises on Catalan and Related Numbers

For the needed Maple procedures see A064638. Cf. also A064639, A060112.

Maple
```
sort(A064638); or sort(A064639);
```

A379430 Array read by antidiagonals: A(n,k) is the number of sensed planar maps with n vertices and k faces, n >= 1, k >= 1.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 5, 5, 2, 3, 14, 23, 14, 3, 6, 42, 108, 108, 42, 6, 14, 140, 501, 761, 501, 140, 14, 34, 473, 2264, 4744, 4744, 2264, 473, 34, 95, 1670, 10087, 27768, 38495, 27768, 10087, 1670, 95, 280, 5969, 44310, 153668, 279698, 279698, 153668, 44310, 5969, 280

Offset: 1

Andrew Howroyd, Jan 13 2025

The planar maps considered are connected and may contain loops and parallel edges.

The number of edges is n + k - 2.

			Array begins:
=========================================================
n\k |  1    2     3      4      5      6      7     8 ...
----+----------------------------------------------------
  1 |  1    1     1      2      3      6     14    34 ...
  2 |  1    2     5     14     42    140    473  1670 ...
  3 |  1    5    23    108    501   2264  10087 44310 ...
  4 |  2   14   108    761   4744  27768 153668 ...
  5 |  3   42   501   4744  38495 279698 ...
  6 |  6  140  2264  27768 279698 ...
  7 | 14  473 10087 153668 ...
  8 | 34 1670 44310 ...
   ...
As a triangle, rows give the number of edges (first row is 0 edges):
   1;
   1,    1;
   1,    2,     1;
   2,    5,     5,     2;
   3,   14,    23,    14,     3;
   6,   42,   108,   108,    42,     6;
  14,  140,   501,   761,   501,   140,    14;
  34,  473,  2264,  4744,  4744,  2264,   473,   34;
  95, 1670, 10087, 27768, 38495, 27768, 10087, 1670, 95;
  ...

Timothy R. Walsh, Number of sensed planar maps with n edges and m vertices, pp. 1-10.

Antidiagonal sums are A006384.
Columns 1..2 are A002995, A380237.
Cf. A269920 (rooted), A277741 (unsensed), A379431 (achiral), A342061 (2-connected), A384964 (simple).

A(n,k) = A(k,n).

A086427 Permutation of natural numbers induced by the Catalan bijection gma086427 acting on symbolless S-expressions encoded by A014486/A063171.

Original entry on oeis.org

0, 1, 3, 2, 8, 6, 7, 5, 4, 22, 19, 20, 15, 14, 21, 16, 18, 13, 12, 17, 10, 11, 9, 64, 60, 61, 52, 51, 62, 53, 55, 41, 40, 54, 38, 39, 37, 63, 56, 57, 43, 42, 59, 47, 50, 36, 34, 49, 35, 32, 31, 58, 44, 46, 27, 26, 48, 29, 33, 30, 45, 24, 25, 28, 23, 196, 191, 192, 178, 177

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

This Catalan bijection rotates by "half step" the interpretations (pp)-(rr) of Stanley, using the "descending slope" mapping illustrated in A086431.

A. Karttunen, Gatomorphisms (With the complete Scheme source)
Index entries for signature-permutations induced by Catalan automorphisms

Inverse: A086428. a(n) = A086431(A086428(A086431(n))) = A057164(A085173(A057164(n))) = A086425(A057501(A086426(n))). Occurs in A073200. Cf. also A086429 (whole step rotate).

Number of cycles: A002995. Number of fixed points: A019590. Max. cycle size: A057543. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

A303864 Array read by antidiagonals: T(n,k) = number of noncrossing path sets on k*n nodes up to rotation with each path having exactly k nodes.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 6, 2, 1, 1, 4, 36, 38, 3, 1, 1, 10, 210, 960, 384, 6, 1, 1, 16, 1176, 18680, 35956, 4425, 14, 1, 1, 36, 6328, 313664, 2280910, 1588192, 57976, 34, 1, 1, 64, 32896, 4683168, 111925464, 323840016, 77381016, 807318, 95, 1

Offset: 0

Andrew Howroyd, May 01 2018

			Array begins:
=======================================================
n\k| 1  2     3        4           5              6
---+---------------------------------------------------
0  | 1  1     1        1           1              1 ...
1  | 1  1     1        3           4             10 ...
2  | 1  1     6       36         210           1176 ...
3  | 1  2    38      960       18680         313664 ...
4  | 1  3   384    35956     2280910      111925464 ...
5  | 1  6  4425  1588192   323840016    46552781760 ...
6  | 1 14 57976 77381016 50668922540 21346459738384 ...
...

Andrew Howroyd, Table of n, a(n) for n = 0..1274

Columns 2..4 are A002995(n+1), A303865, A303866.
Row n=1 is A051437(k-3).
Cf. A302828, A303844, A303869.
Cf. A295224 (polygon dissections), A303694 (sets of cycles instead of paths).

nmax = 10; seq[n_, k_] := Module[{p, q, h}, p = 1 + InverseSeries[ x/(k*2^If[k == 1, 0, k - 3]*(1 + x)^k) + O[x]^n, x ]; h = p /. x -> x^2 + O[x]^n; q = x*D[p, x]/p; Integrate[((p - 1)/k + Sum[EulerPhi[d]*(q /. x -> x^d + O[x]^n), {d, 2, n}])/x, x] + If[OddQ[k], 0, 2^(k/2 - 2)*x*h^(k/2)] + 1];
Clear[col]; col[k_] := col[k] = CoefficientList[seq[nmax, k], x];
T[n_, k_] := col[k][[n + 1]];
Table[T[n - k, k], {n, 0, nmax}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jul 04 2018, after Andrew Howroyd *)

seq(n,k)={ \\ gives gf of k'th column
my(p=1 + serreverse( x/(k*2^if(k==1, 0, k-3)*(1 + x)^k) + O(x*x^n) ));
my(h=subst(p,x,x^2+O(x*x^n)), q=x*deriv(p)/p);
intformal( ((p-1)/k + sum(d=2,n,eulerphi(d)*subst(q,x,x^d+O(x*x^n))))/x) + if(k%2, 0, 2^(k/2-2)*x*h^(k/2)) + 1;
}
Mat(vector(6, k, Col(seq(7, k))))

A380615 Triangle read by rows: T(n,k) is the number of sensed combinatorial maps with n edges and k vertices, 1 <= k <= n + 1.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 5, 8, 5, 2, 18, 38, 34, 14, 3, 105, 275, 288, 154, 42, 6, 902, 2614, 3102, 1959, 705, 140, 14, 9749, 30346, 39242, 27898, 11956, 3142, 473, 34, 127072, 415360, 573654, 446078, 217000, 68544, 13886, 1670, 95, 1915951, 6513999, 9484003, 7911844, 4230802, 1523176, 373188, 60614, 5969, 280

Offset: 0

Andrew Howroyd, Jan 28 2025

By duality, also the number of sensed combinatorial maps with n edges and k faces.

			Triangle begins:
n\k |      1       2       3       4       5      6      7     8   9
----+----------------------------------------------------------------
  0 |      1
  1 |      1,      1
  2 |      2,      2,      1;
  3 |      5,      8,      5,      2;
  4 |     18,     38,     34,     14,      3;
  5 |    105,    275,    288,    154,     42,     6;
  6 |    902,   2614,   3102,   1959,    705,   140,    14;
  7 |   9749,  30346,  39242,  27898,  11956,  3142,   473,   34;
  8 | 127072, 415360, 573654, 446078, 217000, 68544, 13886, 1670, 95;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Row sums are A170946.
Main diagonal is A002995(n+1).
Second diagonal gives A380237.
Columns 1..3 are A007769, A380618, A380619.
Cf. A053979 (rooted), A379430 (planar), A380616 (unsensed), A380617 (achiral).

InvEulerMTS(p)={my(n=serprec(p, x)-1, q=log(p), vars=variables(p)); sum(i=1, n, moebius(i)*substvec(q + O(x*x^(n\i)), vars, apply(v->v^i, vars))/i)}
b(k,r)={if(k%2, if(r%2, 0, my(j=r/2); k^j*(2*j)!/(j!*2^j)), sum(j=0, r\2, binomial(r, 2*j)*k^j*(2*j)!/(j!*2^j)))}
C(k,r,y)={my(p=sumdiv(k,d,eulerphi(k/d)*y^d)/k); sum(i=0, r, abs(stirling(r,i,1))*p^i)/r!}
S(n,k,y)={sum(r=0, 2*n\k, if(k*r%2==0, x^(k*r/2)*b(k,r)*C(k,r,y)), O(x*x^n))}
G(n,y='y)={prod(k=1, 2*n, S(n,k,y))}
T(n)={[Vecrev(p/y) | p<-Vec(y+InvEulerMTS(G(n)))]}
{ my(A=T(10)); for(i=1, #A, print(A[i])) }

A086428 Permutation of natural numbers induced by the Catalan bijection gma086428 acting on symbolless S-expressions encoded by A014486/A063171.

Original entry on oeis.org

0, 1, 3, 2, 8, 7, 5, 6, 4, 22, 20, 21, 18, 17, 13, 12, 15, 19, 16, 10, 11, 14, 9, 64, 61, 62, 55, 54, 63, 57, 59, 50, 49, 58, 46, 48, 45, 36, 34, 35, 32, 31, 41, 40, 52, 60, 53, 43, 56, 47, 44, 27, 26, 29, 33, 30, 38, 39, 51, 42, 24, 25, 28, 37, 23, 196, 192, 193, 181, 180

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

This Catalan bijection rotates by "half step" the interpretations (pp)-(rr) of Stanley, using the "descending slope" mapping illustrated in A086431.

A. Karttunen, Gatomorphisms (With the complete Scheme source)
Index entries for signature-permutations induced by Catalan automorphisms

Inverse: A086427. a(n) = A086431(A086427(A086431(n))) = A057164(A085174(A057164(n))) = A086425(A057502(A086426(n))). Occurs in A073200. Cf. also A086430 (whole step rotate).

Number of cycles: A002995. Number of fixed points: A019590. Max. cycle size: A057543. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

A175954 Unlabeled (cyclic) Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n unlabeled points equally spaced on a circle, up to rotations of the circle.

Original entry on oeis.org

1, 1, 2, 2, 4, 5, 12, 19, 46, 95, 230, 528, 1320, 3219, 8172, 20714, 53478, 138635, 363486, 957858, 2543476, 6788019, 18218772, 49120019, 133036406, 361736109, 987316658, 2703991820, 7429445752, 20473889133, 56579632732, 156766505691

Offset: 0

Max Alekseyev, Oct 29 2010

nonn

Unlabeled version of A001006.

The number of such chord configurations on 2n vertices with n chords is given by A002995(n+1).

Andrew Howroyd, Table of n, a(n) for n = 0..200
Andrew Howroyd, Chord Configuration Symmetries

Cf. A001006, A185100, A002426, A002995.

a1006[0] = 1; a1006[n_Integer] := a1006[n] = a1006[n-1] + Sum[a1006[k]* a1006[n -2-k], {k, 0, n-2}];
a142150[n_] := n*(1 + (-1)^n)/4;
a2426[n_] := Coefficient[(1 + x + x^2)^n, x, n];
a[0] = 1; a[n_] := (1/n)*(a1006[n]+a142150[n]*a1006[n/2-1] + Sum[EulerPhi[ n/d]*a2426[d], {d, Most @ Divisors[n]}]);
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Jul 02 2018, after Andrew Howroyd *)

For odd prime p, a(p) = (A001006(p) - 1)/p + 1.

a(n) = (1/n) * (A001006(n) + A142150(n) * A001006(n/2-1) + Sum{d|n, dA002426(d)). - Andrew Howroyd, Apr 01 2017

cp's OEIS Frontend

A073201 Array of cycle count sequences for the table A073200.

Views

Author

Keywords

Comments

Links

Crossrefs

A002996 a(n) = Sum_{k|n} mu(k)*Catalan(n/k) (mu = Moebius function A008683).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A006082 Number of labeled projective plane trees (or "flat" trees) with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A064640 Positions of non-crossing fixed-point-free involutions (encoded by A014486) in A055089, sorted to ascending order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A379430 Array read by antidiagonals: A(n,k) is the number of sensed planar maps with n vertices and k faces, n >= 1, k >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A086427 Permutation of natural numbers induced by the Catalan bijection gma086427 acting on symbolless S-expressions encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

A303864 Array read by antidiagonals: T(n,k) = number of noncrossing path sets on k*n nodes up to rotation with each path having exactly k nodes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A380615 Triangle read by rows: T(n,k) is the number of sensed combinatorial maps with n edges and k vertices, 1 <= k <= n + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs