A014138 -id:A014138 - cp's OEIS frontend

A089408 Number of fixed points in range [A014137(n-1)..A014138(n-1)] of permutation A089864.

1, 1, 2, 1, 2, 2, 4, 5, 10, 14, 28, 42, 84, 132, 264, 429, 858, 1430, 2860, 4862, 9724, 16796, 33592, 58786, 117572, 208012, 416024, 742900, 1485800, 2674440, 5348880, 9694845, 19389690, 35357670, 70715340, 129644790, 259289580, 477638700

Offset: 0

Antti Karttunen, Nov 29 2003

The number of n-node binary trees fixed by the corresponding automorphism(s). Essentially A000108 interleaved with A068875.

Indranil Ghosh, Table of n, a(n) for n = 0..1000
Antti Karttunen, C-program for computing the initial terms of this sequence
Paveł Szabłowski, Beta distributions whose moment sequences are related to integer sequences listed in the OEIS, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 100.

Cf. A089402.

Cf. A000108.

seq(seq(binomial(2*j,j)/(1+j)*i, i=1..2),j=0..19); # Zerinvary Lajos, Apr 29 2007

a[0] = 1; a[n_] := If[EvenQ[n], 2*CatalanNumber[n/2 - 1], CatalanNumber[(n-1)/2]]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Jul 24 2013 *)

from sympy import catalan
def a(n): return 1 if n==0 else 2*catalan(n//2 - 1) if n%2==0 else catalan((n - 1)//2) # Indranil Ghosh, May 23 2017

(define (A089408 n) (cond ((zero? n) 1) ((even? n) (* 2 (A000108 (-1+ (/ n 2))))) (else (A000108 (/ (-1+ n) 2)))))

a(0)=1, a(2n) = 2*A000108(n-1), a(2n+1) = A000108(n)
G.f.: (1+4x-(1+2x)sqrt(1-4x^2))/(2x). - Paul Barry, Apr 11 2005
a(2*j+i) = i*C(2*j,j)/(1+j), i=1..2, j >= 0. - Zerinvary Lajos, Apr 29 2007
D-finite with recurrence: (n+1)*a(n) - 2*a(n-1) + 4(3-n)*a(n-2) = 0. - R. J. Mathar, Dec 17 2011, corrected by Georg Fischer, Feb 13 2020

A057507 Number of cycles in range [A014137(n-1)..A014138(n-1)] of permutation A057505/A057506.

Original entry on oeis.org

1, 1, 1, 2, 3, 10, 18, 46, 95, 236, 528, 1288, 2936, 6984, 16212, 38528, 90717, 216648, 516358, 1240818, 2979992

Offset: 0

Antti Karttunen, Sep 03 2000

For the convenience of the range notation above, we define A014137(-1) and A014138(-1) as zero.

A. Karttunen, C-program for computing the initial terms of this sequence

a(n) = A081148(n)+A081150(n). Bisections: A081151, A081167. Cf. A057545, A060114, A081164.

Occurs for first time in A073201 as row 2614.

A057513 Number of separate orbits to which permutations given in A057511/A057512 (induced by deep rotation of general parenthesizations/plane trees) partition each A000108(n) objects encoded by A014486 between (A014138(n-1)+1)-th and (A014138(n))-th terms.

Original entry on oeis.org

1, 1, 2, 4, 9, 21, 56, 153, 451, 1357, 4212, 13308, 42898, 140276, 465324, 1561955, 5300285, 18156813, 62732842, 218405402, 765657940

Offset: 0

Antti Karttunen Sep 03 2000

It is much faster to compute this sequence empirically with the given C-program than to calculate the terms with the formula in its present form.

A. Karttunen, Gatomorphisms (with the complete Scheme source)
Index entries for sequences related to rooted trees
A. Karttunen, C-program for computing empirically the initial terms of this sequence

CountCycles given in A057502, for other procedures, follow A057511 and A057501.
Similarly generated sequences: A001683, A002995, A003239, A038775, A057507. Cf. also A000081.
Occurs for first time in A073201 as row 12. Cf. A057546 and also A000081.

A057513 := proc(n) local i; `if`((0=n),1,(1/A003418(n-1))*add(A079216bi(n,i),i=1..A003418(n-1))); end;
# Or empirically:
DeepRotatePermutationCycleCounts := proc(upto_n) local u,n,a,r,b; a := []; for n from 0 to upto_n do b := []; u := (binomial(2*n,n)/(n+1)); for r from 0 to u-1 do b := [op(b),1+CatalanRank(n,DeepRotateL(CatalanUnrank(n,r)))]; od; a := [op(a),CountCycles(b)]; od; RETURN(a); end;

a(0)=1, a(n) = (1/A003418(n-1))*Sum_{i=1..A003418(n-1)} A079216(n, i) [Needs improvement.] - Antti Karttunen, Jan 03 2003

A014143 Partial sums of A014138.

Original entry on oeis.org

1, 4, 12, 34, 98, 294, 919, 2974, 9891, 33604, 116103, 406614, 1440025, 5147876, 18550572, 67310938, 245716094, 901759950, 3325066996, 12312494462, 45766188948, 170702447074, 638698318850, 2396598337950

Offset: 0

N. J. A. Sloane

nonn

Self-convolution of A014137. Column in triangle A200965. - Philippe Deléham, Jan 24 2014

For n >= 2, a(n-2) is the number of 021-avoiding ascent sequences of length n with exactly one occurrence of the consecutive pattern 01. For example, with n=3, a(1)=4 counts 001, 010, 011, 012. - David Callan, Nov 13 2019

Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
S. Kitaev, J. Remmel and M. Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv preprint arXiv:1201.6243 [math.CO], 2012. - From _N. J. A. Sloane_, May 09 2012 [An early version on the arXiv had A014043 instead of A014143]
Sergey Kitaev, Jeffrey Remmel, Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16. (arXiv, arXiv:1302.2274 [math.CO], 2013)

Cf. A014137, A200965.

Table[SeriesCoefficient[(1-2*x-Sqrt[1-4*x])/(2*x^2*(1-x)^2),{x,0,n}],{n,0,20}] (* Vaclav Kotesovec, Oct 07 2012 *)
Table[2*Sum[Sum[Binomial[2*j+1,j]/(j+2),{j,0,k}],{k,0,n}],{n,0,20}] (* Vaclav Kotesovec, Oct 27 2012 *)

x='x+O('x^66); Vec((1-2*x-sqrt(1-4*x))/(2*x^2*(1-x)^2)) \\ Joerg Arndt, May 04 2013

