We have n euros. Every day we buy exactly one of the following products: pretzel (1 euro), candy (2 euro), icecream (2 euros). What is the number of possible ways of spending all the money (the order of the bought products counts)?
How we can solve this problem using generating function? Any help will be appreciated.
If $k$ is the number of days and $n$ the number of euros, the number of possibilities is :
$$\binom {k}{n-k} 2^{n-k}$$
The generating function for one day is:
$$Oneday = e + e^2 + e^2$$
meaning that there is one way to spend one euro and two ways to spent two euros.
$k$ days will be described by :
$$Oneday^k = (e + e^2 + e^2)^k$$
that gives the coefficients
$1, 2$
$0, 1, 4, 4$
$0, 0, 1, 6, \bbox[border:1px solid green] {12}, 8$
$0, 0, 0, 1, 8, 24, 32, 16$
where, for example, $12$ stands for the number of ways to spend 5 euros in 3 days.
Examining the computed numbers for small $k$ and $n$'s, the pattern occurs.
In $k$ days we can spend $k...2k$ euros. If we spends $k+l$ this is because in some $l$ days we buy $l$ expensive candies. These candies may be one of two types.
The sum for fixed $k$ is $3^k$.
The sum for fixed $n$ is "Jacobsthal number" : see https://oeis.org/A001045 .
$0, 1, 1, 3, 5, 11, 21, 43, 85, 171...$
The recurrence $a_n = a_{n-1} + 2a_{n-2}$ is nice and simple to explain.
Exponential generating functions are not directly useful for identical objects, but for distinct, labeled objects, because passing from labeled to unlabeled is a difficult procedure.