number of choices to put k bricks of lengths 3 on n spots

29 Views Asked by At

Consider that you have $k$ bricks of length $1$ and you want to put on a bar of length $n$. In how many ways can you organize them? The answer is simply given by: $$\binom{n}{k}$$ Now, consider that the length of each bricks are equal to $3$, in how many ways can you organize them?

1

There are 1 best solutions below

2
On BEST ANSWER

The $k$ bricks will occupy $3k$ of the $n$ spots, leaving $n-3k$ spots unoccupied. In effect you’re lining up $k$ ‘fat spots’ (bricks) and $n-3k$ ordinary spots. That’s a total of $n-2k$ objects, $k$ of which are bricks, and the bricks can be any $k$ of the $n-2k$ objects, so there are $$\binom{n-2k}k$$ possible arrangements.

For example, if $n=10$ and $k=2$ there are $\binom62=15$ possible arrangements, all of which are shown below, with $b$ for brick and $s$ for spot:

$$\begin{align*} &bbssss,bsbsss,bssbss,bsssbs,bssssb\\ &sbbsss,sbsbss,sbssbs,sbsssb\\ &ssbbss,ssbsbs,ssbssb\\ &sssbbs,sssbsb\\ &ssssbb \end{align*}$$