Extended Pascal Triangles

bismillahmultinomial

What is Extended Binomial Triangle?

The Pascal’s Triangle lists the Binomial Coefficients. The expansion (1+x)^n = \binom{n}{0} + \binom{n}{1} x^1+\cdots +\binom{n}{i} x^i + \cdots + \binom{n}{n}x^n has the coefficients of x^i‘s listed in the nth row of Pascal’s Triangle. The Extended Pascal’s Triangle is the expansion of (1+x+x^2+\cdots+x^l)^n = \binom{n}{0}_l  + \binom{n}{1}_l x + \cdots + \binom{n}{ln}_l x^{ln} .

Intuitively if we have l-faced dice with face values \{0,1,2,\cdots,l\} , the nth row of Extend Pascal’s Triangle lists the \binom{n}{i}_l number of ways to get the sum i, when n such dice are thrown.

It is easy to observe that maximum value in a row is found at index \lceil nl/2\rceil. A formula by Eger [1] gives this maximum value as function of l and n as  \binom{n}{nl/2}_l = \frac{(q+1)^n}{\sqrt{( 2 \pi n q (q+2)/12)}}  .

What is Here?

Here is a Latex + Tikz + Lua script to draw the Extended Pascal’s triangle. Apart from the famous triangle where each entry in a row is the sum of two overhead entries in upper row, In Extended Pascal’s Triangle there can be any number of elements that sum to give an entry in next row. Above picture uses 4 such elements.

How it Started?

One publication required to draw the extended Pascal Triangle. Previously I did it with tables in latex code. This time I learned some Tikz and Lua scripting to automatically draw the figure.

The Source Code

%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Author : Abu Bakar Siddique (14-Oct-2015)
% Credits : It started from Paul Gaborit's binomial Pascal triangle
% License: Creative Commons attribution license.
% Title : Extended Pascal's Triangle
% Information: nth row in usual Pascal triangle gives coefficients
% of x^k in expansion of (1+x)^n. My extended pascal triangle
% for trinomial gives coefficients of x^k in expansion
% of (1+x+x^2)^n . The constant \nomialVal{2} determines
% the order of base polynomial.

% \def\vRatio{3} % Vertical Ratio: Increase to expand vertically
% \def\hRatio{1} % Horizontal Ratio: Increase to expand horizontally
% \def\nomialVal{4} % {2} for binomial, {3} for trinomial
% \def\numRows{5} %{5} 5 means rows in the extended pascal triangle

\documentclass[crop,tikz]{standalone}% 'crop' is the default for v1.0, before it was 'preview'
\usepackage[landscape,margin=1cm]{geometry}
\pagestyle{empty}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{comment}
\usepackage{ifthen}
\usepackage{tikz}
\usetikzlibrary{positioning,shadows,backgrounds}

\begin{document}
  \centering
  \def\vRatio{3} % Vertical Ratio: Increase to expand vertically
  \def\hRatio{1} % Horizontal Ratio: Increase to expand horizontally
  \def\nomialVal{4} % {2} for binomial, {3} for trinomial
  \def\numRows{5} %{5} 5 means rows in the extended pascal triangle

  \begin{tikzpicture}[x=30mm,y=11mm]
  \pgfmathtruncatemacro{\ncol}{-\numRows*(\nomialVal)/2*\hRatio}
  \draw (\ncol,1) -- +(2,2);
  % some colors