G.f.: (1-2*z-sqrt(1-4*z))/(2*z^2*(1-z)^2). - Emeric Deutsch, Jan 27 2003
Recurrence: (n+2)*a(n) = 6*(n+1)*a(n-1) - 3*(3*n+2)*a(n-2) + 2*(2*n+1)*a(n-3). - Vaclav Kotesovec, Oct 07 2012
a(n) ~ 2^(2n+6)/(9*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 07 2012
a(n) = 2 * Sum_{k=0..n} Sum_{j=0..k} C(2*j+1,j)/(j+2). - Vaclav Kotesovec, Oct 27 2012

A057545 Maximum cycle size in range [A014137(n-1)..A014138(n-1)] of permutation A057505/A057506.

Original entry on oeis.org

1, 1, 2, 3, 6, 6, 24, 72, 144, 147, 588, 672, 2136, 10152, 11520, 29484, 117936, 270576, 656352, 2062368, 4040160

Offset: 0

Antti Karttunen, Sep 07 2000

For the convenience of the range notation above, we define A014137(-1) and A014138(-1) as zero.
Equal to the degree of the polynomials M_n(x) Donaghey gives on the page 81 of his paper.
Factored terms: 1, 1, 2, 3, 2*3, 2*3, 2^3 * 3, 2^3 * 3^2, 2^4 * 3^2, 3 * 7^2, 2^2 * 3 * 7^2, 2^5 * 3 * 7, 2^3 * 3 * 89, 2^3 * 3^3 * 47, 2^8 * 3^2 * 5, 2^2 * 3^4 * 7 * 13, 2^4 * 3^4 * 7 * 13, 2^4 * 3^2 * 1879, 2^5 * 3^2 * 43 * 53, 2^5 * 3^3 * 7 * 11 * 31, 2^5 * 3 * 5 * 19 * 443

Robert Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.

Cf. A057507, A060114, A080967, A081165.

Occurs for first time in A073203 as row 2614.

A060114 Least common multiple of all cycle sizes in range [A014137(n-1)..A014138(n-1)] of permutation A057505/A057506.

Original entry on oeis.org

1, 1, 2, 6, 6, 30, 120, 720, 15120, 1164240, 15135120, 283931716867999200, 14510088480716327580681600, 3280681990411073806237542217555200, 936436634805345771521186435213604447980767985241556128000

Offset: 0

Antti Karttunen, Mar 01 2001

nonn

For the convenience of the range notation above, we define A014137(-1) and A014138(-1) as zero.

This sequence grows so fast that it seems hopeless to count A057507 with Burnside's (orbit-counting) lemma.

A. Karttunen, C-program for counting the initial terms of this sequence

Cf. A057505, A057507, A057545, A081165, A081166, A078491.

Occurs for first time in A073204 as row 2614.

A086586 Maximum cycle size in range [A014137(n-1)..A014138(n-1)] of permutations A074681/A074682 & A074683/A074684.

Original entry on oeis.org

1, 1, 2, 5, 9, 28, 57, 253, 842, 3753, 10927, 15014, 130831, 218961, 967104, 3767216, 29715310, 89923607, 314897868, 785059994

Offset: 0

Antti Karttunen, Jun 23 2003

Shifted once right (beginning as 1,1,1,2,5,9,...) this is maximum cycle size (in the same range) of permutations A085169/A085170, shifted twice right (beginning as 1,1,1,1,2,5,9,...) this is the maximum cycle size in permutations A089867/A089868 and A089869/A089870.

Antti Karttunen, C-program for computing the initial terms of this sequence

A073191 Number of separate orbits/cycles to which the Catalan bijections A072796/A072797 partition each A000108(n) structures encoded in the range [A014137(n-1)..A014138(n-1)] of the sequence A014486/A063171.

Original entry on oeis.org

1, 1, 2, 4, 11, 31, 96, 305, 1007, 3389, 11636, 40498, 142714, 507870, 1823040, 6591885, 23989419, 87795473, 322922652, 1193058230, 4425547638, 16475756738, 61539293424, 230548633954, 866095934598, 3261868457698, 12313423931624

Offset: 0

Antti Karttunen, Jun 25 2002

nonn

Occurs for first time in A073201 as row 1.

a(n) = (A000108(n)+A073190(n))/2.

A073193 Number of separate orbits/cycles to which the Catalan bijection A057508 partitions each A000108(n) structures encoded in the range [A014137(n-1)..A014138(n-1)] of the sequence A014486/A063171.

Original entry on oeis.org

1, 1, 2, 4, 11, 30, 93, 292, 965, 3238, 11126, 38708, 136486, 485820, 1744677, 6310584, 22973793, 84103302, 309429066, 1143487428, 4242631626, 15798011604, 59018856522, 221143860936, 830895360978, 3129747395548, 11816242209260

Offset: 0

Antti Karttunen, Jun 25 2002

nonn

Occurs for first time in A073201 as row 168.

a(n) = (A000108(n)+A073192(n))/2

A073431 Number of separate orbits/cycles to which the Catalan bijections A069767/A069768 partition each A000108(n) structures encoded in the range [A014137(n-1)..A014138(n-1)] of the sequence A014486/A063171.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 12, 28, 65, 160, 408, 1074, 2898, 7998, 22508, 64426, 187251, 551730, 1645840, 4964876, 15130808, 46545788, 144424944, 451715460

Offset: 0

Antti Karttunen, Jul 31 2002

nonn

Occurs for first time in A073201 as row 6 (and 8). Column sums of the square array A074079/Row sums of the triangle A074080.

A073431 := proc(n) local i; (1/2^n) * add((2^(n-i))*A073346bi(n,i),i=0..n); end;

a(0)=1, a(n) = (1/(2^(n-1))) * Sum_{i=1..(2^(n-1))} (Sum_{j=0..A007814(i)} A073346(n, j)) = (1/(2^(n-2))) * Sum_{i=1..(2^(n-1))} A073346(n, A007814(i)) - 1 = (1/2^n) * Sum_{i=0..n} (2^(n-i))*A073346(n, i) = Sum_{i=0..n} A074079(n, i)

cp's OEIS Frontend

A089408 Number of fixed points in range [A014137(n-1)..A014138(n-1)] of permutation A089864.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

Scheme

Formula

A057507 Number of cycles in range [A014137(n-1)..A014138(n-1)] of permutation A057505/A057506.

Views

Author

Keywords

Comments

Links

Crossrefs

A057513 Number of separate orbits to which permutations given in A057511/A057512 (induced by deep rotation of general parenthesizations/plane trees) partition each A000108(n) objects encoded by A014486 between (A014138(n-1)+1)-th and (A014138(n))-th terms.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A014143 Partial sums of A014138.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A057545 Maximum cycle size in range [A014137(n-1)..A014138(n-1)] of permutation A057505/A057506.

Views

Author

Keywords

Comments

Links

Crossrefs

A060114 Least common multiple of all cycle sizes in range [A014137(n-1)..A014138(n-1)] of permutation A057505/A057506.

Views

Author

Keywords

Comments

Links

Crossrefs

A086586 Maximum cycle size in range [A014137(n-1)..A014138(n-1)] of permutations A074681/A074682 & A074683/A074684.

Views

Author

Keywords

Comments

Links

A073191 Number of separate orbits/cycles to which the Catalan bijections A072796/A072797 partition each A000108(n) structures encoded in the range [A014137(n-1)..A014138(n-1)] of the sequence A014486/A063171.

Views

Author

Keywords

Crossrefs

Formula

A073193 Number of separate orbits/cycles to which the Catalan bijection A057508 partitions each A000108(n) structures encoded in the range [A014137(n-1)..A014138(n-1)] of the sequence A014486/A063171.

Views

Author

Keywords

Crossrefs

Formula

A073431 Number of separate orbits/cycles to which the Catalan bijections A069767/A069768 partition each A000108(n) structures encoded in the range [A014137(n-1)..A014138(n-1)] of the sequence A014486/A063171.

Views

Author

Keywords

Crossrefs