
# First, define z as a variable
var('z')

# Next, define the Catalan generating function
C = (1-sqrt(1-4*z))/(2*z)
show("C(z) = ", C)


# The coefficients of the power series expansion of C at the origin form the Catalan numbers
ser = C.series(z,10)
show("C(z) = ",ser)


# Search the Online Encyclopedia of Integer Sequences for sequences with this start
# Note: From here down Sage requires an internet connection
oe = oeis(ser.list())
print(oe)

0: A000108: Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).
1: A120588: G.f. is 1 + x*c(x), where c(x) is the g.f. of the Catalan numbers (A000108).
2: A211216: Expansion of (1-8*x+21*x^2-20*x^3+5*x^4)/(1-9*x+28*x^2-35*x^3+15*x^4-x^5).


# There are a few sequences where the first 10 terms appear, generating more terms narrows down the correct sequence
oe[0]

A000108: Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).


# Here are a few of the formulas for the Catalan numbers available on the OEIS
oe[0].formulas()[1:10]

0: a(n) = binomial(2*n, n) - binomial(2*n, n-1).
1: a(n) = Sum_{k=0..n-1} a(k)a(n-1-k).
2: a(n) = Product_{k=2..n} (1 + n/k), if n > 1.
3: G.f.: A(x) = (1 - sqrt(1 - 4*x)) / (2*x). G.f. A(x) satisfies A = 1 + x*A^2.
4: a(n+1) = Sum_{i} binomial(n, 2*i)*2^(n-2*i)*a(i). - Touchard
5: D-finite with recurrence: 2*(2*n-1)*a(n-1) = (n+1)*a(n).
6: It is known that a(n) is odd if and only if n=2^k-1, k=0, 1, 2, 3, ... - _Emeric Deutsch_, Aug 04 2002, corrected by _M. F. Hasler_, Nov 08 2015
7: Using the Stirling approximation in A000142 we get the asymptotic expansion a(n) ~ 4^n / (sqrt(Pi * n) * (n + 1)). - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 13 2001
8: Integral representation: a(n) = (1/(2*Pi))*Integral_{x=0..4} x^n*sqrt((4-x)/x). - _Karol A. Penson_, Apr 12 2001


# Here are a few of the examples of Catalan numbers listed on the OEIS
oe[0].comments()[1:10]

0: The solution to Schröder's first problem. A very large number of combinatorial interpretations are known - see references, esp. Stanley, Enumerative Combinatorics, Volume 2. This is probably the longest entry in the OEIS, and rightly so.
1: Number of ways to insert n pairs of parentheses in a word of n+1 letters. E.g., for n=2 there are 2 ways: ((ab)c) or (a(bc)); for n=3 there are 5 ways: ((ab)(cd)), (((ab)c)d), ((a(bc))d), (a((bc)d)), (a(b(cd))).
2: Consider all the binomial(2n,n) paths on squared paper that (i) start at (0, 0), (ii) end at (2n, 0) and (iii) at each step, either make a (+1,+1) step or a (+1,-1) step. Then the number of such paths that never go below the x-axis (Dyck paths) is C(n). [Chung-Feller]
3: Number of noncrossing partitions of the n-set. For example, of the 15 set partitions of the 4-set, only [{13},{24}] is crossing, so there are a(4)=14 noncrossing partitions of 4 elements. - _Joerg Arndt_, Jul 11 2011
4: a(n-1) is the number of ways of expressing an n-cycle in the symmetric group S_n as a product of n-1 transpositions (u_1,v_1)*(u_2,v_2)*...*(u_{n-1},v_{n-1}) where u_k <= u_j and v_k <= v_j for k < j; see example.  If the condition is dropped, one obtains A000272. - _Joerg Arndt_ and Greg Stevenson, Jul 11 2011
5: a(n) is the number of ordered rooted trees with n nodes, not including the root. See the Conway-Guy reference where these rooted ordered trees are called plane bushes. See also the Bergeron et al. reference, Example 4, p. 167. - _Wolfdieter Lang_, Aug 07 2007
6: As shown in the paper from Beineke and Pippert (1971), a(n-2)=D(n) is the number of labeled dissections of a disk, related to the number R(n)=A001761(n-2) of labeled planar 2-trees having n vertices and rooted at a given exterior edge, by the formula D(n)=R(n)/(n-2)!. - _M. F. Hasler_, Feb 22 2012
7: Shifts one place left when convolved with itself.
8: For n >= 1 a(n) is also the number of rooted bicolored unicellular maps of genus 0 on n edges. - Ahmed Fares (ahmedfares(AT)my-deja.com), Aug 15 2001

Example 1.2 (The Catalan Generating Function)¶