Skip to main content
\(\newcommand{\cycle}[1]{\arraycolsep 5 pt \left(\begin{array}#1\end{array}\right)} \newcommand{\importantarrow}{\Rightarrow} \newcommand{\qchoose}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_q} \def\neg1choose#1#2{\genfrac{[}{]}{0pt}{}{#1}{#2}_{-1}} \newcommand{\bp}{ \begin{enumerate}{\setcounter{enumi}{\value{problemnumber}}}} \newcommand{\ep}{\setcounter{problemnumber}{\value{enumi}} \end{enumerate}} \newcommand{\ignore}[1]{} \renewcommand{\bottomfraction}{.8} \renewcommand{\topfraction}{.8} \newcommand{\apple}{\text{🍎}} \newcommand{\ap}{\apple} \newcommand{\banana}{\text{🍌}} \newcommand{\ba}{\banana} \newcommand{\pear}{\text{🍐}} \newcommand{\pe}{\pear} \DeclareMathOperator{\Fix}{Fix} \DeclareMathOperator{\Orb}{Orb} \newcommand{\F}{\mathcal{F}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section C.1 Indicator Functions

When we introduced the idea of a generating function, we said that the formal sum

\begin{equation*} \sum_{i=0}^n a_ix^i \end{equation*}

may be thought of as a convenient way to keep track of the sequence \(a_i\text{.}\) We then did quite a few examples that showed how combinatorial properties of arrangements counted by the coefficients in a generating function could be mirrored by algebraic properties of the generating functions themselves. The monomials \(x^i\) are called indicator polynomials. (They indicate the position of the coefficient \(a_i\text{.}\)) One example of a generating function is given by

\begin{equation*} (1+x)^n = \sum_{i=0}^\infty \binom{n}{i}x^i. \end{equation*}

Thus we say that \((1+x)^n\) is the generating function for the binomial coefficients \(\binom{n}{i}\text{.}\) The notation tells us that we are assuming that only \(i\) varies in the sum on the right, but that the equation holds for each fixed integer \(n\text{.}\) This is implicit when we say that \((1+x)^n\) is the generating function for \(\binom{n}{i}\text{,}\) because we haven't written \(i\) anywhere in \((1+x)^n\text{,}\) so it is free to vary.

Another example of a generating function is given by

\begin{equation*} x^{\underline{n}} = \sum_{i=0}^\infty s(n,i)x^i. \end{equation*}

Thus we say that \(x^{\underline{n}}\) is the generating function for the Stirling numbers of the first kind, \(s(n,i)\text{.}\) There is a similar equation for Stirling numbers of the second kind, namely

\begin{equation*} x^n = \sum_{i=0}^\infty S(n,i)x^{\underline{i}}. \end{equation*}

However with our previous definition of generating functions, this equation would not give a generating function for the Stirling numbers of the second kind, because \(S(n,i)\) is not the coefficient of \(x^i\text{.}\) If we were willing to consider the falling factorial powers \(x^{\underline{i}}\) as indicator polynomials, then we could say that \(x^n\) is the generating function for the numbers \(S(n,i)\) relative to these indicator polynomials. This suggests that perhaps different sorts of indicator polynomials go naturally with different sequences of numbers.

The binomial theorem gives us yet another example.

Problem 371

Write \((1+x)^n\) as a sum of multiples of \(\frac{x^i}{i!}\) rather than as a sum of multiples of \(x^i\text{.}\)

This example suggests that we could say that \((1+x)^n\) is the generating function for the falling factorial powers \(n^{\underline{i}}\) relative to the indicator polynomials \(\frac{x^i}{i!}\text{.}\) In general, a sequence of polynomials is called a family of indicator polynomials if there is one polynomial of each nonnegative integer degree in the sequence. Those familiar with linear algebra will recognize that this says that a family of indicator polynomials form a basis for the vector space of polynomials. This means that each polynomial way can be expressed as a sum of numerical multiples of indicator polynomials in one and only one way. One could use the language of linear algebra to define indicator polynomials in an even more general way, but a definition in such generality would not be useful to us at this point.