|
| |
|
|
A157161
|
|
Formal infinite product representation for the Catalan numbers (A000108) o.g.f. series.
|
|
2
|
|
|
|
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
|
|
|
|
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).
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
