Catalan Numbers

September 12, 2017

I wouldn’t get the job. The first thing I thought of was 2n − 1, but I quickly realized that was wrong. Then I set about drawing the first few sets of search trees, and realized I wasn’t getting anywhere. Then I looked at the answer:

(define (choose n k) ; binomial theorem
  (if (zero? k) 1
    (* n (/ k) (choose (- n 1) (- k 1)))))
(define (catalan n)
  (if (zero? n) 1
    (- (choose (+ n n) n) (choose (+ n n) (- n 1)))))

If you don’t like to compute those huge factorials, you can instead perform a dynamic programming calculation, using define-memoized from a previous exercise:

(define-memoized (catalan n)
  (if (zero? n) 1
    (let loop ((i 1) (count 0))
      (if (< n i) count
        (loop (+ i 1) (+ count (* (catalan (- i 1))
                                  (catalan (- n i)))))))))

The number of unique binary search trees that can be made from the integers from 1 to n is (catalan n), and it grows at a phenomally high rate:

> (do ((i 0 (+ i 1))) ((< 30 i))
    (display i) (display #\tab)
    (display (catalan i)) (newline))
0       1
1       1
2       2
3       5
4       14
5       42
6       132
7       429
8       1430
9       4862
10      16796
11      58786
12      208012
13      742900
14      2674440
15      9694845
16      35357670
17      129644790
18      477638700
19      1767263190
20      6564120420
21      24466267020
22      91482563640
23      343059613650
24      1289904147324
25      4861946401452
26      18367353072152
27      69533550916004
28      263747951750360
29      1002242216651368
30      3814986502092304

You can run the program at https://ideone.com/KM5smO.

Although I didn’t know it, Catalan numbers are ubiquitous in combinatorics; Sloane says “This is probably the longest entry in the OEIS, and rightly so.” Go to A000108 to look at it yourself.

I would be astonished at the candidate who answered that correctly.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
7 Comments »

7 Responses to “Catalan Numbers”

  1. James Curtis-Smith said
    September 12, 2017 at 9:19 AM

    Came up with the solution below… after looking at the graphs realised that

    Tn = Sum (0..n-1) T[i] T[n-i-1]
    {where T[0] = 1, T[1] = 1}

    e,g,
    T2 = T0T1 + T1T0
    T3 = T1T2 + T1T1 + T2T0
    …

    Then came up with the following solution…

    my $N = shift;
my @T = (1,1);

foreach my $t (2..$N) {
  my $x = 0;
  $x += $T[$_] * $T[$t-$_-1] foreach 0 .. $t-1;
  push @T, $x;
}
shift @T;

print join "\n", q(), @T, q(),q();
  2. Paul said
    September 12, 2017 at 11:51 AM

    A dynamic solution in Python (same method as @James Curtis-Smith). For n elements, you can split the range by taking out 1 element (the split). Then you have a number of elements at the left and a number on the right, so you can reduce the problem if you have calculated all case smaller than n already.

    def ntrees():
    table = [1]
    yield from table
    for k in count(1):
        table.append(sum(table[split] * table[k-1-split] for split in range(k)))
        yield table[-1]
  3. James Curtis-Smith said
    September 12, 2017 at 12:46 PM

    Forgot to say – the logic to the calculation is that you chose each element in turn for the fist element – other elements are either smaller larger than the current element {assuming no dupes}. We set the node as root and work out what trees are to the left or right…

    Smallest element:0 element tree to left : (n-1)-element tree to right – count is therefore T0 * T(n-1)
    Next element:1 element tree to left : (n-2)-element tree to right
    …
    Next element:(n-1) element tree to left : 0 element tree to right- count is therefore T(n-1) * T0

  5. chaw said
    September 12, 2017 at 5:16 PM

    Once we map the problem to Catalan numbers (the title gives it away!)
    the main challenge may be calculating those numbers. The sample
    solution by @programmingpraxis works for modest values of n but for
    much larger values we can use the following, in standard (R7RS)
    Scheme. It runs in a few seconds with Larceny Scheme on my very modest
    computer.

    (import (scheme base)
        (scheme write))

(define (n-choose-k/cps n k return)
  (if (zero? k)
      (return 1) 
      (n-choose-k/cps (- n 1)
                      (- k 1)
                      (lambda (result)
                        (return (* n
                                   (/ result k)))))))

(define (n-choose-k n k)
  (call-with-current-continuation
   (lambda (cont)
     (n-choose-k/cps n k cont))))

(define (cat-num n)
  (- (n-choose-k (* 2 n)
                 n)
     (n-choose-k (* 2 n)
                 (+ n 1))))

(display  (cat-num 10000))
(newline)

  6. Paul said
    September 13, 2017 at 8:20 AM

    A very fast way to calcuate Catalan numbers and a more elegant version of my earlier solution.

    def dotproduct(vec1, vec2):
    return sum(map(mul, vec1, vec2))

def ntrees():
    table = [1]
    yield 1  # for n=0
    while True:
        table.append(dotproduct(table, reversed(table)))
        yield table[-1]

def catalan_g():
    'very fast way to calculate Catalan numbers'
    yield from (0, 1)
    c = 1
    for n in count(1):
        c = c * 2 * (2*n + 1) // (n + 2)
        yield c
  7. Catalan’s Triangle | Programming Praxis said
    September 19, 2017 at 9:00 AM

    […] our exercise a week ago, I’ve been reading about Catalan numbers, primarily based on the references at […]

Leave a comment