Take the 2-minute tour ×
TeX - LaTeX Stack Exchange is a question and answer site for users of TeX, LaTeX, ConTeXt, and related typesetting systems. It's 100% free, no registration required.

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.

share|improve this question
7  
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
add comment

4 Answers

up vote 36 down vote accepted

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

share|improve this answer
8  
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. :-) –  I am who I say I am 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
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
show 1 more comment

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

share|improve this answer
    
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. :-) –  I am who I say I am 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. :-) –  I am who I say I am Jul 17 '12 at 18:52
    
add comment

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

share|improve this answer
add comment

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}
share|improve this answer
1  
I made it as a CW post just for avoiding getting a reputation point. –  I am who I say I am Sep 10 '12 at 4:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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