OFFSET
0,3
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
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.
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)
a(n) ~ 2^(4*n-7/2) * n^(n-1) / exp(n). - Amiram Eldar, Sep 30 2025
G.f.: x*2F0(1/2,1;;16*x). - R. J. Mathar, Nov 18 2025
EXAMPLE
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
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 *)
PROG
(Magma) [0] cat [Catalan(n-1)*4^(n-1)*Factorial(n): n in [1..20]]; // Vincenzo Librandi, Mar 11 2013
(SageMath) [0]+[4^(n-1)*factorial(n)*catalan_number(n-1) for n in (1..30)] # G. C. Greubel, Apr 02 2021
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
INRIA Encyclopedia of Combinatorial Structures, Jan 25 2000
EXTENSIONS
Entry revised by N. J. A. Sloane, Feb 04 2013 and Feb 06 2013
STATUS
approved