J Labs

Catalan Numbers

(1 of 24) Introduction

Catalan numbers appear in several areas of mathematics. For example, the nth Catalan number is the number of planar binary trees with n nodes, and is the number of ways of cutting up a polygon with n+2 sides into triangles by drawing non-intersecting diagonals.

Catalan numbers 0-8 are: 1 1 2 5 14 42 132 429 1430

The question we will look at here is how to calculate the nth Catalan number, for n taking values of 5, 10, 1000, 10000 and up.

(2 of 24) Basic Formula

The formula in conventional math notation is:

A direct translation of the formula into J is given below, evaluated for n=5. Note that the factorial function is written !n

(3 of 24) Basic Formula (ctd)

For a more efficient solution, rewrite the formula as:

and note that the first expression is the number of ways of choosing n things from 2n, which in J is the binomial coefficent: n!2*n

(4 of 24) Basic Formula (ctd)

A direct translation of this formula into J is:

(5 of 24) Basic Formula (ctd)

This can be simplified using +: (double) and >: (increment) as follows:

(6 of 24) Basic Formula (ctd)

Try this with other values for n:

(7 of 24) First Solution

We can now define our first Catalan verb, by removing references to the argument n in the expression:

```(n ! +: n) % >: n```

and assigning the result to cat1.

(8 of 24) First Solution (ctd)

To display a table of numbers, join n with cat1 n, as below:

(9 of 24) First Solution (ctd)

Lets now try this with n=100. This results in a big number that exceeds the standard integer representation.

To calculate it accurately, use x: to convert the argument to an extended integer.

(10 of 24) Second Solution

This suggests a new verb cat2, which applies x: followed by cat1.

(11 of 24) Second Solution (ctd)

The 1,000th catalan number has 598 digits:

(12 of 24) Second Solution (ctd)

This can be formatted using the xfmt (extended format) utility:

(13 of 24) Second Solution (ctd)

Can cat2 be used to generate the 10,000th Catalan number?

Yes - with a fast PC and enough memory. On the authors PC, this calculation takes just under a second and results in a number with 6,015 digits. However, it is near the limit of what can be achieved using this simple formula. If you try this, you might find that your PC runs out of memory, and starts paging memory to hard disk. This slows the calculation down enormously, and should be avoided.

(14 of 24) Third Solution

It turns out that you can calculate !n by calculating the exponents in !n of each prime up to n, and this leads to a more efficient technique for computing the Catalan numbers where n is very large.

The idea is that for each prime p up to n, you calculate a list, lp, of the prime powers of p up to n, and then the exponent of p in !n is given by:

```+/ <. n % lp```

To keep numbers small, We will illustrate this for the calculation of !100.

(15 of 24) Third Solution (ctd)

For any prime p, the maximum power of p less than or equal to n is:

```<. p ^. n```

For example, the maximum power of 3 less than or equal to 100 is 4, and the corresponding maximum power of 7 is 2:

(16 of 24) Third Solution (ctd)

The exponent of p in !n is then:

```+/ <. n % p ^ >: i. <. p ^. n```

For example:

(17 of 24) Third Solution (ctd)

As confirmation, note that 3^48 evenly divides !100, but 3^49 does not:

(18 of 24) Third Solution (ctd)

The formula for each prime used (as above) is:

```+/ <. n % p ^ >: i. <. p ^. n```

Since n may be an extended integer, we rewrite this to avoid floating point results as:

```+/ n <.@% p ^ >: i. p <.@^. n```

and define a corresponding verb pexp:

(19 of 24) Third Solution (ctd)

The list of primes less than or equal to n can be found using the inverse of p: the prime-producing verb.

Define a verb, ple, to produce this list.

(20 of 24) Third Solution (ctd)

The exponents of each prime p in !n are then given by:

```(ple n) pexp"0 n```

Rank 0 is used to evaluate pexp on each prime in the left argument, rather than the list of primes as a whole.

(21 of 24) Third Solution (ctd)

The calculation of:

can now be done by calculating the exponents of the numerator less the exponents of the denominator, for each prime up to 2n, then taking the product of the prime powers.

(22 of 24) Third Solution (ctd)

Therefore we define cat3 as below, and check it matches cat2:

(23 of 24) Third Solution (ctd)

cat3 can be used to calculate the 10,000th Catalan number.

You can try larger numbers, but be warned this may take a long time, or run out of memory. On the PC of the author, cat3 100,000 takes just under 1 second and returns a result with 60,199 digits.

The next section calculates cat3 10000.

(24 of 24) Third Solution (ctd)

To see the answer in full, enter:

```xfmt a```

End of Lab