# How to draw a Catalan number diagram on TikZ

This is a very easy question, but I am a LaTeX newbie. Any idea how to code diagrams of this kind?

Image taken from the Catalan number Wikipedia page.

-
Hi alberto, welcome to TeX.sx! Please edit your question to include information about what you've tried so far, ideally with a minimal example, and where exactly you're stuck. –  Jake Jul 16 '12 at 19:18
Follow-up Question: How to draw a generalized Catalan number diagram using TikZ. –  Peter Grill Sep 20 '12 at 21:41

An idea:

\documentclass[border=2mm]{standalone}
\usepackage{tikz}

\newcommand\catalannumber[3]{
% start point, size, Dyck word (size x 2 booleans)
\fill[cyan!25]  (#1) rectangle +(#2,#2);
\fill[fill=lime]
(#1)
\foreach \dir in {#3}{
\ifnum\dir=0
-- ++(1,0)
\else
-- ++(0,1)
\fi
} |- (#1);
\draw[help lines] (#1) grid +(#2,#2);
\draw[dashed] (#1) -- +(#2,#2);
\coordinate (prev) at (#1);
\foreach \dir in {#3}{
\ifnum\dir=0
\coordinate (dep) at (1,0);
\else
\coordinate (dep) at (0,1);
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}

\begin{document}
\begin{tikzpicture}
\catalannumber{0,0}{4}{0,1,0,0,1,1,0,1};
\catalannumber{0,-9}{8}{0,1,0,0,1,1,0,0,0,0,1,1,0,1,1,1};
\end{tikzpicture}
\end{document}


Version with all Dyck numbers:

\documentclass{article}
\usepackage[margin=1cm]{geometry}
\usepackage{tikz}
\usepackage{ifthen}
\pagestyle{empty}
\newcommand\catalannumber[3]{
% start point, size, Dyck word (size x 2 booleans)
\fill[cyan!25]  (#1) rectangle +(#2,#2);
\fill[fill=lime]
(#1)
\foreach \dir in {#3}{
\ifnum\dir=0
-- ++(1,0)
\else
-- ++(0,1)
\fi
} |- (#1);
\draw[help lines] (#1) grid +(#2,#2);
\draw[dashed] (#1) -- +(#2,#2);
\coordinate (prev) at (#1);
\foreach \dir in {#3}{
\ifnum\dir=0
\coordinate (dep) at (1,0);
\tikzset{label/.style={below}};
\else
\coordinate (dep) at (0,1);
\tikzset{label/.style={left}};
\fi
\draw[line width=2pt,-stealth] (prev) --
++(dep) coordinate (prev);
};
}

\newcommand\genallcatalannumbers[6]{%
\pgfmathtruncatemacro{\steps}{#4+#5}%
\ifthenelse{#3>\steps}{%
\ifthenelse{#5<#4}{%
{%
\ifthenelse{#4<#2}{%
\pgfmathtruncatemacro{\nbzero}{#4+1}%
\genallcatalannumbers{#1}{#2}{#3}{\nbzero}{#5}{#6,0}%
}{}%
}%
{%
\pgfmathtruncatemacro{\nbone}{#5+1}%
\genallcatalannumbers{#1}{#2}{#3}{#4}{\nbone}{#6,1}%
}%
}{%
\pgfmathtruncatemacro{\nbzero}{#4+1}%
\genallcatalannumbers{#1}{#2}{#3}{\nbzero}{#5}{#6,0}%
}%
}{%
\begin{tikzpicture}[myscale]
\catalannumber{#1}{#2}{#6}
\end{tikzpicture} %
}%
}

\newcommand\allcatalannumbers[2]{%
\pgfmathtruncatemacro{\nbsteps}{2*#2}%
\genallcatalannumbers{#1}{#2}{\nbsteps}{1}{0}{0}%
}

\begin{document}
\begin{enumerate}
\foreach \num in {1,...,5}{
\item%{\LARGE\bfseries \num}
\tikzset{myscale/.style={scale=2/\num}}
\noindent\allcatalannumbers{0,0}{\num}\par
}
\end{enumerate}
\end{document}


-
Recommend that you submit this to texample.net/tikz/examples as this is a new and useful diagram (for Computer Science and Discrete Math Instructors). This is very nice. –  R. Schumacher Jul 16 '12 at 23:08
It will be nicer if the 0,1,0,0,1,1,0,0,0,0,1,1,0,1,1,1 is obtained on the fly rather than hard coded. :-) –  Please don't touch Jul 17 '12 at 3:25
@HiggsBoson: if you think to generate all monotonic paths automatically, you can't draw my last example (with size = 9): there are 4862 different paths! –  Paul Gaborit Jul 17 '12 at 6:59
Woah, well done with the recursive generation of the paths! Very impressive! This definitely needs to go on TeXample.net. –  Jake Jul 17 '12 at 11:34
@Jake Thanks for letting me know! I had already upvoted it, but I was oblivious to the fact that there was a tick mark to click on. :) –  Combin Jul 19 '12 at 19:56

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);
Populate(temp, m, n - 1);
}
}
else
{
if (m == n)
{
List<bool> temp = new List<bool>(set);
Populate(temp, m - 1, n);
}
else
{
List<bool> temp1 = new List<bool>(set);
Populate(temp1, m - 1, n);

List<bool> temp2 = new List<bool>(set);
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[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}
}

\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
\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.

-
Could you elaborate on your opening statement "As TikZ runs slower than PSTricks (...) I was forced to make use of an external application ..."? While it's true that TikZ runs slower than PSTricks, I don't see the relevance in this case. PolGab's code runs surprisingly quickly for me, definitely fast enough to be usable. –  Jake Jul 17 '12 at 16:16
@Jake: As Tikz runs slower than PSTricks, I want to make use of PSTricks. However, I have no knowledge to do so. The last resort is to use an external program which is much faster than PSTricks. :-) –  Please don't touch Jul 17 '12 at 16:20
latex->dvips->ps2pdf is extremely "crazy". It can produce10 by 10 Catalan diagrams which are 16,796 pages in total. :-) –  Please don't touch Jul 17 '12 at 18:52

This is my latest edit. Hopefully it is the most minimal. Now it does not use an external application nor pgf package.

\documentclass[pstricks,border=5pt]{standalone}

\newcommand\One[2]{%
\begin{pspicture}(#2,#2)
\psframe*[linecolor=cyan](#2,#2)
\pscustom*[linecolor=brown]{
\moveto(0,0)
\psforeach{\i}{#1}{\ifnum\i=0\rlineto(1,0)\else\rlineto(0,1)\fi}
\psline(#2,#2)(#2,0)}
\psgrid[style=gridstyle,gridlabels=0pt]
\psline[linestyle=dashed,dash=3pt 1.5pt,linecolor=red](#2,#2)
\psStartPoint(0,0)\psset{ArrowInside=->,arrowscale=0.75}
\psforeach{\i}{#1}{\ifnum\i=0\psVector[arrows=-](1,0)\else\psVector[arrows=-](0,1)\fi}
\end{pspicture}}

\newcount\u
\newcount\r

\newcommand{\All}[4]{%
\r#2\u#3%
\ifnum\r=0
\ifnum\u=0
\One{#1}{#4}\else
\d\u\All{#1,1}{#2}{\the\u}{#4}\fi
\else
\ifnum\r=\u
\d\r\All{#1,0}{\the\r}{#3}{#4}\else
{\d\r\All{#1,0}{\the\r}{#3}{#4}}% must be grouped!
\d\u\All{#1,1}{#2}{\the\u}{#4}\fi
\fi}

\begin{document}
\All{0}{3}{4}{4}
\end{document}

-
I made it as a CW post just for avoiding getting a reputation point. –  Please don't touch Sep 10 '12 at 4:32

Just for fun... a randomized version based on PolGab's first answer.

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{backgrounds}
\pgfdeclarelayer{mylayer}
\pgfsetlayers{background,mylayer,main}
\usepackage{etoolbox}

% counters to check movements
\newcounter{up}
\newcounter{rightp}

\newcommand\catalannumber[2]{
\setcounter{up}{0}
\setcounter{rightp}{0}
% start point, size
\begin{pgfonlayer}{background}
\fill[cyan!25]  (#1) rectangle +(#2,#2);
\end{pgfonlayer}
\draw[help lines] (#1) grid +(#2,#2);
\draw[dashed] (#1) -- +(#2,#2);
\coordinate (prev) at (#1);

\pgfmathtruncatemacro\dim{#2*2}
\foreach \x in {1,...,\dim}{
\pgfmathtruncatemacro\dir{round(rand)}
% first case
\ifnum\x=1
\pgfmathtruncatemacro\dir{0}
\fi
% normal behaviour
\ifnumodd{\x}{
% check number of up to not exceed the diagonal
\pgfmathtruncatemacro\dir{0}
\fi
}{}
% check number of rightp to not exceed the border
\ifnum\therightp=#2
\pgfmathtruncatemacro\dir{1}
\fi
% movements
\ifnum\dir=0
\coordinate (dep) at (1,0);
\stepcounter{rightp}
\else
\coordinate (dep) at (0,1);
\stepcounter{up}
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) node(a\x){} coordinate (prev){};
}
\begin{pgfonlayer}{mylayer}
\fill[orange!25](#1)
\foreach \x in {1,...,\dim}{
--(a\x.center)
}|-(#1);
\end{pgfonlayer}
}

\begin{document}
\begin{tikzpicture}
\catalannumber{0,0}{7};
\catalannumber{0,-10}{9};
\end{tikzpicture}
\end{document}


-