A000782 -id:A000782 - cp's OEIS frontend

A215512 a(n) = 5a(n-1) - 6a(n-2) + a(n-3), with a(0)=1, a(1)=3, a(2)=8.

1, 3, 8, 23, 70, 220, 703, 2265, 7327, 23748, 77043, 250054, 811760, 2635519, 8557089, 27784091, 90213440, 292919743, 951102166, 3088205812, 10027335807, 32558546329, 105716922615, 343260670908, 1114560365179, 3618954723062, 11750672095144, 38154192502527

Offset: 0

Roman Witula, Aug 14 2012

The Berndt-type sequence number 7 for the argument 2Pi/7 defined by the relation: sqrt(7)*a(n) = s(1)*c(4)^(2*n) + s(2)*c(1)^(2*n) + s(4)*c(2)^(2*n), where c(j):=2*cos(2*Pi*j/7) and s(j):=2*sin(2*Pi*j/7). If we additionally defined the following sequences:
sqrt(7)*b(n) = s(2)*c(4)^(2*n) + s(4)*c(1)^(2*n) + s(1)*c(2)^(2*n),
sqrt(7)*c(n) = s(4)*c(4)^(2*n) + s(1)*c(1)^(2*n) + s(2)*c(2)^(2*n), and
sqrt(7)*a1(n) = s(1)*c(4)^(2*n+1) + s(2)*c(1)^(2*n+1) + s(4)*c(2)^(2*n+1),
sqrt(7)*b1(n) = s(2)*c(4)^(2*n+1) + s(4)*c(1)^(2*n+1) + s(1)*c(2)^(2*n+1),
sqrt(7)*c1(n) = s(4)*c(4)^(2*n+1) + s(1)*c(1)^(2*n+1) + s(2)*c(2)^(2*n+1), then the following simple relationships between elements of these sequences hold true: a(n)=c1(n), c(n+1)=a1(n), -a(n)-b(n)=b1(n), which means that the sequences a1(n), b1(n), and c1(n) are completely and in very simple way determined by the sequences a(n), b(n) and c(n). However the last one's satisfy the following system of recurrence equations: a(n+1) = 2*a(n) + b(n), b(n+1) = a(n) + 2*b(n) - c(n), c(n+1) = c(n) - b(n). We have b(n)=A215694(n) and c(n)=A215695(n).
We note that a(n)=A000782(n) for every n=0,1,...,4 and A000782(5)-a(5)=2.
From general recurrence relation: a(n) = 5*a(n-1) - 6*a(n-2) + a(n-3), i.e. a(n) = 5*(a(n-1)-a(n-2)) + (a(n-3)-a(n-2)) the following summation formula can be easily obtained: sum{k=3,..,n} a(k) = 5*a(n-1)-a(n-2)+a(0)-5*a(1). Hence in discussed sequence it follows that: sum{k=3,..,n} a(k) = 5*a(n-1) - a(n-2) - 14.

			We have a(6) = 10*a(4)+a(1), a(5) = 11*(a(3)-a(1)), a(10)-a(4)+a(3)+a(1)+a(0) = 77*10^3, and a(11)-a(4)+a(3)-a(2)+a(0) = 25*10^4 = (5^6)*(2^4).

G. C. Greubel, Table of n, a(n) for n = 0..1000
Roman Witula and Damian Slota, New Ramanujan-Type Formulas and Quasi-Fibonacci Numbers of Order 7, Journal of Integer Sequences, Vol. 10 (2007), Article 07.5.6
Index entries for linear recurrences with constant coefficients, signature (5, -6, 1).

Cf.A215694, A215695, A215007, A215008, A215143, A215493, A215494, A215510, A215575, A215455, A214683, A214699.

I:=[1,3,8]; [n le 3 select I[n] else 5*Self(n-1) - 6*Self(n-2) + Self(n-3): n in [1..30]]; // G. C. Greubel, Apr 23 2018

Mathematica
```
LinearRecurrence[{5,-6,1}, {1,3,8}, 50]
```

