21

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

enter image description here

Image taken from the Catalan number Wikipedia page.

39

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}

enter image description here

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}

all steps

  • 9
    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
  • @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
  • 7
    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
  • 1
    @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
8

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.

enter image description here

  • 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. :-) – kiss my armpit Jul 17 '12 at 16:20
  • 2
    latex->dvips->ps2pdf is extremely "crazy". It can produce10 by 10 Catalan diagrams which are 16,796 pages in total. :-) – kiss my armpit Jul 17 '12 at 18:52
6

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

enter image description here

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

\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
\def\d#1{\advance#1-1\relax}

\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}
  • 1
    I made it as a CW post just for avoiding getting a reputation point. – kiss my armpit Sep 10 '12 at 4:32
5

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\numupadmitted{\x/2}%
\ifnum\numupadmitted=\theup
\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}

enter image description here

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.