Solve the Car Dealer Problem with Generating Functions

Question

A gasoline car dealer is stopping operations in a city as part of reallocation of company resources to electric cars. It has eight identical sedan cars left in its inventory. They give an advertisement in a local newspaper announcing free distribution of remaining cars as a symbol of gratitude to their city of operation. But only five customers show up on the final day.

Can you find out the total number of ways by which one can distribute these cars to these five customers such that a given customer does not receive more than two cars but should receive at least one car.

Solution

==================================================================================================

If n identical objects are to be distributed among r persons, then no. of ways is given by:

$\begin{align*} \boxed{x_1 + x_2 + .... + x_r = n } \end{align*}$

This is equal to coefficient of $x_n$ in,
$(x^0 + x^1 + x^2 + ... + x^n) . (x^0 + x^1 + x^2 + ... + x^n) .... r \ times$

Here, identical sedans = 8, number of customers = 5.

The generating function for this particular problem is,

$\begin{align*} \boxed{x_1 + x_2 + x_3 + x_4 + x_5 = 8 \mid 1 \leq x_i \leq 2} \end{align*}$

This is the same as,
$(x^1 + x^2).(x^1 + x^2).(x^1 + x^2).(x^1 + x^2).(x^1 + x^2) = (x^1 + x^2)^5$

$[x^8]$ of $(x^1 + x^2)^5$ = $[x^8] . x^5(1 + x)^5$ = $[x^{8-5}] . (1 + x)^5$ = $[x^3] . (1 + x)^5$

Coefficients = $\binom 50 x^0 + \binom 51 x^1 + \binom 52 x^2 + \binom 53 x^3 + \binom 54 x^4 + \binom 55 x^5$

$[x^3] = \binom 53 = \frac{5!}{2!3!} = 10$

Thus, there are 10 ways in which the cars can be distributed among the customers.

Question

Solution

Subscribe to Ehan Ghalib!

Leave a Reply Cancel Reply