x='x+O('x^30); Vec((1-2*x-x^2)/(1-5*x+6*x^2-x^3)) \\ G. C. Greubel, Apr 23 2018

G.f.: (1-2*x-x^2)/(1-5*x+6*x^2-x^3).

A071721 Expansion of (1+x^2C^2)C^2, where C = (1-(1-4x)^(1/2))/(2x) is g.f. for Catalan numbers, A000108.

Original entry on oeis.org

1, 2, 6, 18, 56, 180, 594, 2002, 6864, 23868, 83980, 298452, 1069776, 3863080, 14040810, 51325650, 188574240, 695987820, 2579248980, 9593714460, 35804293200, 134032593240, 503154100020, 1893689067348, 7144084508256

Offset: 0

N. J. A. Sloane, Jun 06 2002

nonn

a(n) = A138156(n) - 4*A138156(n-1). - Alzhekeyev Ascar M, Jul 19 2011
Apparently, for n>=1, the sum of the heights of the first and last peaks in all Dyck n-paths (in paths with one peak the height counts as both first and last). - David Scambler, Oct 05 2012
For n>=1, a(n) is the total number of nonempty subtrees over all binary trees having n+1 internal nodes.  Here, a binary tree is a full (each node has two or zero children), rooted, plane (ordered), unlabeled tree.  An empty subtree is a tree attached to the root that consists only of an external node.  a(n) = 2*A002057(n-2) + A068875(n). - Geoffrey Critzer, Sep 16 2013
From Colin Defant, Sep 15 2018: (Start)
a(n) is the number of permutations pi of [n+1] such that s(pi) avoids the patterns 132, 231, 312, and 321, where s denotes West's stack-sorting map.
a(n) is the number of permutations on [n+1] that avoid the patterns 1342, 2341, 3142, 3241, 3412, and 3421. (End)

			G.f. = 1 + 2*x + 6*x^2 + 18*x^3 + 56*x^4 + 180*x^5 + 594*x^6 + 2002*x^7 + ... - _Michael Somos_, Apr 22 2022

Michael De Vlieger, Table of n, a(n) for n = 0..1000
Colin Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.
Stoyan Dimitrov, On permutation patterns with constrained gap sizes, arXiv:2002.12322 [math.CO], 2020.
Ling Gao, Graph assembly for spider and tadpole graphs, Master's Thesis, Cal. State Poly. Univ. (2023). See p. 32.
Boram Park and Seonjeong Park, Shellable posets arising from even subgraphs of a graph, arXiv preprint arXiv:1705.06423 [math.CO], 2017.
Seonjeong Park, Real toric manifolds and shellable posets arising from graphs, 2018.

Cf. A000108, A000245, A001622, A002421, A068875.
Row sums of triangles A319251, A319252.
gf=(1+x^2*C^2)*C^m: A000782 (m=1), this sequence (m=2), A071722 (m=3), A071723 (m=4).

a := n -> `if`(n=0, 1, 6*binomial(2*n, n-1)/(n+2));
seq(a(n), n=0..24); # Peter Luschny, Jun 28 2018

Join[{1},Table[6n CatalanNumber[n]/(n+2),{n,30}]] (* Harvey P. Dale, Jun 05 2012 *)
nn=20;t=(1-(1-4x)^(1/2))/(2x);CoefficientList[Series[D[1+x (y t -y+1)^2,y]/.y->1,{x,0,nn}],x] (* Geoffrey Critzer, Sep 16 2013 *)

{a(n) = if(n<1, n==0, 6*n*(2*n)!/(n!*(n + 1)!*(n + 2)))}; /* Michael Somos, Apr 22 2022 */

a = lambda n: n*(n+1)*hypergeometric([1-n, 2-n], [4], 1) if n>0 else 1
[simplify(a(n)) for n in range(25)] # Peter Luschny, Nov 19 2014

