a) (i.e. Permutations of the letters in MATHEMATICS)
b) (i.e. Permutations of the letters in COASTAL CAROLINA)
We utilize exponential generating functions
Recall the problem of finding the number of permutations of the letters in the word MISSISSIPPI. The answer was . Let’s modify the question slightly. Find the number of permutations of 9 of the letters in the word MISSISSIPPI.
The answer is the sum of the number of permutations of each of the possible combinations of 9 of the letters.
In other words, we must first select 9 of the 11 letters, then we must count the
number of permutations of these 9 letters. After doing this for every possible
selection of 9 of the 11 letters, we sum these answers. There are 9 different
combinations of 9 of the 11 letters:
SSISSIPPI, ISISSIPPI, ISSISSIPI, MSSSSIPPI, MSISSIPPI, MSSISSIPI,
MIISSIPPI, MISISSIPI, and MISSISSII.
Thus the total number of ways to permute 9 of the 11 letters in the word MISSISSIPPI is
We would like to see this answer a coefficient in some generating function. For the letter M, consider the function . For the letter I, consider . For the letter S, consider , and for the letter P, consider . The product of these functions is Note that this function is a polynomial of degree . Since we are considering the permutations of 9 of the 11 letters in the word, let’s inspect the coefficient of . We notice that is almost matches the solution to our problem. It is Thus the answer to our problem can be considered the coefficient not of , but of . This discussion both motivates the following definition of exponential generating functions and verifies the proposition that follows.
The exponential generating function of the sequence is the function If the sequence
is finite, then the corresponding summation is finite, i.e., the exponential generating
function of the sequence is
The name “exponential” generating function is motivated by the fact that the
exponential generating function of the sequence is
Let be the number of permutations of of the objects in the multiset . The
exponential generating function for the sequence is where .
example 1 Find the exponential generating function of the sequence where is is the
number of permutations of of the elements in the multiset .
According to the proposition with and , we have
According to the proposition with and , we have
(problem 1) Find the exponential generating function of the sequence where is is the
number of permutations of of the elements in the given multiset.
a) (i.e. Permutations of the letters in MATHEMATICS)
a) (i.e. Permutations of the letters in MATHEMATICS)
example 2 Let be the number of permutations of of the elements of the multiset .
Find the exponential generating function of the sequence .
According the the proposition, the exponential generating function is
According the the proposition, the exponential generating function is
(problem 2) Let be the number of permutations of of the elements of the
given multiset. Find the exponential generating function of the sequence
.
a)
a)
b)
example 3 Let be the number of permutations of of the elements of the multiset .
Find the exponential generating function of the sequence .
According the the proposition, the exponential generating function is
According the the proposition, the exponential generating function is
example 4 Let be the number of ways to color the squares of a chess board
using the colors red, white and blue if the number of squares painted blue
must be even. Find the exponential generating function for the sequence
.
This problem is analogous to example 3, with the exception of the condition that the number of blue squares must be even. Hence, the exponential generating function is Since we know the Maclaurin series for , we can find an explicit formula for . We have and hence .
This problem is analogous to example 3, with the exception of the condition that the number of blue squares must be even. Hence, the exponential generating function is Since we know the Maclaurin series for , we can find an explicit formula for . We have and hence .
(problem 4) Let be the number of ways to color the squares of a chess board
using the colors red, white and blue with the indicated conditions. Find the
exponential generating function for the sequence , and find an explicit formula for
.
a) The number of blue squares must be odd.
a) The number of blue squares must be odd.
b) There must be at least one blue square.