Some computations with the Catalan generating function.

*Requirements: Internet access (partially)*

In [1]:

```
# 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)
```

Out[1]:

In [2]:

```
# 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)
```

Out[2]:

In [3]:

```
# 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)
```

In [4]:

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

Out[4]:

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

In [5]:

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

Out[5]:

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

In [6]:

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

Out[6]:

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

In [0]:

```
```

In [0]:

```
```

In [0]:

```
```

In [0]:

```
```