a(n) = 6n * (2n)! / [(n+2)n!(n+1)! ], n>0. In terms of Catalan numbers (A000108), a(n) = 6n*Cat(n)/(n+2), n>0. - Ralf Stephan, Mar 11 2004
a(n) = n*(n+1)*hypergeom([1-n, 2-n], [4], 1) for n>=1. - Peter Luschny, Nov 19 2014
D-finite with recurrence -(n+2)*(n-1)*a(n) +2*n*(2*n-1)*a(n-1)=0. - R. J. Mathar, Jul 18 2017
a(n) = 2*Cat(n+1) - 2*Cat(n) = 2*A000245(n) for n>=1. - Colin Defant, Jun 27 2018
From Amiram Eldar, Mar 22 2022: (Start)
Sum_{n>=0} 1/a(n) = 23/18 + 7*Pi/(27*sqrt(3)).
Sum_{n>=0} (-1)^n/a(n) = 43/50 - 82*sqrt(5)*log(phi)/375, where phi is the golden ratio (A001622). (End)
From Michael Somos, Apr 22 2022: (Start)
G.f.: (1 - 3*x + x^2 - (1 - x) * sqrt(1 - 4*x))/x^2.
G.f.: (2 - 2*x + x^2)/(1 - 3*x + x^2 + (1 - x)*sqrt(1 - 4*x)).
G.f.: 1 + 1/((1 - x)/(1 - sqrt(1 - 4*x)) - 1/2).
a(n) = b(n+1) - b(n) for all n in Z if b(0) = 2, b(-1) = -1, a(0) = 0, a(-1) = 3, a(-2) = -1 where b = A068875.
0 = a(n)*(+16*a(n+1) -58*a(n+2) +18*a(n+3)) +a(n+1)*(+18*a(n+1) +15*a(n+2) -13*a(n+3)) +a(n+2)*(+3*a(n+2) +a(n+3)) for all n in Z if a(0) = 0, a(-1) = 3, a(-2) = -1. (End)

A071722 Expansion of (1+x^2C^2)C^3, where C = (1-(1-4x)^(1/2))/(2x) is g.f. for Catalan numbers, A000108.

Original entry on oeis.org

1, 3, 10, 33, 110, 372, 1276, 4433, 15574, 55250, 197676, 712538, 2585292, 9434830, 34610400, 127553745, 472055910, 1753616370, 6536826780, 24443315550, 91664179620, 344655239760, 1299052403688, 4907335827258, 18576824685820

Offset: 0

N. J. A. Sloane, Jun 06 2002

nonn

gf=(1+x^2*C^2)*C^m: A000782 (m=1), A071721 (m=2), this sequence (m=3), A071723 (m=4).

Cf. A000108.

a := n -> (17*n^2 + 13*n + 6)*binomial(2*n, n)/((n + 1)*(n + 2)*(n + 3)): seq(a(n), n = 0..24);  # Peter Luschny, Dec 01 2024

a(n):=(3*binomial(2*n+2,n)+5*binomial(2*n,n+2))/(n+3); makelist(a(n),n,0,50);
/* Tani Akinari, Dec 01 2024 */

Conjecture: 2*(n+3)*a(n) + 4*(-3*n-4)*a(n-1) + (17*n-9)*a(n-2) + 2*(-2*n+5)*a(n-3) = 0. - R. J. Mathar, Aug 25 2013

a(n) = (3*binomial(2*n+2, n) + 5*binomial(2*n, n+2))/(n + 3). - Tani Akinari, Dec 01 2024

A071723 Expansion of (1+x^2C^2)C^4, where C = (1-(1-4x)^(1/2))/(2x) is g.f. for Catalan numbers, A000108.

Original entry on oeis.org

1, 4, 15, 54, 192, 682, 2431, 8710, 31382, 113696, 414086, 1515516, 5571750, 20569590, 76228095, 283481670, 1057628550, 3957577800, 14849601090, 55859886420, 210622646520, 795898303668, 3013646759910, 11432740177564, 43448822603452, 165396657221152

Offset: 0

N. J. A. Sloane, Jun 06 2002

nonn

gf=(1+x^2*C^2)*C^m: A000782 (m=1), A071721 (m=2), A071722 (m=3), this sequence (m=4).

