A014137 -id:A014137 - 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.

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.

A082852 a(0)=0, a(n) = A014137(A072643(n)-1).

Original entry on oeis.org

0, 1, 2, 2, 4, 4, 4, 4, 4, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65

Offset: 0

Antti Karttunen, Apr 17 2003

nonn

A014137(n) occurs A000108(n+1) times.

Used to compute A082853. Cf. also A082855.

a014137[n_] := Sum[CatalanNumber[k], {k, 0, n}];
a072643[n_] := Module[{i, c, a}, i = c = 0; a = 1; While[n > c, a *= (4*i + 2)/(i + 2); i++; c += a]; i];
a[n_] := a014137[a072643[n] - 1];
Table[a[n], {n, 0, 76}] (* Jean-François Alcover, Dec 26 2017 *)

def A082852(n) :
    i = c = 0; a = 1
    while n > c :
        a *= (4*i+2)/(2+i)
        i += 1; c += a
    return c-a+1
[A082852(n) for n in (0..76)] # - Peter Luschny, Sep 07 2012

(define (A082852 n) (if (zero? n) 0 (A014137 (-1+ (A072643 n)))))

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)

A074080 Triangle T(n,k) (listed in order T(1,0), T(2,0), T(2,1), T(3,0), T(3,1), T(3,2), T(4,0), etc.) giving the number of 2^k-cycles that occur in the n-th sub-permutation of A069767/A069768 (i.e., in the range [A014137(n-1)..A014138(n-1)] inclusive).

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 0, 0, 3, 5, 3, 1, 1, 0, 3, 10, 9, 4, 1, 0, 1, 3, 17, 24, 14, 5, 1, 0, 1, 3, 28, 57, 44, 20, 6, 1, 0, 0, 5, 41, 128, 128, 71, 27, 7, 1, 0, 1, 4, 60, 271, 354, 234, 106, 35, 8, 1, 0, 0, 5, 81, 549, 937, 738, 384, 150, 44, 9, 1, 0, 0, 5, 106, 1061

Offset: 0

Antti Karttunen, Aug 19 2002

			If we take the fifth such sub-permutation, i.e., the subsequence A069767[23..64]: [45,46,48,49,50,54,55,57,58,59,61,62,63,64,44,47,53,56,60,43,52,40,31,32,41,34,35,36,42,51,39,30,33,38,29,26,27,37,28,25,24,23], subtract 22 from each term and convert the resulting permutation of [1..42] to disjoint cycle notation, we get:
(17,31),(20,21,30,29),(3,26,12,40),(6,32,8,35,7,33,11,39),(15,22,18,34,16,25,19,38),(1,23,9,36,4,27,13,41,2,24,10,37,5,28,14,42)
which implies that T(5,0) = 0 (no fixed elements), T(5,1) = 1 (one transposition), T(5,2) = 2 (two 4-cycles), T(5,3) = 2 (two 8-cycles), T(5,4) = 1 (and one 16-cycle). It is guaranteed that only cycles whose length is a power of 2 occur in A069767/A069768.

Upper triangular region of the square array A074079 (actually, only the area above its main diagonal, excluding also the leftmost column). T(n, k) = A073430(n, k)/(2^k) [with the rightmost edge of A073430 discarded]. Row sums: A073431. A000108(n) = Sum_{i=0..n-1} 2^i * T(n, i). Cf. A073346, A003056, A002262.

A074079bi := (n,k) -> A073346bi(n,k)/(2^k);
A074080 := n -> A074079bi(A003056(n)+1, A002262(n));
A003056 := n -> floor(sqrt(2*(1+n))-(1/2));
A002262 := n -> n - binomial(floor((1/2)+sqrt(2*(1+n))),2);

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

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

A082852 a(0)=0, a(n) = A014137(A072643(n)-1).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Sage

Scheme

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

Programs

Maple

Formula

A074080 Triangle T(n,k) (listed in order T(1,0), T(2,0), T(2,1), T(3,0), T(3,1), T(3,2), T(4,0), etc.) giving the number of 2^k-cycles that occur in the n-th sub-permutation of A069767/A069768 (i.e., in the range [A014137(n-1)..A014138(n-1)] inclusive).

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple