login
A226022
A modified version of Catalan numbers.
5
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,3
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.
LINKS
N. J. Lord, Non-associative operations, Mathematics Magazine 60:3 (1987), pp. 174-177.
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
EXAMPLE
a(0)=A000108(0), a(1)=A000108(1), a(2)=A000108(2), a(3)=A000108(3)-1.
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 *)
PROG
(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), ", "))
CROSSREFS
Cf. A000108.
Sequence in context: A149841 A149842 A149843 * A272463 A217699 A291190
KEYWORD
nonn,easy
AUTHOR
Ellen Ziliak, May 23 2013
STATUS
approved