Cane Toads & Mathematical Modeling with Generating Functions
Let’s explore generating functions — a really cool combinatorial technique.
Australia boasts a diverse array of wildlife, including venomous spiders, crazed koalas, and aggressive crocodiles. However, within this rich ecosystem, there exists a species that has become a notorious source of trouble: the Cane Toad. Cane toads were initially introduced to combat agricultural pests but have become an invasive species in Australia, causing disruption to local communities. Today, we are going to construct a mathematical model on the infamous Cane Toad.
We’ve been hired by the Australian government to analyze the risk of a Cane Toad outbreak in three regions of Australia — the north, the west, and the east. Scientists have provided estimates suggesting that there could be as few as 2 and as many as 6 cane toads in each region. An outbreak is defined as a total of 11 or more cane toads across all three regions combined. The government will allocate resources to eradicate cane toads if an outbreak occurs. Our objective is to calculate the probability that an outbreak exists given the current estimates.
To solve this problem, we can use generating functions. What are generating functions? A generating function is a mathematical tool used to represent an infinite sequence of numbers using an infinite sum of terms involving the powers of a variable. An example is “1 + 2x + 3x² + 4x³ + …” which represents the sequence (1, 2, 3, 4, …). Through mathematical manipulation of the generating functions, we can extract information about the original sequence.
In the context of our problem, we can use generating functions to represent different labeled boxes, and then search for a specific item within those boxes. Consider the generating function “1 + 3x + 2x² + x³ + …” which represents a set of boxes. Each box is labeled with a power of x that corresponds to the number of cane toads inside the box, while the coefficient of x represents the number of boxes. For example, the term 2x² represents two boxes containing two cane toads as illustrated in the figure below.
Since each region reports cane toads in the range from 2 to 6, we can represent the generating function for each region as (x² + x³ + x⁴ + x⁵ + x⁶). Furthermore, since there are three regions, we raise this function to the power of three. Thus, our generating function becomes g(x) = (x² + x³ + … + x⁶)³. This is visually depicted in the figure below.
Our original problem defines an outbreak as the presence of 11 or more cane toads across all three regions. To simplify the problem, we will determine the number of ways to distribute only 11 cane toads among these three regions. This can be achieved by finding the coefficient of x¹¹ in the expression (x² + x³ + … + x⁶)³. Afterward, we will use a computer simulation to calculate the coefficients of x¹², x¹³, and so on to determine the presence of 11 or more cane toads across all three regions. And so, our current objective can be restated as follows:
Find the coefficient of x¹¹ in (x²+x³+…+x⁶)³
Let’s first simplify the generating function g(x) = (x² + x³ + … + x⁶)³ by factoring out an x² term to get g(x) = x⁶(1 + x + … + x⁴)³.
In order to simplify this expression further, we need to understand geometric series. What are geometric series? Geometric series are a set of numbers that increase by a constant ratio. A constant ratio is a number by which each term in the sequence is multiplied to obtain the next term (i.e. the sequence 1, 2, 4, 8, 16 increase by a constant ratio of 2).
Let’s break down our simplified expression g(x) = x⁶(1+x+…+x⁴)³ and focus on the “1+x+…+x⁴” portion. This particular section can be represented as a sequence that follows a geometric series pattern. In this series, the first term (a₁) is 1, the constant ratio between consecutive terms (r) is x — each term is multiplied by x — and there are a total of five terms (n).
So now g(x) has the following equation.
Let’s separate this equation into the numerator and the denominator.
To determine the coefficient of x¹¹ in the expression g(x), let’s consider an analogy using money. Imagine we need to collect a total of $11. In this analogy, each term in the expression g(x) represents different ways of obtaining money in certain denominations. For example, the term x⁶ gives you $6. However, we still need an additional $5 to reach the total of $11. To obtain this remaining amount, we need to consider the other terms in g(x).
Each term in g(x) has different denominations of money. First, let’s figure out the denominations of the binomial within Term B.
Typically, we would expand and distribute a binomial by using the FOIL method. However, this process is time-consuming so we have a quicker alternative: the binomial theorem.
The binomial coefficient (n choose k) represents the number of ways to choose k items from n possibilities, as expressed in the formula below.
Applied to our problem, we get the following denominations for Term B.
By considering Term A and Term B, we can determine the possible denominations in Term C based on the total amount required, which is $11 in our case.
Since we need to collect a coin from each term, we see that Term C can only have two denominations: $0 and $5.
Term C is a geometric series that can be converted back into a geometric sequence as shown in the figure below.
Let’s approach this problem using the concept of geometric sequences, as we discussed earlier. We will assign each individual generating function (1 + x + x² + …) to variables, denoted as y₁, y₂, and y₃.
Our objective is to determine the values of y₁, y₂, and y₃ that correspond to the denominations in Term C, which can be either 0 or 5. Since finding the values that make the equation equal to 0 is a trivial task, we will focus on identifying the values that make the equation equal to 5.
By solving this equation, we need to then determine the number of ways to distribute the sum of 5 across these variables. To tackle this problem, we will utilize a specific combinatorial technique known as “stars and bars.” In the traditional example, stars and bars are used, but we will use the analogy of distributing cane toads for thematic purposes. Since we aim to distribute a total of 5 cane toads among three variables, we can represent this by placing 5 cane toads. We will then use two walls (represented by the equals sign) to separate them. By rearranging the bars, we can create different combinations of equations.
In this problem, there are seven spots available for placement, consisting of five cane toads and two bars. We can select two spots out of the seven to position the bars, while the remaining spots will be filled with cane toads. The binomial coefficient, as introduced earlier, is ideal for this scenario as it enables the selection of a specific number of objects from a given set.
Finally, we need to sum up all the possible combinations to obtain $11 in total from all of these denominations.
Let’s do the math!
We have determined that the coefficient of x¹¹ in (x²+x³+x⁴+x⁵+x⁶)³ is 18.
An alternative method for solving this problem involves utilizing the multinomial theorem, an extension of the binomial theorem. While the binomial theorem applies when there are two terms raised to a power, the multinomial theorem is applicable when dealing with more than two terms raised to a power, as implied by its name. The formula for the multinomial theorem is as follows:
For the solution to this problem, I will leave it as an exercise for you to explore. However, I can provide you with a hint on how to approach it. Begin by creating a system of equations and identifying all the ordered partitions. Then, proceed to calculate the binomial coefficients associated with each partition. Finally, sum up these binomial coefficients to determine the desired result.
Now that we have determined that the coefficient of x¹¹ in (x²+x³+x⁴+x⁵+x⁶)³ is 18, let’s try to understand what this means in the context of our original problem. This coefficient represents the number of possible ways in which 11 cane toads could be distributed across the three areas in Australia. However, this only accounts for cases where there are exactly 11 cane toads, and we are interested in identifying potential outbreaks defined as 11 cane toads and more.
In order to find the outbreak, we need to calculate the coefficients for x¹¹ and subsequent higher powers of x. To do this, we can use SageMath, which is an open-source software tool for mathematical computation.
Once we establish the generating function, we can utilize various methods in SageMath to calculate the required coefficients. By summing up these coefficients, we can then proceed to determine the probability associated with the given scenario.
Yikes… with the probability of a Cane Toad outbreak being 72%, the government should take immediate measures to prevent the further devastation of agriculture and ecological communities. Those Cane Toads are vicious creatures!
Generating functions offer a remarkable tool within the realm of combinatorics, enabling us to navigate the intricacies of the world. Through its application, we gain valuable insights that help us frame our environment and make informed decisions. Nevertheless, it is crucial for us to grasp the limitations inherent in relying solely on mathematical models to decipher an ever-evolving and complex universe. By recognizing our capacity to acquire knowledge while acknowledging the multifaceted nature of reality, we empower ourselves to approach decision-making with strategic wisdom. Thanks for reading!
