Catalan Numbers

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa 365 Puzzlers  Calendar 2017

Mensa 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

Problem Description

Create a program to compute Catalan numbers and list the expressions they represent.

 

Background & Techniques

An expression generator was needed to implement our version of the British TV game show, "Countdown", CountdownPlus.   The game requires that expressions evaluating to a given value be created from a given set of numbers.  Catalan numbers are the key to creating all possible valid algebraic expressions of a given length. This page explores Catalan numbers on more detail.   We'll start by seeing how to generate the "templates" for all parenthesized expressions of a given length. 

Given symbols "X" and "Y", generate all possible strings of length 2N following these two rules:

  1. The final string must contain the same number of X's and Y's (N of each).
  2. As the string is built (or examined) from left to right, the number Y's can never exceed the number of X's.  Or, stated another way: The number of Y's in any initial segment of the string cannot exceed the number of X's.    

The Nth Catalan number CN, is the number of such strings.  They are named after Belgian mathematician Eugene Catalan.  The strings are called "Dyck" words after German mathematician Walther Van Dyck. 

The equation for CN is given by the number of combinations of 2N things taken N at time divided by (N+1).  The more difficult problem is to list all of the templates for a given N.  Replacing "X" with "(" and "Y" with ")" gives all valid expression structures containing N sets of parentheses.  If we replace X's with  "(" and "Y"s with variable names. ("a", "b", c", ...), and add one extra variable at then end, we have the basis for constructing all valid  algebraic expressions containing N+1 variables connected by  binary operators (e.g. +, -, x, or /). 

That is exactly what this program does.  Here is a step by step example of the process:

  1. Start with a C3 string, for example, XYXXYY to represent some 4 variable expression.  Note: For reasons described below, the program displays "1"s and "0"s instead of "X"s and "Y"s
  2. Replace X's with left parens and Y's with variable names:  (a((bc
  3. Add the 4th variable; (a((bcd
  4. Insert right parens after each variable occurrence after the first within a level.  Addadditional right parentheses at the end to balance the number of left pearentheses: (a((bc)d))
  5. Insert operators (we'll use only * operators here): (a*((b*c)*d)).

This example is one of the 5 "templates" for expressions with 4 variables.  For each of these,  the 4 variables can occur in 24, (4!), ways and the  4 common binary operators which occur 3 times (and which may be repeated)  can appear in 64, (43), ways.  So altogether there are 7,680 (5x24x64) parenthesized algebraic expressions with 4 variables and 4 binary operators.

For the Countdown game there are 42 ways to write expressions with 6 variables and 5 operations.   For each of these expression "templates",  the 6 variables (the given constants) may be plugged in in 720 ways, and the 4 operation choices which may appear in the 5 operation positions may be substituted in 1024 ways.  That makes more than 3 million expressions to be evaluated to find all solutions!  

Non-programmers are welcome to read on, but may want to skip to the bottom of this page to download executable version of the program.

Notes for programmers:  

The trickiest part of writing the code was deciding how to generate the templates.  I decided to use 1 and 0 characters instead of X and Y which allowed me to check treat each string as the binary representation of an integer.  Considered this way, all of the templates can be represented by integers whose binary representation falls between 101010... and 111...000... inclusive and which  can be inspected individually to save those which meet the 2 original rules.  Function IsOK accomplished this.  Valid keys are converted back to binary strings and saved in ListBox1.  A pass through Listbox1(Phase 2) then converts "1"s to left parentheses and "0" s to variable letters as described in the example above.  Procedures AddRightParens and AddOps add right parentheses and operation characters to make the final expression template which are saved in ListBox2.

The number of variable values in generated templates is limited to 9 merely because that is largest template lengths that can be conveniently displayed.

 Running/Exploring the Program 

bulletDownload source
bulletDownload  executable

Suggestions for Further Explorations

Original Date: May 25, 2010 

Modified: July 29, 2017

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.