Cf. A000108.

a := n -> (2*(2*n + 1)*(11*n^2 + 17*n + 12)*binomial(2*n, n))/((n + 1)*(n + 2)*(n + 3)*(n + 4)): seq(a(n), n = 0..25); # Peter Luschny, Dec 01 2024

a(n):=sum((k+1)*(k^2+k+1)*binomial(2*n-k,n),k,0,n)/(n+1); /* Vladimir Kruchinin, Sep 28 2011 */

a(n):=(4*binomial(2*n+3,n)+6*binomial(2*n+1,n+3))/(n+4); /* Tani Akinari, Dec 01 2024 */

a(n) = (Sum_{k=0..n} (k+1)*(k^2+k+1)*binomial(2*n-k,n))/(n+1). - Vladimir Kruchinin, Sep 28 2011
a(n) = (4*binomial(2*n+3,n)+6*binomial(2*n+1,n+3))/(n+4). - Tani Akinari, Dec 01 2024
D-finite with recurrence 2*(n+4)*a(n) +2*(-7*n-16)*a(n-1) +3*(9*n+4)*a(n-2) +6*(-2*n+3)*a(n-3)=0. - R. J. Mathar, Jul 13 2025

A000781 a(n) = 3*Catalan(n) - Catalan(n-1) - 1.

Original entry on oeis.org

1, 4, 12, 36, 111, 353, 1154, 3860, 13155, 45525, 159561, 565249, 2020687, 7280419, 26410094, 96378164, 353576699, 1303271309, 4824150869, 17925098069, 66834680639, 249981423899, 937696277309, 3526652828321, 13295935057031, 50240112815003

Offset: 1

N. J. A. Sloane

nonn

John Cerkan, Table of n, a(n) for n = 1..1657
J. R. Stembridge, Some combinatorial aspects of reduced words in finite Coxeter groups, Trans. Amer. Math. Soc. 349 (1997), no. 4, 1285-1332.

Cf. A000108, A000782.

3#[[2]]-#[[1]]-1&/@Partition[CatalanNumber[Range[0,30]],2,1] (* Harvey P. Dale, Apr 28 2013 *)

G.f.: (1/2)*(((sqrt(1-4*x)-7)*x - 3*sqrt(1-4*x) + 3)/x^2 + 2/(x-1)). - Harvey P. Dale, Apr 28 2013

Conjecture: 3*(n+1)*a(n) + (-19*n+7)*a(n-1) + (33*n-53)*a(n-2) + (-21*n+61)*a(n-3) + 2*(2*n-9)*a(n-4) = 0. - R. J. Mathar, Aug 20 2013

A061557 a(n) = (7n+2)C(n)/(n+2), where C(n) is the n-th Catalan number.

Original entry on oeis.org

3, 8, 23, 70, 222, 726, 2431, 8294, 28730, 100776, 357238, 1277788, 4605980, 16715250, 61020495, 223931910, 825632610, 3056887680, 11360977650, 42368413620, 158498860260, 594636663660, 2236748680998, 8433988655580

Offset: 1

Darko Marinov (marinov(AT)lcs.mit.edu), May 17 2001

The identity a(n) = Sum_{k = 0..n} 3*(k-1)*C(k)*C(n-k)/(2*k-1) was verified using the Wilf-Zeilberger theory for hypergeometric sums. The sum arises in the enumeration of separable 1324-avoiding permutations: A026009(n) = a(n)/2 + 2*C(n-1) - 5*C(n)/2.

a(n) = 2*C(n+1) - C(n), with C(n) = A000108(n). - Ralf Stephan, Jan 13 2004

Cf. A000108, A026009.

A000782 shifted left.

A071735 Expansion of (1+x^3C^3)C^2, where C = (1-(1-4x)^(1/2))/(2x) is g.f. for Catalan numbers, A000108.

Original entry on oeis.org

1, 2, 5, 15, 47, 152, 504, 1705, 5863, 20436, 72046, 256462, 920550, 3328192, 12109270, 44305245, 162911415, 601700700, 2231255070, 8304089970, 31007435970, 116130446640, 436137803400, 1642112017338, 6197239974582, 23438771087272, 88826989017004, 337262603824860

