A007595 -id:A007595 - cp's OEIS frontend

A069770 Signature permutation of the first non-identity, nonrecursive Catalan automorphism in table A089840: swap the top branches of a binary tree. An involution of nonnegative integers.

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

Offset: 0

Antti Karttunen, Apr 16 2002

nonn

This is the simplest possible Catalan automorphism after the identity bijection (A001477). It effects the following transformation on the unlabeled rooted plane binary trees (letters A and B refer to arbitrary subtrees located on those vectices):
   A   B           B   A
    \ /     -->     \ /
     x               x
  (a . b)  -----> (b . a)
Applying this permutation recursively to the right hand side branch of the binary trees produces permutations A069767 and A069768 (that occur at the same index 1 in tables A122203 and A122204), and applying this recursively to the both branches of binary trees (as in pre- or postorder traversal) produces A057163 (which occurs at the same index 1 in tables A122201 and A122202) that reflects the whole binary tree.
For this permutation, A127302(a(n)) = A127302(n) for all n, [or equally, A153835(a(n)) = A153835(n)], and likewise for all such recursive derivations as mentioned above.

			To obtain the signature permutation, we apply these transformations to the binary trees as encoded and ordered by A014486 and for each n, a(n) will be the position of the tree to which the n-th tree is transformed to, as follows:
.
                   one tree of one internal
  empty tree         (non-leaf) node
      x                      \/
n=    0                      1
a(n)= 0                      1               (both are always fixed)
.
the next 7 trees, with 2-3 internal nodes, in range [A014137(1), A014137(2+1)-1] = [2,8] are:
.
                          \/     \/                 \/     \/
       \/     \/         \/       \/     \/ \/     \/       \/
      \/       \/       \/       \/       \_/       \/       \/
n=     2        3        4        5        6        7        8
.
and the new shapes after swapping their left and right hand subtrees are:
.
                        \/     \/                     \/     \/
     \/         \/     \/       \/       \/ \/       \/       \/
      \/       \/       \/       \/       \_/       \/       \/
a(n)=  3        2        7        8        6        4        5
thus we obtain the first nine terms of this sequence: 0, 1, 3, 2, 7, 8, 6, 4, 5.

Row 1 of A089840.
The number of cycles and the number of fixed points in each subrange limited by terms of A014137 are given by A007595 and A097331.
Other related sequences: A014486, A057163, A069767, A069768, A089864, A123492, A154125, A154126.
Cf. also A127302, A153835.

a(n) = A154125(A154126(n)) = A154126(A154125(n)).

a(n) = A083927(A072796(A057123(n))) = A083927(A057508(A057123(n))) = A083927(A057509(A057123(n))).

Entry revised by Antti Karttunen, Oct 11 2006 and Mar 30 2024

A007123 Number of connected unit interval graphs with n nodes; also number of bracelets (turnover necklaces) with n black beads and n-1 white beads.

Original entry on oeis.org

1, 1, 2, 4, 10, 26, 76, 232, 750, 2494, 8524, 29624, 104468, 372308, 1338936, 4850640, 17685270, 64834550, 238843660, 883677784, 3282152588, 12233309868, 45741634536, 171530482864, 644953425740, 2430975800876, 9183681736376, 34766785487152, 131873995933480

Offset: 1

N. J. A. Sloane

