# Extended Pascal Triangles

## 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
% 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}

\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{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,
rounded corners=2.3mm,
rotate=0,
},
}
% Pascal's triangle
% row #0 =&amp;gt; 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(&amp;quot;&amp;quot; .. multinom(\row,\col,\nomialVal))}};
}
}

% Draw arrows from each node to &amp;quot;nomialVal&amp;quot; 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&amp;lt;\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 &amp;lt; 2 then  return 1 else  return f*factorial(f-1) end
end

function nchoosek(n, k)
if (k&amp;gt;=0 and k&amp;lt;=n) then
y = (factorial(n) / (factorial(n-k) * factorial(k)) )
else
if(k==n and k&amp;lt;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
}

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