A052734 a(n) = 4^(n-1) * n! * Catalan(n-1) for n > 0, with a(0) = 0.

0, 1, 8, 192, 7680, 430080, 30965760, 2724986880, 283398635520, 34007836262400, 4625065731686400, 703009991216332800, 118105678524343910400, 21731444848479279513600, 4346288969695855902720000, 938798417454304874987520000, 217801232849398730997104640000, 54014705746650885287281950720000, 14259882317115833715842434990080000

Offset: 0

Author

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Keywords

• easy
• nonn

Comments

For n>0, the number of fully-parenthesized expressions that you can form with n operands and 4 types of binary operators. - Yogy Namara (yogy.namara(AT)gmail.com), Mar 07 2010

a(n+1) is the number of square roots of any permutation in S_{16*n} whose disjoint cycle decomposition consists of 2*n cycles of length 8. - Luis Manuel Rivera Martínez, Feb 26 2015

Examples

			Let's say the 4 types of binary operators are +, -, *, and /. Then, with 3 operands {a, b, c}, we can form expressions such as ((b+a)/c), (a-(c-b)), (c*(b+a)), etc. There are a(3)=192 such expressions. - Yogy Namara (yogy.namara(AT)gmail.com), Mar 07 2010
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 690.
• Jesús Leaños, Rutilo Moreno and Luis Manuel Rivera-Martínez, On the number of mth roots of permutations, arXiv:1005.1531 [math.CO], 2010-2011.
• Jesús Leaños, Rutilo Moreno and Luis Manuel Rivera-Martínez, On the number of mth roots of permutations, Australas. J. Combin., Vol. 52 (2012), pp. 41-54 (Theorem 1).
• W. van der Aalst, J. Buijs and B. van Dongen, Towards Improving the Representational Bias of Process Mining, 2012.

Crossrefs

Sequences of the form m^(n-1)*n!*Catalan(n-1): A001813 (m=1), A052714 (or A144828) (m=2), A221954 (m=3), this sequence (m=4), A221953 (m=5), A221955 (m=6).

Equal to A000108 if all operands and all operators are indistinguishable.

Programs

Magma

[0] cat [Catalan(n-1)*4^(n-1)*Factorial(n): n in [1..20]]; // Vincenzo Librandi, Mar 11 2013

Maple

spec := [S,{B=Prod(C,C),S=Union(B,Z),C=Union(B,S,Z)},labeled]: seq(combstruct[count](spec,size=n), n=0..20);
seq((2*n)!/n! * 4^n, n = 0..10);

Mathematica

Join[{0}, Table[CatalanNumber[n-1] 4^(n-1) n!, {n, 1, 20}]] (* Vincenzo Librandi, Mar 11 2013 *)

Sage

[0]+[4^(n-1)*factorial(n)*catalan_number(n-1) for n in (1..30)] # G. C. Greubel, Apr 02 2021

Formula

E.g.f.: (1 - sqrt(1-16*x))/8.

Recurrence: a(1)=1, 8*(1 - 2*n)*a(n) + a(n+1) = 0.

a(n) = 16^n*Gamma(n+1/2)/sqrt(Pi).

a(0) = 0, a(1) = 1; a(n) = 4 * Sum_{k=1..n-1} binomial(n,k) * a(k) * a(n-k). - Ilya Gutkovskiy, Jul 09 2020

From Amiram Eldar, Jan 08 2022: (Start)

Sum_{n>=1} 1/a(n) = 1 + e^(1/16)*sqrt(Pi)*erf(1/4)/4, where erf is the error function.

Sum_{n>=1} (-1)^(n+1)/a(n) = 1 - e^(-1/16)*sqrt(Pi)*erfi(1/4)/4, where erfi is the imaginary error function. (End)

Extensions

Entry revised by N. J. A. Sloane, Feb 04 2013 and Feb 06 2013