Also number of rooted planar general trees (of n vertices or n-1 edges) up to reflection. - Antti Karttunen, Aug 09 2002 (For the correspondence with bracelets, start by considering Raney's lemma as explained by Graham, Knuth & Patashnik.)
Number of connected lattice path matroids on n elements up to isomorphism.
a(n) = number of noncrossing set partitions of [n] up to reflection (i<->n+1-i). Example: a(4) counts 123, 1-23, 13-2, 1-2-3 but not 12-3 because it is the reflection of 1-23. - David Callan, Oct 08 2005
From Vladimir Shevelev, Apr 23 2011: (Start)
Also number of non-equivalent necklaces of n beads, each of which is painted by one of 2*n-1 colors.
The sequence solves the so-called Reis problem about convex k-gons in case N=2*n-1, k=n. H. Gupta (1979) gave a full solution; I gave a short proof of Gupta's result and showed an equivalence of this problem and each of the following problems: the problem of enumerating the bracelets of n beads of 2 colors, k of them black, and the problem of enumerating the necklaces of k beads, each painted by one of n colors.
a(n) is an essentially unimprovable upper estimate for the number of distinct values of the permanent in (0,1)-circulants of order 2*n-1 with n 1's in every row. (End)
The number of Dyck paths of semilength n-1 up to reversal; that is, the number of Dyck paths of semilength n-1, treating as identical a path and that path when traveled in reverse order. - Noah A Rosenberg, Jan 28 2019

			x + x^2 + 2*x^3 + 4*x^4 + 10*x^5 + 26*x^6 + 76*x^7 + 232*x^8 + 750*x^9 + ...

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.7.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 345 & 346.
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1980.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..1670 (first 190 terms from R. W. Robinson)
J. E. Bonin, A. de Mier, and M. Noy, Lattice path matroids: enumerative aspects and Tutte polynomials, arXiv:math/0211188 [math.CO], 2002.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs., Vol. 3 (2000), #00.1.5.
Hansraj Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., 10 (1979), no. 8, 964-999.
Z. M. Himwich and N. A. Rosenberg, Roadblocked monotonic paths and the enumeration of coalescent histories for non-matching caterpillar gene trees and species trees, arXiv:1901.04465 [qbio.PE], 2019; Adv. Appl. Math. 113 (2020), 101939. (cf. Table 1)
Claudio Procesi, Some special bases of the 2-swap algebras, arXiv:2406.18687 [math.QA], 2024. See p. 3.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Vladimir Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
Vladimir Shevelev, Spectrum of permanent's values and its extremal magnitudes in Lambda_n^3 and Lambda_n(alpha,beta,gamma), arXiv:1104.4051 [math.CO], 2011. (Cf. Section 5).
Index entries for sequences related to bracelets

Cf. A000108, A002420, A007595, A063886, A073201.
Occurs as row 164 in A073201.
Next-to-center columns of triangle A052307.
Equal to A001405 plus A006079.

f[k_Integer, n_] := (Plus @@ (EulerPhi[ # ]Binomial[n/#, k/# ] & /@ Divisors[GCD[n, k]])/n + Binomial[(n - If[OddQ@n, 1, If[OddQ@k, 2, 0]])/2, (k - If[OddQ@k, 1, 0])/2])/2 (* Robert A. Russell, Sep 27 2004 *)
Table[ f[n, 2n - 1], {n, 10}]
(* Comment from Wouter Meeussen, Feb 02 2013, added by N. J. A. Sloane, Feb 02 2013: To get lists of the necklaces in Mathematica, use (if n=4, say):
<

{a(n) = if( n<1, 0, (2 * binomial(n-1, (n-1)\2) + binomial(2*n, n) / (2*n - 1)) / 4)} /* Michael Somos, Apr 16 2012 */

from sympy import catalan, binomial, floor
def a(n): return 1 if n==1 else (catalan(n - 1) + binomial(n - 1, floor((n - 1)/2)))/2 # Indranil Ghosh, Jun 03 2017

a(n+1) = (Catalan(n) + binomial(n, floor(n/2)))/2 = (A000108(n) + A001405(n))/2. - Antti Karttunen, Aug 09 2002
G.f.: (1 + 2*x - sqrt(1 - 4*x)*sqrt(1 - 4*x^2))/(4*sqrt(1 - 4*x^2)).
G.f.: (sqrt((1 + 2*x) / (1 - 2*x)) - sqrt(1 - 4*x)) / 4. - Michael Somos, Apr 16 2012
a(n) = (A063886(n) - A002420(n)) / 4. - Michael Somos, Apr 16 2012
D-finite with recurrence n*(n-1)*(n-4)*a(n) - 4*(n-1)*(n^2-5*n+5)*a(n-1) - 4*(n-2)*(n^2-7*n+11)*a(n-2) + 8*(2*n-7)*(n-2)*(n-3)*a(n-3)=0. - R. J. Mathar, Aug 22 2018

Extended by Christian G. Bower

Edited by Jon E. Schoenfield, Feb 14 2015

A125976 Signature-permutation of Kreweras' 1970 involution on Dyck paths.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 02 2007

nonn

Lalanne shows in the 1992 paper that this automorphism preserves the sum of peak heights, i.e., that A126302(a(n)) = A126302(n) for all n. Furthermore, he also shows that A126306(a(n)) = A057514(n)-1 and likewise, that A057514(a(n)) = A126306(n)+1, for all n >= 1.
Like A069772, this involution keeps symmetric Dyck paths symmetric, but not necessarily same.
The number of cycles and fixed points in range [A014137(n-1)..A014138(n-1)] of this involution seem to be given by A007595 and the "aerated" Catalan numbers [1, 1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42, ...], thus this is probably a conjugate of A069770 (as well as of A057163).

A. Karttunen, Table of n, a(n) for n = 0..2055
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationelle, Cahier no. 15, Paris, 1970, pp. 3-41.
J.-C. Lalanne, Une Involution sur les Chemins de Dyck, European J. Combin. 13 (1992), no. 6, 477-487.
Index entries for signature-permutations of Catalan automorphisms

Cf. A080300, A125974, A014486.
Cf. A057163, A069770, A007595, A014137, A014138.
Compositions and conjugations with other automorphisms: A125977-A125979, A125980, A126290.

a(n) = A080300(A125974(A014486(n))).

A073201 Array of cycle count sequences for the table A073200.

Original entry on oeis.org

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.

A000150 Number of dissections of an n-gon, rooted at an exterior edge, asymmetric with respect to that edge.

Original entry on oeis.org

0, 0, 1, 2, 7, 20, 66, 212, 715, 2424, 8398, 29372, 104006, 371384, 1337220, 4847208, 17678835, 64821680, 238819350, 883629164, 3282060210, 12233125112, 45741281820, 171529777432, 644952073662, 2430973096720, 9183676536076

Offset: 0

N. J. A. Sloane

Number of Dyck paths of length 2n having an odd number of peaks at even height. Example: a(3)=2 because we have UDU(UD)D and U(UD)DUD, where U=(1,1), D=(1,-1) and the peaks at even height are shown between parentheses. - Emeric Deutsch, Nov 13 2004
For n>=1, a(n) is the number of unordered binary trees with n internal nodes in which the left subtree is distinct from the right subtree. - Geoffrey Critzer, Feb 21 2013
Assuming offset -1 this is an analog of A275166: pairs of distinct Catalan numbers with index sum n. - R. J. Mathar, Jul 19 2016

S. J. Cyvin, J. Brunvoll, E. Brendsdal, B. N. Cyvin and E. K. Lloyd, Enumeration of polyene hydrocarbons: a complete mathematical solution, J. Chem. Inf. Comput. Sci., 35 (1995) 743-751
R. K. Guy, "Dissecting a polygon into triangles," Bull. Malayan Math. Soc., Vol. 5, pp. 57-60, 1958.
R. K. Guy, Dissecting a polygon into triangles, Research Paper #9, Math. Dept., Univ. Calgary, 1967.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 78, (3.5.26).
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
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.

T. D. Noe, Table of n, a(n) for n=0..200
S. J. Cyvin, J. Brunvoll, E. Brendsdal, B. N. Cyvin and E. K. Lloyd, Enumeration of polyene hydrocarbons: a complete mathematical solution, J. Chem. Inf. Comput. Sci., 35 (1995) 743-751. [Annotated scanned copy]
R. K. Guy, Dissecting a polygon into triangles, Research Paper #9, Math. Dept., Univ. Calgary, 1967. [Annotated scanned copy]
F. Harary and E. M. Palmer, On acyclic simplicial complexes, Mathematika 15 1968 115-122.
Krishna Menon and Anurag Singh, Grassmannian permutations avoiding identity, arXiv:2212.13794 [math.CO], 2022.
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 Lyndon words

a(n) = T(2n+2, n), array T as in A051168, a count of Lyndon words.
Cf. A051168, A005430.
Cf. A007595.
A diagonal of the square array described in A051168.

nn=20;CoefficientList[Series[x/2(((1-(1-4x)^(1/2))/(2x))^2-(1-(1-4x^2)^(1/2))/(2x^2)),{x,0,nn}],x]  (* Geoffrey Critzer, Feb 21 2013 *)

Let c(x) = (1-sqrt(1-4*x))/(2*x) = g.f. for Catalan numbers (A000108), let d(x) = 1+x*c(x^2). Then g.f. is (c(x)-d(x))/2.
G.f.: (sqrt(1-4*z^2) - sqrt(1-4*z) - 2*z)/(4*z). - Emeric Deutsch, Nov 13 2004
With c(x) defined as above: g.f. = x*(c(x)^2/2 - c(x^2)/2). - Geoffrey Critzer, Feb 21 2013
a(n) = ( 2^(n-3)/sqrt(Pi) ) * ( 4*2^n*GAMMA(n+1/2)/GAMMA(n+2) + ((-1)^n - 1)*GAMMA(n/2)/GAMMA(n/2 + 3/2) ) for n>0. - Mark van Hoeij, Nov 11 2009
a(n) ~ 2^(2*n-1) / (sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 10 2014
a(2n) = A000108(2n) / 2; a(2n+1) = ( A000108(2n+1) - A000108(n) ) / 2. - John Bodeen, Jun 24 2015
D-finite with recurrence +n*(n+1)*(n-2)^2*a(n) -2*n*(2*n-5)*(n-1)^2*a(n-1) -4*n*(n-2)^3*a(n-2) +8*(2*n-5)*(n-3)*(n-1)^2*a(n-3)=0. - R. J. Mathar, Oct 28 2021

Additional comments from Clark Kimberling

A007223 Number of distinct perforation patterns for deriving (v,b) = (n+2,n) punctured convolutional codes from (2,1).

Original entry on oeis.org

1, 2, 8, 24, 85, 286, 1008, 3536, 12618, 45220, 163504, 594320, 2173197, 7983990, 29465440, 109174560, 405995326, 1514797020, 5669021488, 21275014800, 80047272578, 301892460012, 1141069157408, 4321730134624, 16399422757300

Offset: 2

Simon Plouffe

nonn

Number of ways to distribute n pairs parentheses into 2 groups where each group of parentheses represents a Catalan ordering (A000108), and each group must contain at least one pair of parentheses. If one of the groups may have no parentheses, we arrive at A007595. Analog of A274934 with Catalan numbers replacing connected graph counts. - R. J. Mathar, Jul 19 2016
From Petros Hadjicostas, Jul 27 2020: (Start)
"A punctured convolutional code is a high-rate code obtained by the periodic elimination (i.e., puncturing) of specific code symbols from the output of a low-rate encoder. The resulting high-rate code depends on both the low-rate code, called the original code, and the number and specific positions of the punctured symbols." (The quote is from Haccoun and Bégin (1989).)
A high-rate code (v,b) (written as R = b/v) can be constructed from a low-rate code (v0,1) (written as R = 1/v0) by deleting from every v0*b code symbols a number of v0*b - v symbols (so that the resulting rate is R = b/v).
Even though the formulas below do not appear in the two published papers in the IEEE Transactions on Communications, from the theory in those two papers, it makes sense to replace "k|b" with "k|v0*b" (and "k|gcd(v,b)" with "k|gcd(v,v0*b)"). Pab Ter, however, uses "k|b" in the Maple program below. (End)

Guy Bégin, On the enumeration of perforation patterns for punctured convolutional codes, Séries Formelles et Combinatoire Algébrique, 4th colloquium, 15-19 Juin 1992, Montréal, Université du Québec à Montréal, pp. 1-10.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Guy Bégin and David Haccoun, High rate punctured convolutions codes: Structure properties and construction techniques, IEEE Transactions on Communications 37(12) (1989), 1381-1385.
David Haccoun and Guy Bégin, High rate punctured convolutional codes for Viterbi and sequential coding, IEEE Transactions on Communications, 37(11) (1989), 1113-1125; see Section II.

Cf. A000108, A007229, A007595, A274934, A275206.

with(numtheory):P:=proc(b,v0) local k: RETURN(add(phi(k)*(1+z^k)^(v0*(b/k)),k=divisors(b))/b): end; seq(coeff(P(b,2),z,b+2),b=2..40); # Pab Ter

A[x_] = (1 - Sqrt[1 - 4x])/(2x) - 1;
CoefficientList[(A[x]^2 + A[x^2])/(2 x^2) + O[x]^25, x] (* Jean-François Alcover, Apr 30 2023, after R. J. Mathar's proven conjecture *)

Conjecture: Expansion of [A(x)^2 + A(x^2)]/2, where A(x) = A000108(x) - 1. - R. J. Mathar, Jul 19 2016
From Petros Hadjicostas, Jul 27 2020: (Start)
The number of perforation patterns to derive high-rate convolutional code (v,b) (written as R = b/v) from a given low-rate convolutional code (v0, 1) (written as R = 1/v0) is (1/b)*Sum_{k|gcd(v,b)} phi(k)*binomial(v0*b/k, v/k).
According to Pab Ter's Maple code, this is the coefficient of z^v in the polynomial (1/b)*Sum_{k|b} phi(k)*(1 + z^k)^(v0*b/k).
Here (v,b) = (n+2,n) and (v0,1) = (2,1), so
a(n) = (1/n)*Sum_{k|gcd(n+2,n)} phi(k)*binomial(2*n/k, (n+2)/k).
This simplifies to
a(n) = (1/n)*(binomial(2*n, n+2) + [(n mod 2) == 0]*binomial(n, (n/2) + 1)).
It follows from my comments in A275206 that R. J. Mathar's conjecture is correct and that
a(n) = (-2*c(n) + c(n+1) + [(n mod 2) == 0]*c(n/2))/2 for n >= 1, where c = A000108. (End)
D-finite with recurrence -(11*n-30)*(n+2)*(n+1) *a(n) +10*(n+1) *(7*n^2-22*n+6) *a(n-1) -60*(n-2)*(n^2-5*n+1) *a(n-2) -40*(n-2) *(7*n^2-22*n+6) *a(n-3) +16*(2*n-7) *(n-3) *(13*n-22) *a(n-4)=0. - R. J. Mathar, Mar 21 2021

More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 13 2005

a(2) = 1 prepended by R. J. Mathar, Jul 19 2016

A122351 Row 1 of A122289 and A122290. An involution of nonnegative integers.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 01 2006

nonn

The signature-permutation of the automorphism which is derived from the automorphism *A057163 with the recursion schema FORK (see A122201), that is, from the first non-recursive automorphism *A069770 with FORK(FORK(*A069770)) or equivalently, with KROF(KROF(*A069770)) (see A122202).

Index entries for signature-permutations of Catalan automorphisms

A007595 gives the number of orbits in range [A014137(n-1)..A014138(n-1)] of this permutation.

A129604 Signature-permutation of a Catalan automorphism, row 1654720 of A089840.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, May 22 2007

nonn

This involution effects the following transformation on the binary trees (labels A,B,C,D refer to arbitrary subtrees located on those nodes and () stands for a terminal node.)
.A..B.C..D.....D..C.B..A.......B...C...C...B........A...B............B...A
..\./.\./.......\./.\./.........\./.....\./..........\./..............\./.
...x...x....-->..x...x.......()..x..-->..x..()........x..()...-->..()..x..
....\./...........\./.........\./.........\./..........\./..........\./...
.....x.............x...........x...........x............x............x....
Note that automorphism *A069770 = FORK(*A129604) = KROF(*A129604). See the definitions given in A122201 and A122202.

a(n) = A069770(A089864(n)) = A089864(A069770(n)). The number of cycles and the number of fixed points in range [A014137(n-1)..A014138(n-1)] of this involution are given by the same sequences as is the case for example with A069770, A057163 and A122351, that is, A007595 and zero-interspersed A000108.

A071688 Number of plane trees with even number of leaves.

Original entry on oeis.org

0, 1, 3, 7, 20, 66, 217, 715, 2424, 8398, 29414, 104006, 371384, 1337220, 4847637, 17678835, 64821680, 238819350, 883634026, 3282060210, 12233125112, 45741281820, 171529836218, 644952073662, 2430973096720, 9183676536076, 34766775829452, 131873975875180, 501121106988464

Offset: 1

Sen-peng Eu, Jun 23 2002

Number of Dyck n-paths with an even number of peaks (or, equivalently, odd number of valleys). - Yu Hin Au, Dec 07 2019

			a(3) = 3 because among the 5 plane 3-trees there are 3 trees with even number of leaves; a(4) = 7 because among the 14 plane 4-trees there are 7 trees with even number of leaves.

G. C. Greubel, Table of n, a(n) for n = 1..1000
Yu Hin (Gary) Au, Some Properties and Combinatorial Implications of Weighted Small Schröder Numbers, arXiv:1912.00555 [math.CO], 2019.
S. P. Eu, S. C. Liu and Y. N. Yeh, Odd or Even on Plane Trees, Discrete Mathematics, Volume 281, Issues 1-3, 28 April 2004, Pages 189-196.

a(n) + A071684 = A000108: Catalan numbers.

Cf. A007595.

[ &+[2*k*Binomial(n,2*k)^2/(n*(n-2*k+1)): k in [0..Floor(n/2)]] : n in [1..30]]; // G. C. Greubel, Dec 10 2019

seq( add(2*k*binomial(n,2*k)^2/(n*(n-2*k+1)), k=0..floor(n/2)), n=1..30); # G. C. Greubel, Dec 10 2019

a[n_] := If[EvenQ[n], Binomial[2n, n]/(2n + 2), Binomial[2n, n]/(2n + 2) + (-1)^((n + 1)/2)Binomial[n - 1, (n - 1)/2]/(n + 1)]
Table[(CatalanNumber[n] - 2^n Binomial[1/2, (n + 1)/2])/2, {n, 20}] (* Vladimir Reshetnikov, Oct 03 2016 *)

a(n) = 0^n + sum(k=1, n, (1/n)*binomial(n,k)*binomial(n,k-1)*(1+(-1)^k)/2); \\ Michel Marcus, Dec 09 2019

[ sum(2*k*binomial(n,2*k)^2/(n*(n-2*k+1)) for k in (0..floor(n/2))) for n in (1..30)] # G. C. Greubel, Dec 10 2019

a(2n) = (1/(4*n+2))*binomial(4*n, 2*n), a(2n+1) = (1/(4*n+4))*binomial(4*n+2, 2*n+1) + (-1)^(n+1)*(1/(2*n+2))*binomial(2*n, n).
G.f.: (1/4)*(2-(1-4*x)^(1/2) + 2*x - (1+4*x^2)^(1/2))/x. - Vladeta Jovovic, Apr 19 2003
a(0)=1, a(n) = Sum_{k=0..floor(n/2)} (1/n)*C(n,2k-1)*C(n,2k), n>0. - Paul Barry, Jan 25 2007
a(n) = 0^n + Sum_{k=1..n} (1/n)*C(n,k)*C(n,k-1)*(1+(-1)^k)/2. - Paul Barry, Dec 16 2008
a(n) = Sum_{k=0..n} Sum_{j=0..n-k} (-1)^j*(C(n,2*k)*C(n,2*k+j) - C(n,2*k-1)*C(n,2*k+j+1)). - Paul Barry, Sep 13 2010
n*(n+1)*a(n) -2*n*(n+1)*a(n-1) - 4*(2*n^2 -10*n +9)*a(n-2) +8*(n^2 -11*n + 21)*a(n-3) -48*(n-3)*(n-4)*a(n-4) + 32*(2*n-9)*(n-5)*a(n-5) = 0. - R. J. Mathar, Nov 24 2012 (corrected by Yu Hin Au, Dec 09 2019 )
a(n) = (A000108(n) - 2^n * binomial(1/2, (n+1)/2))/2. - Vladimir Reshetnikov, Oct 03 2016
From Vaclav Kotesovec, Oct 04 2016: (Start)
Recurrence (of order 3): n*(n+1)*(5*n^2 - 20*n + 18)*a(n) = 2*n*(2*n - 5)*(5*n^2 - 10*n + 3)*a(n-1) - 4*(n-2)*n*(5*n^2 - 20*n + 18)*a(n-2) + 8*(n-3)*(2*n - 5)*(5*n^2 - 10*n + 3)*a(n-3).
a(n) ~ 2^(2*n-1)/(sqrt(Pi*n)*n).
(End)
a(n) = A119358(n) - A119359(n) = hypergeom([1/2-n/2, 1/2-n/2, -n/2, -n/2], [1/2, 1/2, 1], 1) - hypergeom([-1/2-n/2, 1/2-n/2, 1-n/2, -n/2], [1/2, 1/2, 1], 1). - Vladimir Reshetnikov, Oct 05 2016

Edited by Robert G. Wilson v, Jun 25 2002

A384966 Number of sensed simple planar maps with n vertices and 2 faces.

Original entry on oeis.org

0, 0, 1, 2, 8, 29, 113, 444, 1763, 6951, 27395, 107672, 422330, 1654180, 6472518, 25308760, 98923442, 386589398, 1510737079, 5904291401, 23079308104, 90236258057, 352908128341, 1380632536468, 5403055984114, 21152009997924, 82835786189975, 324518950873991, 1271797441923614, 4985982054721119

Offset: 1

Andrew Howroyd, Jun 14 2025

nonn

In other words, a(n) is the number of embeddings on the sphere of connected simple unicyclic planar graphs with n nodes up to orientation preserving isomorphisms.

Andrew Howroyd, Table of n, a(n) for n = 1..1000

Column 2 of A384964.

Cf. A001429, A006078 (cycle is loop), A007595 (cycle is digon), A380237 (not necessarily simple), A384967 (unsensed version)..

seq(n)={my(c(d)=(1-sqrt(1-4*x^d + O(x*x^(n+d))))/(2*x^d)); Vec(1/(1 - x*c(2)) - x*(c(1)^2 + c(2)) - x^2*(c(1)^4 + 3*c(2)^2)/2 - 1 - sum(k=1, n, log(2 - c(k))*eulerphi(k)/k), -n)/2}

a(n) = A380237(n) - A007595(n) - A006078(n).

cp's OEIS Frontend

A069770 Signature permutation of the first non-identity, nonrecursive Catalan automorphism in table A089840: swap the top branches of a binary tree. An involution of nonnegative integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A007123 Number of connected unit interval graphs with n nodes; also number of bracelets (turnover necklaces) with n black beads and n-1 white beads.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A125976 Signature-permutation of Kreweras' 1970 involution on Dyck paths.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A073201 Array of cycle count sequences for the table A073200.

Views

Author

Keywords

Comments

Links

Crossrefs

A000150 Number of dissections of an n-gon, rooted at an exterior edge, asymmetric with respect to that edge.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A007223 Number of distinct perforation patterns for deriving (v,b) = (n+2,n) punctured convolutional codes from (2,1).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A122351 Row 1 of A122289 and A122290. An involution of nonnegative integers.

Views

Author

Keywords

Comments

Links

Crossrefs

A129604 Signature-permutation of a Catalan automorphism, row 1654720 of A089840.

Views

Author

Keywords

Comments

Links

Crossrefs