373 views
Let $\text{T}_{n}$ be the number of ways to arrange cars in a row with $n$ parking spaces if we can use sedans, SUVs, trucks to park such that a truck requires two spaces, whereas a sedan or SUV requires just one space each, and No two trucks are consecutively parked. (Assume that all trucks are identical, all sedans are identical, all SUVs are identical)
What is the value of $\text{T}_{7}?$
(Use the following data: $\text{T}_{1}=2 ; \text{T}_{2}=5 ; \text{T}_{3}=12$ i.e. initial conditions are already given, hence no need to compute them)

The recurrence relation for $\text{T}_{n}$ will be:
$$\text{T}_{n}=2 \text{T}_{n-1}+2 \text{T}_{n-3}$$
So, Since initial conditions are already given,
$$\text{T}_{4}=28 ; \text{T}_{5}=66 ; \text{T}_{6}=156 ; \text{T}_{7}=368.$$

Watch Complete Recurrence Relations in Discrete Mathematics  Complete Playlist to understand the concept:

1 comment

edited
Since, base cases are already given we'll directly move to discuss what will happen at $n^{th}$ position.

There are only two cases possible for $n^{th}$ position –

Case $1$ :– Parked car is not a truck.

Two options are available for $n^{th}$ position ie sedan or SUV can be parked at $n^{th}$ position. Now for the remaining $(n-1)$ positions we can park in $T_{n-1}$ ways.

$\therefore$ Number of ways to park = $2 * T_{n-1}$.

Case $2$ :– Parked car is a truck.

Truck takes $n^{th}$ and $(n-1)^{th}$ position. Now as per given conditions we cannot park another truck at $(n-2)^{th}$ position. Like case $1$, two options are available for $(n-2)^{th}$ position ie sedan or SUV can be parked at $(n-2)^{th}$ position. Now for the remaining $(n-3)$ positions we can park in $T_{n-3}$ ways.

$\therefore$ Number of ways to park = $2 * T_{n-3}$.

Therefore, recurrence relation for $T_n$ is $2 * T_{n-1} + 2 * T_{n-3}$.

Let me try to explain this :

_ _ _ _ nth: this is what we want to find.

T(n) → Truck at nth place:

→ Now we don't want a truck to be there at n-2th place because (n -2, n - 1) will be occupied by that truck

→ So, we have 2 options: ………. SUV(n-2) (Truck at nth & n-1th place) or ………………….sedan(n-2) (Truck at nth & n - 1th place) that’s why we say { 2* T(n – 3)}

→ No truck at nth place: Whatever be the arrangement of everything beyond the nth place

→ …...sedan (SUV) or …….SUV (sedan) that’s we say { 2 * T(n-1)

Which will result in total of T(n) = 2*T(n-1) + 2*T(n-3).

@shishir__roy bro im getting 409

see this

@jiren nice, I'm also getting same $408$.

just recheck your calculations for $T_7$.

@shishir__roy yeah I wrote 71 instead of 70 in T(7) my bad 😅

1
2
3