2
$\begingroup$

Studying for the midterm. Trying to solve the following problem:

There are $8$ zoos in the City. During the next $13$ weeks, each week Benny wants to visit one zoo. Count the number of possibilities so Benny visited each zoo at least once and at most three times.

What I did: I want to fulfill the "at least one" request. So let's choose $8$ weeks in ${13 \choose 8}$ possibilities. Then I arrange the $8$ zoos in $8!$ possibilities. Now I left with $5$ additional weeks that should be filled with the zoos. But how can I fulfill the "at most three times"?

$\endgroup$
8
  • $\begingroup$ Some of the possible approaches: Approach1: find cases - if all $8$ zoos must be visited and no zoo more than $3$ times, how many cases are there? One of them for example is two zoos visited $3$ times, one zoo $2$ times and rest of the zoos $1$ time each. Approach2: use generating function. Approach3: use Principle of Inclusion Exclusion. $\endgroup$
    – Math Lover
    Commented Nov 28, 2021 at 13:40
  • $\begingroup$ @MathLover In this particular case, there are only three potential patterns so your approach 1 may be easiest $\endgroup$
    – Henry
    Commented Nov 28, 2021 at 13:52
  • $\begingroup$ @Henry yes even I think approach $1$ is easiest $\endgroup$
    – Math Lover
    Commented Nov 28, 2021 at 13:55
  • $\begingroup$ Thank you for the comments. How Principle of Inclusion Exclusion can be used here? $\endgroup$
    – vesii
    Commented Nov 28, 2021 at 13:56
  • $\begingroup$ I tried to use the Principle of Inclusion Exclusion and this is what I got: $E(0)=W(0)-W(1)+W(2)-W(3)=8^{13}-{13 \choose 1 }13\cdot7^{12}+{13 \choose 2}0.5\cdot13\cdot12\cdot6^{11}-{13 \choose 3}\frac{1}{6} 13\cdot 12\cdot 11 \cdot 5^{10}$. Is it correct? $\endgroup$
    – vesii
    Commented Nov 28, 2021 at 14:04

1 Answer 1

Reset to default
5
$\begingroup$

@Math Lover gave you all possible ways. I want to solve this question using $2$ approach ,i.e generating functions.

Let assume that we align all $13$ weeks in a row such that $$-,-,-,-,-,-,-,-,-,-,-,-,-$$

The first line means the first week , the second line means second week so on.

We want to put these $8$ distinct zoos to these lines with obeying the given restriction.For example , one of the possible visiting order is : $$1,3,5,5,7,8,6,1,1,3,4,4,4$$ where each number represent one of these $8$ zoos. This arrangements tells us we visit first zoo in first week , visit third zoo in second week etc.We could also arrange them like $$3,1,5,5,6,8,7,1,3,1,4,4,4$$

As you realize we are making permutation with repetition like the questions asking "how many possible words are there using the letters of MISSISSIPI". However , we have an hindrance here such that the number of visiting zoos range from $1$ to $3$.

Then , exponential generating functions comes to help !

For given restrictions E.G.F. of each zoo is equal to: $$\bigg(x + \frac{x^2}{2!}+ \frac{x^3}{3!}\bigg)$$

Realize that $x$ means given zoo is visited once , $x^2$ means given zoo is visited twice , $x^3$ means given zoo is visited three times.

Then , we should find the coefficient of $x^{13}$ and multiply it by $13!$ or find the coefficient of $\frac{x^{13}}{13!}$ in the expansion of $$\bigg(x + \frac{x^2}{2!}+ \frac{x^3}{3!}\bigg)^{8}$$

So $$13! \times \frac{119}{12} =61.751.289.600$$ ways there are

$\endgroup$
2
  • $\begingroup$ Is it possible to explain how did you get $\bigg(x + \frac{x^2}{2!}+ \frac{x^3}{3!}\bigg)$? $\endgroup$
    – vesii
    Commented Nov 28, 2021 at 18:04
  • $\begingroup$ @vesii It may not be much possible , i recommend you to read about it to understand deeply , it is completely about the core of exponential generating function. I am putting a beginner level book Look at related chapter in this book $\endgroup$
    – Not a Salmon Fish
    Commented Nov 28, 2021 at 18:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .