## PROBABILITIES Course

# Generating function

When dealing with combinatorics, generating functions (`Fonctions génératrices`

) can make your life easier!

You will write a function, in which having $a_k * x^k$ means that

- for $n=k$
- the number of distributions is $a_k$

For instance, let's say your result is $5 x^2 + 4 x^3 + ...$ then that's means that if $n=2$ then the number of distributions is $5$...

It's usually defined like this

## Creating a generating function

If we got $k$ issues and $m$ experiments ($m = Card(X)$ for instance) then we would have

- this is a product of sums
- for each value of X (indexed by $j$)
- we calculate a sum,
- from $k_j$ (the minimum of times you want this value)
- to $n_j$ (the maximum of times you want this value)
- once you multiplied and factorized the result, $a$ in $a * x^i$ is the number of distributions for $n=i$.

You may also use the other methods as explained on these websites

## Example (1)

Let's say you are rolling two dices. You got $m=2$ and each experiment goes from $1$ to $6$, so you have $k_1=k_2=1$ (min) to $n_1=n_2=6$ (max). We will have

You can develop that easily using websites (😂) like wolframalpha.

If you are asked the number of issues/the cardinal

- when the sum is $7$ then it's $6$
- when the sum is $8$ then it's $4$
- ...

Okay, you could actually find that yourself like for the $sum=7$ then we have $(1,6),\ (2,5),\ (3,4)$ so that's 6 (without the order like $1+6=6+1$), but a generating function is scalable and that was not that hard (aside from developing the function 😬).

## Example (2)

You have $n=12$ cakes (chocolate, vanilla, strawberry),

- each person must have
**at least two flavors** - and they
**can't have chocolate more than 4 times**

Since we need "at least two", then $k_1=k_2=k_3=2$. Aside from $n_1$, we don't have restrictions on vanilla/strawberry, so $n_2=n_3=12$. As for chocolate, $n_1=4$ (since "up to" 4).

is evaluated (using wolframalpha 😶) as

@ x^{28} + ... + 18 x^{12} + ... + x^6 @

So we have 18 ways of distributing our cakes (since $n=12$). If $n=6$ then it would be 1, etc.