A026012 Second differences of Catalan numbers A000108.

1, 2, 6, 19, 62, 207, 704, 2431, 8502, 30056, 107236, 385662, 1396652, 5088865, 18642420, 68624295, 253706790, 941630580, 3507232740, 13105289370, 49114150020, 184560753390, 695267483664, 2625197720454, 9933364416572, 37660791173152, 143048202990504

Offset: 0

Author

N. J. A. Sloane, Clark Kimberling

Keywords

• nonn
• changed

Comments

Number of (s(0), s(1), ..., s(n)) such that s(i) is a nonnegative integer and |s(i) - s(i-1)| = 1 for i = 1,2,...,n, s(0) = s(2n) = 2.

Number of Dyck paths of semilength n+2 with no initial and no final UD's. Example: a(2)=6 because the only Dyck paths of semilength 4 with no initial and no final UD's are UUDUDUDD, UUDUUDDD, UUUDDUDD, UUUDUDDD, UUDDUUDD, UUUUDDDD. - Emeric Deutsch, Oct 26 2003

Number of branches of length 1 starting from the root in all ordered trees with n+1 edges. Example: a(1)=2 because the tree /\ has two branches of length 1 starting from the root and the path-tree of length 2 has none. a(n) = Sum_{k=0..n+1} (k*A127158(n+1,k)). - Emeric Deutsch, Mar 01 2007

Number of staircase walks from (0,0) to (n,n) that never cross y=x+2. Example: a(3) = 19 because up,up,up,right,right,right is not allowed but the other binomial(6,3)-1 = 19 paths are. - Mark Spindler, Nov 11 2012

Number of standard Young tableaux of skew shape (n+2,n)/(2), for n>=2. - Ran Pan, Apr 07 2015

References

• S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see pp. 188, 196).

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.
• Reinis Cirpons, James East, and James D. Mitchell, Transformation representations of diagram monoids, arXiv:2411.14693 [math.RA], 2024. See pp. 3, 33.
• Ryota Inagaki, Tanya Khovanova, and Austin Luo, On Chip-Firing on Undirected Binary Trees, Ann. Comb. (2025). See p. 15.
• Jocelyn Quaintance and Harris Kwong, A combinatorial interpretation of the Catalan and Bell number difference tables, Integers, 13 (2013), #A29.
• Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2.

Crossrefs

T(2n, n), where T is the array defined in A026009.

Cf. A000108, A000245, A000344, A039599, A059346, A127158, A342912.

Programs

Mathematica

Differences[Table[CatalanNumber[n], {n, 0, 28}], 2] (* Jean-François Alcover, Sep 28 2012 *)
Table[Binomial[2n,n]-Binomial[2n,n-3],{n,0,26}] (* Mark Spindler, Nov 11 2012 *)

PARI

a(n) = 3*(3*n^2+3*n+2)*binomial(2*n, n)/((n+1)*(n+2)*(n+3)); /* Joerg Arndt, Aug 19 2012 */

Formula

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

a(n) = 3*(3*n^2+3*n+2)*binomial(2*n, n)/((n+1)*(n+2)*(n+3)). - Emeric Deutsch, Oct 26 2003

a(n) = Sum_{k=0..2} A039599(n,k) = A000108(n) + A000245(n) + A000344(n). - Philippe Deléham, Nov 12 2008

a(n) = binomial(2*n,n)/(n+1)*hypergeom([-2,n+1/2],[n+2],4). - Peter Luschny, Aug 15 2012

a(n) = binomial(2*n,n) - binomial(2n,n-3). - Mark Spindler, Nov 11 2012

D-finite with recurrence (n+3)*a(n) + (-5*n-6)*a(n-1) + 2*(2*n-3)*a(n-2) = 0. - R. J. Mathar, Jun 20 2013

E.g.f.: exp(2*x)*(BesselI(0,2*x) - BesselI(3,2*x)). - Ilya Gutkovskiy, Feb 28 2017

Sum_{n>=0} a(n)/4^n = 6. - Amiram Eldar, Jul 10 2023

a(n) = C(n+2)+C(n)-2*C(n+1), C = A000108. - Alois P. Heinz, Apr 02 2025

Binomial transform of A342912. - Mélika Tebni, Apr 05 2025