Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is a practice question. I understand Inclusion and Exclusion but I am having a terrible time setting questions up correctly.

This is on of the practice questions in the text.

At a flower shop they want to arrange $15$ different plants on five shelves for a window display. In how many ways can they arrange them so that each shelf has at least one, but no more than four plants ?

My understanding is that the equation would be of the form $x_1+x_2.....+x_5=15$ where $1 \le x_i \le 4$ but then we modify it so that it is $y_1+y_2+y_3...+y_5=15-5$ where $0 \le y_i \le 4$

$|S|= \binom{5+10-1}{10}$ and $N(c_i)= \binom{5+5-1}{5}$ where $1 \le i \le 5 $ so $|S_1|=5* \binom{5+5-1}{5}$

Am I setting this up correctly. Please note I am very new to the subject of inclusion and exclusion.

share|improve this question
    
Since the plants are different, you want to use permutations, instead of the stars and bars. –  Calvin Lin Jul 25 '13 at 12:19

2 Answers 2

The way inclusion-exclusion can be used here is: for each subset $S$ of $\{1,2,3,4,5\}$ (representing the shelves) let $N_S$ be the number of ways to do the arrangement if the shelves in set $S$ are required to be empty (the other shelves may or may not be empty). Write the number of arrangements where at least one shelf is empty in terms of these, using the Inclusion-Exclusion formula.
Subtract from the total number of arrangements, and you have the number where no shelf is empty.

share|improve this answer
    
Note that because we have the restriction that no shelf may have more than 4 plants, we need to use either 4 or 5 shelves. –  Calvin Lin Jul 25 '13 at 12:19
    
Thanks for the answer but I am little confused. So I would be looking at the total number of ways 15 plants can be a arranged on 5 shelves which is $15C5$ and then I would subtract the total number of ways no plant is on either of the shelves and then subtract the number of ways more than 4 plants would be on either of the shelves (not sure how to do this part), but then I have to add those possibilities where some shelves have no pot and simultaneously other shelves have more than 5 pots as they may have been double counted. Am I right ? –  Kj Tada Jul 25 '13 at 19:56
up vote 0 down vote accepted

So had to go through the basics again but I figured it out. The answer is

$15![(\binom{5+10-1}{10})-(\binom{5}{1})(\binom{5+6-1}{6})+(\binom{5}{2})(\binom{5+2-1}{2})]$

main Principles used are Inclusion and exclusion, Combination with Repetition.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.