As TikZ runs slower than PSTricks and I don't know how to write a recursive function in PSTricks, I was forced to make use of an external application executed from within LaTeX by \write18 macro.
If you compile the following C# source code
// This is CatalanLocator.cs
using System.Collections.Generic;
using System.IO;
namespace CatalanLocator
{
class Program
{
static void Populate(List<bool> set, int m, int n)
{
if (m == 0)
{
if (n == 0)
{
using (StreamWriter sw = new StreamWriter("data.txt", true))
{
sw.Write("{");
int x;
for (x = 0; x < set.Count - 1; x++)
sw.Write("{0},", set[x] ? 1 : 0);
sw.WriteLine("{0}}}", set[x] ? 1 : 0);
}
}
else
{
List<bool> temp = new List<bool>(set);
temp.Add(true);
Populate(temp, m, n - 1);
}
}
else
{
if (m == n)
{
List<bool> temp = new List<bool>(set);
temp.Add(false);
Populate(temp, m - 1, n);
}
else
{
List<bool> temp1 = new List<bool>(set);
temp1.Add(false);
Populate(temp1, m - 1, n);
List<bool> temp2 = new List<bool>(set);
temp2.Add(true);
Populate(temp2, m, n - 1);
}
}
}
static void Main(string[] args)
{
int N = int.Parse(args[0]);
Populate(new List<bool>(), N, N);
}
}
}
with csc CatalanLocator.cs, you will get an executable file named CatalanLocator.exe.
Executing CatalanLocator 6 manually, for example, from DOS prompt, will produce a text file named data.txt. It contains rows of sets of binary numbers. Each set represent a Catalan's path. (Catalan's path is my own terminology. Wikipedia might not have such a definition.)
However, I prefer to execute CatalanLocator from a LaTeX input file as described in the following code:
% CatalanDiagram.tex
\documentclass{article}
\usepackage{pstricks-add}
\usepackage[active,tightpage]{preview}
\PreviewBorder=12pt
\PreviewEnvironment{pspicture}
\newcounter{oX}% old x
\newcounter{oY}% old y
\newcounter{nX}% new x
\newcounter{nY}% new y
\newcounter{N}% N by N grid
\newcommand\CatalanPath[2][-]
{
% reset all counters
\setcounter{nX}{0}\setcounter{nY}{0}\setcounter{oX}{0}\setcounter{oY}{0}
% please make sure there is no blank line allowed in \psforeach
\psforeach{\i}{#2}
{
\ifnum\i=0
\stepcounter{nX}% move to the right
\else
\stepcounter{nY}% move upward
\fi
%
% draw a single segment
\psline[arrows=#1,linewidth=1pt](\theoX,\theoY)(\thenX,\thenY)
%
% renew the old counters
\setcounter{oX}{\value{nX}}
\setcounter{oY}{\value{nY}}
}
}
\newcommand\CatalanDiagram[1]
{
% probe the given Catalan's set and find the corresponding grid dimension
\setcounter{N}{0}\psforeach{\i}{#1}{\stepcounter{N}}\setcounter{N}{\numexpr\theN/2\relax}
\begin{pspicture}(\theN,\theN)
{
\psset{fillstyle=solid,linestyle=none,opacity=0.5}
% fill the upper region
\pscustom[fillcolor=cyan]{\CatalanPath{#1}\psline(\thenX,\thenY)(0,\thenY)}
% fill the lower region
\pscustom[fillcolor=yellow]{\CatalanPath{#1}\psline(\thenX,\thenY)(\thenX,0)}
}
% draw grid
\psgrid[style=gridstyle,gridlabels=0pt]
% draw a diagonal line
\psline[linestyle=dashed,dash=3pt 1.5pt,linecolor=red](\theN,\theN)
% draw Catalan path
\CatalanPath[->]{#1}
\end{pspicture}
}
\newread\myfile
\def\temp#1{\CatalanDiagram{#1}}
\begin{document}
\immediate\write18{cmd /C del data.txt}
\immediate\write18{CatalanLocator.exe 6}
\openin\myfile=data.txt\relax
\loop
\read\myfile to \j
\unless\ifeof\myfile
\expandafter\temp\j\relax
\repeat
\closein\myfile
\end{document}
Executing latex --shell-escape CatalanDiagram followed by dvips CatalanDiagram followed by ps2pdf CatalanDiagram.ps produces CatalanDiagram.pdf.
The following GIF image is the animated 6 by 6 Catalan diagram. I intentionally made it very small to save your bandwidth.