Offset: 0

N. J. A. Sloane, Jun 06 2002

nonn

First differences of A000782.

a(n):=if n=0 then 1 else (2*binomial(2*n+1,n)+5*binomial(2*n-2,n+1))/(n+2); makelist(a(n),n,0,20);  /* Tani Akinari, Jul 24 2025 */

a(n) = (2*binomial(2*n+1,n)+5*binomial(2*n-2,n+1))/(n+2) for n>0. - Tani Akinari, Jul 24 2025

A352700 G.f.: Sum_{n>=0} binomial((n+1)(2n+1),n)/(2n+1) x^n / C(x)^(n(2n+1)+1), where C(x) = 1 + x*C(x)^2 is the Catalan function (A000108).

Original entry on oeis.org

1, 1, 12, 239, 7178, 296092, 15666162, 1014796995, 77899495174, 6919858148750, 698584345392968, 79022119891573410, 9902447587480555624, 1361894352334815968554, 203969111022547680433454, 33047362680815865252524643, 5759708920548423261284008230

Offset: 0

Paul D. Hanna, Mar 29 2022

nonn

Compare g.f. to: 1 = Sum_{n>=0} binomial((k+1)*(2*n+1),n)/(2*n+1) * x^n / C(x)^(k*(2*n+1)+1) which holds for fixed k, where C(x) = 1 + x*C(x)^2 is the Catalan function (A000108).
The g.f. A(x) seems to satisfy A(x)^3 = A(x^3) (mod 3); compare this to the congruence: C(x)^3 = C(x^3) (mod 3), where C(x) is the Catalan function.
Odd terms seem to occur only at positions 2^n-1 for n >= 0.
Conjectures: given g.f. A(x), let C(x) = (1 - sqrt(1-4*x))/(2*x) be the Catalan power series (A000108), then
(1) A(x)^3 = A(x^3) (mod 3),
(2) A(x) = C(x) + x^2*C(x)^3 (mod 3) = (2 - x)*C(x) - 1 (mod 3),
(3) A(x) = C(x) (mod 2),
(4) a(n) = binomial(2*n+1,n)/(2*n+1) + 3*binomial(2*n-1,n-2)/(2*n-1) (mod 3) for n >= 0,
(5) a(n) = 2*A000108(n) - A000108(n-1)  (mod 3) for n >= 1,
(6) a(n) = A000108(n) (mod 2) for n >= 0.

			G.f.: A(x) = 1 + x + 12*x^2 + 239*x^3 + 7178*x^4 + 296092*x^5 + 15666162*x^6 + 1014796995*x^7 + 77899495174*x^8 + 6919858148750*x^9 + ...
where
A(x) = 1/C(x) + 2*x/C(x)^4 + 21*x^2/C(x)^11 + 468*x^3/C(x)^22 + 16555*x^4/C(x)^37 + 812448*x^5/C(x)^56 + 51274146*x^6/C(x)^79 + 3965837928*x^7/C(x)^106 + ... + (n+1)*A299429(n)*x^n/C(x)^(n*(2*n+1)+1) + ...
and
C(x) = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 42*x^5 + 132*x^6 + 429*x^7 + 1430*x^8 + 4862*x^9 + ... + A000108(n)*x^n + ...
Congruence modulo 3.
(1) It appears that A(x)^3 is congruent to A(x^3) modulo 3, where
A(x)^3 = 1 + 3*x + 39*x^2 + 790*x^3 + 23436*x^4 + 949701*x^5 + 49503687*x^6 + 3171679536*x^7 + 241578165750*x^8 + 21340270771814*x^9 + ...
and
(A(x)^3 - A(x^3))/3 = x + 13*x^2 + 263*x^3 + 7812*x^4 + 316567*x^5 + 16501225*x^6 + 1057226512*x^7 + 80526055250*x^8 + 7113423590525*x^9 + ...
(2) Also, g.f. A(x) seems to be congruent to C(x) + x^2*C(x)^3, where
C(x) + x^2*C(x)^3 = 1 + x + 3*x^2 + 8*x^3 + 23*x^4 + 70*x^5 + 222*x^6 + 726*x^7 + 2431*x^8 + 8294*x^9 + ... + (C(2*n,n)/(n+1) + C(2*n-1,n-2)*3/(2*n-1))*x^n + ...