%  \colorlet{even}{blue!127!white}
  \colorlet{even}{blue!100!black}
  \colorlet{links}{red!127!black}
  \colorlet{back}{green!30!white}
  % some styles
  \tikzset{
    box/.style={
      text width=25mm,
      minimum height=5mm,
      inner sep=.7mm,
      outer sep=0mm,
      text centered,
      %font=\small\bfseries\sffamily,
      font=\LARGE\bfseries\sffamily,
      text=#1!50!black,
      draw=#1,
      line width=.25mm,
      top color=#1!5,
      bottom color=#1!40,
      shading angle=0,
      rounded corners=2.3mm,
      drop shadow={fill=#1!40!gray,fill opacity=.8},
      rotate=0,
    },
    link/.style={-latex,links,line width=.3mm},
    plus/.style={text=links,font=\footnotesize\bfseries\sffamily},
  }
  % Pascal's triangle
  % row #0 => value is 1

  % Draw nodes: p-0-0 is first node (0th row and 0th column)
  \foreach \row in {0,...,\numRows} {
    \pgfmathtruncatemacro{\eCol}{\row*(\nomialVal-1) )} //eCol = row * (nomial-1)
    \foreach \col in {0,...,\eCol} {
      \coordinate (pos) at ({-\row*(\nomialVal-1)/2*\hRatio+\col*\hRatio}, -\row*\vRatio);
      \node[box=even,label={}] (p-\row-\col) at (pos)
      	  {\directlua{tex.print("" .. multinom(\row,\col,\nomialVal))}};
    }
  }

  % Draw arrows from each node to "nomialVal" nodes in next row
  \foreach \row in {0,...,\numRows} {
    \pgfmathtruncatemacro{\eCol}{\row*(\nomialVal-1) )} //eCol = row * (nomial-1)
    \foreach \col in {0,...,\eCol} {
	  \foreach \arrow in {1,...,\nomialVal} {
	    \pgfmathtruncatemacro{\ncol}{\col+\arrow-1}
	    \pgfmathtruncatemacro{\nrow}{\row+1}
		\ifnum \row<\numRows
		  \draw[link] (p-\row-\col) -- (p-\nrow-\ncol);
		\fi
	  }
    }
  }  

  \pgfmathtruncatemacro{\ncol}{\numRows*(\nomialVal-1)}
  \begin{pgfonlayer}{background}
    % filling and drawing with the same color to enlarge background
    \path[draw=back,fill=back,line width=5mm,rounded corners=2.5mm]
    (  p-0-0.north west) -- (  p-0-0.north east) --
    (p-\numRows-\ncol.north east) -- (p-\numRows-\ncol.south east) --
    ( p-\numRows-0.south west) -- ( p-\numRows-0.north west) --
    cycle;
  \end{pgfonlayer}

  \end{tikzpicture}

\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The above code makes use of following lualatex functions and these can be added on top of the same latex file.

\directlua{
  function factorial (f)
    if f < 2 then  return 1 else  return f*factorial(f-1) end
  end

  function nchoosek(n, k)
    if (k>=0 and k<=n) then
      y = (factorial(n) / (factorial(n-k) * factorial(k)) )
    else
      if(k==n and k<0) then y=1  else y=0  end
    end
    return round(y)
  end  

  function round(num, idp)
    local mult = 10^(idp or 0)
    return math.floor(num * mult + 0.5) / mult
  end

  function multinom(n,r,s)
    r = n+r;
    sum=0;
    for k=0,math.floor((r-n)/s),1 do
      sum = sum + ((-1)^k * nchoosek(n,k)*nchoosek(r-s*k-1,n-1));
    end
    return round(sum,1)
  end
}
Binomial Pascal Triangle with 25 Rows (Click for Enlarged View)
Binomial Pascal Triangle with 25 Rows
References:

1. S. Eger, Stirling’s approximation for central extended binomial coefficients, The American Mathematical Monthly 121 (2014), 344–349.

2. Stack exchange posts that shows number of ways a Pascal's Triangle can be plotted in Tikz:
http://tex.stackexchange.com/questions/17522/pascals-triangle-in-tikz
http://tex.stackexchange.com/questions/32654/pascals-triangle-in-latex-with-pointing-arrows

3. Here is Mr. Christopher Olah from Toronto explaining some aspects of Pascal's triangle on his blog: 
https://christopherolah.wordpress.com/2011/08/29/understanding-pascals-triangle/

4. Of course wikipedia has very interesting info on Pascal's Triangle too:
https://en.wikipedia.org/wiki/Pascal%27s_triangle


Advertisements

Comments Invited

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s