Fifty Shades of J/Chapter 44
Table of Contents ... Glossary ... Previous Chapter ... Next Chapter
Principal Topics
- Catalan numbers, permutations, combinations, Manhattan diagram, binary trees
The Catalan numbers, although not as universally well-known as the Fibonacci sequence, arise in a surprisingly disparate number of counting situations. They have nothing to do with Catalonia – they were known to the Chinese, but first discovered in Europe by Euler, and named after Eugène Catalan who elaborated on them in a paper in the 1830s. First here are a few problems for which they are relevant :
Some counting problems
(1) Given a polygon with n sides, into how many triangles can its area be divided by connecting vertices with non-crossing line segments. If n=4, the answer is readily seen to be 2, if n=5, the answer is 5 obtained by drawing two internal rays from each of the vertices in turn:
The n=6 case is a little more complex and just three of the 14 possibilities are shown:
(2) Given a list of n numbers to be totalled, how many different ways of subtotalling are there, for example for an n-list with n=4 the possibilities are :
- ((a+b)+c)+d (a+(b+c))+d (a+b)+(c+d) a+((b+c)+d) a+(b+(c+d))
(3) How many binary trees are there with n branches which do not end in a leaf. For example for n=2 the possible trees are (n.b. leaves when reached are not shown) :
(4) How many ways can n pairs of parentheses be written in such a way that no right parenthesis appears before its matching left parenthesis, for example with n=3 pairs
((( ))) (( ))( ) (( )( )) ( )(( )) ( )( )( )
(5)In an n by n ‘Manhattan diagram’ how many different progressive routes are there from bottom left to top right which do not cross the diagonal but may be on either side of it. One such route is
(6) How many different mountain ranges can be formed given n slopes, e.g. for n=6 the possibilities are
The Catalan Sequence
The Catalan numbers can be evaluated by a simple formula (2n!)/[(n+1)! n!], and so the first twelve Catalan numbers along with their indices are
cat=.monad : '(!+:y)%(*/! every y,y+1)' |:(i.12),.cat every i.12 0 1 2 3 4 5 6 7 8 9 10 11 1 1 2 5 14 42 132 429 1430 4862 16796 58786
The ratio of the (n+1)th number to the nth is 2(2n+1)/(n+2) which for large values of n approaches 4.
The procedure for obtaining the next Catalan number is similar to, but slightly more elaborate than, that for the Fibonacci sequence. Based on the hook (,:|.) the rule is ‘take a sequence and its reverse, multiply corresponding pairs and add’ :
]u=.(,:|.)t=.cat every i.5 1 1 2 5 14 14 5 2 1 1 +/*/u 42
Another interesting property of Catalan sequences involves determinants and is illustrated by the sequence below.
cat every i.4 1 1 2 5
(i.4)+every <i.4 NB. construct a matrix of indices ... 0 1 2 3 1 2 3 4 2 3 4 5 3 4 5 6
box=.<”1 (cat every) every box (<i.4)+every i.4 1 1 2 5 1 2 5 14 2 5 14 42 5 14 42 132
So define :
catmat=.monad : 'cat every every box (<i.y)+every i.y det=.-/ .* det catmat 4 1
Now generalise :
catdet=.monad : 'det catmat y' catdet every i.12 1 1 1 1 1 1 1 1 1 1 0.999957 0.99893
The last two items reflect the rapid growth in size of the Catalan numbers as the sequence progresses.
Relation to Permutations and Combinations
J conveniently gives a list of all permutations of a given order by
allperms=.i.@! A. i. |:allperms 4 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 1 1 2 2 3 3 0 0 2 2 3 3 0 0 1 1 3 3 0 0 1 1 2 2 2 3 1 3 1 2 2 3 0 3 0 2 1 3 0 3 0 1 1 2 0 2 0 1 3 2 3 1 2 1 3 2 3 0 2 0 3 1 3 0 1 0 2 1 2 0 1 0
(Note : the transpose |: is applied for compactness of display.)
Catalan permutations are those in which there are no sub-lists of length 3. A first step in extracting these is
incseq=.*./@(_1&}.)@:(< 1&|.) NB. 1 if list y strictly increasing incseq every 2 3 4 5;2 5 4 3 1 0
The items which form a three-sequence in a permutation need not be consecutive, so for any permutation, all possible 3-lists must be obtained, e.g. 1 4 2 3 contains the strictly increasing sub-list 1 2 3. Testing for all 3-lists within a given permutation therefore requires a verb to give all combinations of r items out of n.
cnos=.i.@:(2&^)@] NB. integers from 0 to 2^n -1
bins=.#:@cnos NB. binary nos from 0 to 2^n-1
mark=.|.@((= +/"1@bins) # cnos) { bins NB. 1=include in combn
combs=.mark #"1 i.@] NB. transform to combinations
|:3 combs 4
0 0 0 1
1 1 2 2
2 3 3 3
The ‘no ascending-3-list’ is then given by
tri=.monad : '-.+./incseq every box (box 3 combs #y){ every <y'
tri every 1 4 2 3;3 4 1 2
0 1
|:(tri every box t)#t=.allperms 3 NB. 5 columns
0 1 1 2 2
2 0 2 0 1
1 2 0 1 0
|:(tri every box t)#t=. allperms 4 NB. 14 columns
0 1 1 1 2 2 2 2 2 3 3 3 3 3
3 0 3 3 0 1 1 3 3 0 1 1 2 2
2 3 0 2 3 0 3 0 1 2 0 2 0 1
1 2 2 0 1 3 0 1 0 1 2 0 1 0
Returning to the six problems
The solutions are now seen to be
- (1) cat(n-2), (2) cat(n-1), (3) cat(n+1), (4) cat(n), (5) 2cat(n), (6) cat(n/2).
The correspondences between (2) and (3), and between (4), (5) and (6) are relatively easy to observe. In the case of (4) write L for left parenthesis, R for right parenthesis. The number of valid pairings is thus the number of possible words such as LLRRLRLLLRLRRR starting with L in which n= the equal numbers of Ls and Rs. To count these introduce a ‘false’ L as first character to ensure validity of the bracketing represented. The number of words in the enhanced set is thus the number of ways in which n like items can be chosen from 2n+1 which is 2n+1Cn = ((2n+1)!)/[((n+1)!)(n!)] divided by (2n+1), since the first character is pre-determined. This simplifies to the formula 2nCn/(n+1) as given above.
Code Summary
box=: <"1
det=: -/ .*
cat=: monad : '(!+:y)%(*/! every y,y+1)' NB. Catalan numbers
allperms=: i.@! A. i. NB. List of all perms
perms=: dyad :'~.x{.&.|: allperms y' NB. All y-perms from x
combs=: mark #"1 i.@] NB. All y-combns from x
mark=: |.@((= +/"1@bins) # cnos) { bins NB. 1=include in combn
cnos=: i.@:(2&^)@] NB. integers from 0 to 2^n -1
bins=: #:@cnos NB. binary nos from 0 to 2^n-1
incseq=: *./@(_1&}.)@:(< 1&|.) NB. 1 if list strictly increasing
NB. Catalan perms of order y:
tri=: monad : '-.+./incseq every box (box 3 combs #y){ every <y'
catmat=: monad :'cat every every box (<i.y)+every i.y' NB. Catalan matrix ...
catdet=: monad :'det catmat y' NB. ... and its determinant