login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A157161 Formal infinite product representation for the Catalan numbers (A000108) o.g.f. series. 1
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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).

LINKS

Table of n, a(n) for n=1..29.

W. Lang: Two recurrences for the general problem.

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<d<n) + sum(((-1)^(m-1))*(1/m)*sum(M0(p)*C(1)^e(1)*...*C(n)^e(n), p=(1^e(1),...,n^e(n)) from P(n,m)), m=1..n-1), n>=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<n) + (2*n-1)!/n!^2, n>=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.

EXAMPLE

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.

CROSSREFS

Cf. A147542 (for Fibonacci numbers).

Sequence in context: A137811 A041955 A239445 * A041811 A229066 A248161

Adjacent sequences:  A157158 A157159 A157160 * A157162 A157163 A157164

KEYWORD

nonn,easy

AUTHOR

Wolfdieter Lang Aug 10 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 25 13:31 EDT 2019. Contains 322461 sequences. (Running on oeis4.)