Cf. A298696, A299429, A000108, A000782.

{a(n) = my(C = (1 - sqrt(1-4*x +O(x^(n+3))))/(2*x),
A = sum(m=0,n, binomial((m+1)*(2*m+1),m)/(2*m+1) * x^m/C^(m*(2*m+1)+1))); polcoeff(A,n)}
for(n=0,20,print1(a(n),", "))

G.f. A(x) satisfies:
(1) A(x-x^2) = Sum_{n>=0} binomial((n+1)*(2*n+1),n)/(2*n+1) * (x/(1-x))^n * (1-x)^((n+1)*(2*n+1)).
(2) A(x/(1+x)^2) = Sum_{n>=0} binomial((n+1)*(2*n+1),n)/(2*n+1) * x^n / (1+x)^((n+1)*(2*n+1)).

cp's OEIS Frontend

A215512 a(n) = 5*a(n-1) - 6*a(n-2) + a(n-3), with a(0)=1, a(1)=3, a(2)=8.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A071721 Expansion of (1+x^2*C^2)*C^2, where C = (1-(1-4*x)^(1/2))/(2*x) is g.f. for Catalan numbers, A000108.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

A071722 Expansion of (1+x^2*C^2)*C^3, where C = (1-(1-4*x)^(1/2))/(2*x) is g.f. for Catalan numbers, A000108.

Views

Author

Keywords

Crossrefs

Programs

Maple

Maxima

Formula

A071723 Expansion of (1+x^2*C^2)*C^4, where C = (1-(1-4*x)^(1/2))/(2*x) is g.f. for Catalan numbers, A000108.

Views

Author

Keywords

Crossrefs

Programs

Maple

Maxima

Maxima

Formula

A000781 a(n) = 3*Catalan(n) - Catalan(n-1) - 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A061557 a(n) = (7*n+2)*C(n)/(n+2), where C(n) is the n-th Catalan number.

Views

Author

Keywords

Comments

Crossrefs

A071735 Expansion of (1+x^3*C^3)*C^2, where C = (1-(1-4*x)^(1/2))/(2*x) is g.f. for Catalan numbers, A000108.

Views

Author

Keywords

Crossrefs

Programs

Maxima

Formula

A352700 G.f.: Sum_{n>=0} binomial((n+1)*(2*n+1),n)/(2*n+1) * x^n / C(x)^(n*(2*n+1)+1), where C(x) = 1 + x*C(x)^2 is the Catalan function (A000108).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A215512 a(n) = 5a(n-1) - 6a(n-2) + a(n-3), with a(0)=1, a(1)=3, a(2)=8.

A071721 Expansion of (1+x^2C^2)C^2, where C = (1-(1-4x)^(1/2))/(2x) is g.f. for Catalan numbers, A000108.

A071722 Expansion of (1+x^2C^2)C^3, where C = (1-(1-4x)^(1/2))/(2x) is g.f. for Catalan numbers, A000108.

A071723 Expansion of (1+x^2C^2)C^4, where C = (1-(1-4x)^(1/2))/(2x) is g.f. for Catalan numbers, A000108.

A061557 a(n) = (7n+2)C(n)/(n+2), where C(n) is the n-th Catalan number.

A071735 Expansion of (1+x^3C^3)C^2, where C = (1-(1-4x)^(1/2))/(2x) is g.f. for Catalan numbers, A000108.

A352700 G.f.: Sum_{n>=0} binomial((n+1)(2n+1),n)/(2n+1) x^n / C(x)^(n(2n+1)+1), where C(x) = 1 + x*C(x)^2 is the Catalan function (A000108).