A226022 A modified version of Catalan numbers.

1, 1, 2, 4, 12, 36, 112, 360, 1184, 3968, 13504, 46544, 162144, 570016, 2019648, 7204864, 25856896, 93288576, 338167296, 1231045376, 4498577408, 16496039936, 60681046016, 223860786432, 828040881664, 3070320123392

Offset: 0

Author

Ellen Ziliak, May 23 2013

Keywords

• nonn
• easy

Comments

This sequence arose when looking for an upper bound on the number of parenthesis schemes assuming that schemes of length 4 have exactly two schemes which are equal. The most common example would be working with subtraction. When you subtract ((a-(b-c))-d) is equal to (a-(b-(c-d))) so if you count unique parenthesis schemes then for length 4 you would have one less than the Catalan number A000108(3). This sequence counts the maximum number of parenthesis schemes you can have for longer words. This notion can be easily generalized to any schemes that deviate from the Catalan numbers for schemes of any length k. This is related to the depth of a quasigroup.

Examples

			a(0)=A000108(0), a(1)=A000108(1), a(2)=A000108(2), a(3)=A000108(3)-1.
		

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..1000
• N. J. Lord, Non-associative operations, Mathematics Magazine 60:3 (1987), pp. 174-177.

Crossrefs

Cf. A000108.

Programs

Mathematica

Table[Sum[(-1)^k*Binomial[n - 3 k + 1, k] CatalanNumber[n - 3 k], {k, 0, Floor[n/3]}], {n, 0, 25}] (* Michael De Vlieger, Sep 21 2017 *)

PARI

a(n)=sum(k=0,n\3,(-1)^k*binomial(n-3*k+1,k)*binomial(2*n-6*k,n-3*k)/(n-3*k+1))
for(n=0,30,print1(a(n),","))

Formula

a(n) = Sum_{k=0..floor(n/3)} (-1)^k*binomial(n-3*k+1,k)*A000108(n-3*k), where A000108(n) is the n-th Catalan number.

a(n) = Sum_{k=0..n-1} a(k)a(n-k) for n>3 just like the Catalan sequence formula.

Let A(x) be the g.f., then

(1) A(x)=1-x^3+x*A(x)^2

(2) A(x)=(1-sqrt(1-4*x+4*x^4))/(2*x)

(3) A(x)=(1-x^3)*C(x-x^4), where C(x)=1+x*C(x)^2=(1-sqrt(1-4*x))/(2*x) is the Catalan sequence.

To generalize for a operator where two parenthesis schemes of length m are the same just match the Catalan sequence for the first m-1 terms and then we would have a(m) = A000108(m)-1.

Then the generating B(x) function for this sequence would satisfy B(x)=1-x^m+x*B(x)^2 and B(x)=(1-sqrt(1+4*x^(m+1)-4*x))/(2*x).

The formula for the general sequence is b(n) = Sum_{k=0..floor(n/m)}(-1)^k*binomial(n-m*k+1,k)*A000108(n-m*k).

D-finite with recurrence (n+1)*a(n) +(n+2)*a(n-1) +(n+9)*a(n-2) +42*(-2*n+5)*a(n-3) +4*(n-5)*a(n-4) +20*(n-6)*a(n-5) +84*(n-7)*a(n-6)=0. - R. J. Mathar, May 23 2014