A157161 Formal infinite product representation for the Catalan numbers (A000108) o.g.f. series.

1, 2, 3, 11, 25, 79, 245, 869, 2692, 9544, 32065, 115381, 400023, 1462730, 5165327, 19165035, 68635477, 255546242, 930138521, 3491772737, 12810761323, 48334512920, 178987624513, 678272753284, 2528210175630, 9616904064021, 36047930953482, 137654448221760, 518401146543811

Offset: 1

Author

Wolfdieter Lang Aug 10 2009

Keywords

• nonn
• easy

Comments

(1-sqrt(1-4*x))/(2*x) = Sum_{k>=0} C(k)*x^k with C(n)=A000108(n) written as formal Product_{n>=1} (1 + a(n)*x^n).

Examples

			Recurrence I: a(4) = C(4) - a(1)*a(3) = 14 - 1*3 = 11.
Recurrence II: a(4)= 2*(-1)^2 + (1*C(4)-(1/2)*(2*C(1)*C(3) + 1*C(2)^2) + (1/3)*3*C(1)^2*C(2)) = 2 + (14 - (10+4)/2 + 2) = 11.
Recurrence II (rewritten): a(4)= (1/4)*(-a(1))^4 + (1/2)*(-a(2))^2 + 7!/4!^2 = 11.
		

Links

• W. Lang: Two recurrences for the general problem.

Crossrefs

Cf. A147542 (for Fibonacci numbers).

Formula

Product_{n>=1} (1 + a(n)*x^n) = Sum_{k>=1} C(k)*x^k = (1-sqrt(1-4*x))/(2*x), with C(n)= A000108(n) (Catalan numbers).

Recurrence I: With FP(n,m) the set of partitions of n with m distinct parts (which could be called fermionic partitions (fp)):

a(n)= C(n) - sum(sum(product(a(k[j]),j=1..m), fp from FP(n,m)), m=2..maxm(n)), with maxm(n):=A003056(n) and the distinct parts k[j], j=1,...,m, of the partition fp of n, n>=3. Inputs a(1)=C(1)=1, a(2)=C(2)=2. See the array A008289(n,m) for the cardinality of the set FP(n,m).

Recurrence II: With P(n,m) the set of all partitions of n with m parts, and the multinomial numbers M0 (given for every partition under A048996):

a(n) = sum((d/n)*(-a(d)^(n/d)),d|n with 1=2; a(1)=C(1)=1. The exponents e(j)>=0 satisfy sum(j*e(j),j=1..n)=n and sum(e(j),j=1..m). If e_j=0 then part j does not appear. The M0 numbers are m!/product(e(j)!,j=1..n).

Recurrence II (rewritten, thanks to email from V. Jovovic, Mar 10 2009):

a(n)= (sum((d/n)*(-a(d))^(n/d),d|n with 1<=d=2; a(1)=1. Note that n*(2*n-1)!/n!^2 = A001700(n-1)= A088218(n), n>=1, with o.g.f. (d/dx)log(c(x)), where c(x) is the o.g.f. for Catalan numbers A000108. Here no partitions are needed.