# Principle of Inclusion and Exclusion

Annually, the 65 members of the maintenance staff sponsor a “Christmas in July” picnic for the 400 summer employees at their company. For these 65 people,

• 21 bring hot dogs,
• 35 bring fried chicken,
• 32 bring desserts,
• 13 bring hot dogs and fried chicken,
• 10 bring hot dogs and salads,
• 9 bring hot dogs and desserts,
• 12 bring fried chicken and salads,
• 17 bring fried chicken and desserts,
• 14 bring salads and desserts,
• 4 bring hot dogs, fried chicken, and salads,
• 6 bring hot dogs, fried chicken, and desserts,
• 5 bring hot dogs, salads, and desserts,
• 7 bring fried chicken, salads, and desserts, and
• 2 bring all four food items.

Those (of the 65) who do not bring any of these four food items are responsible for setting up and cleaning up for the picnic. How many of the 65 maintenance staff will

(a) help to set up and clean up for the picnic?

(b) bring only hot dogs?

(c) bring exactly one food item?

What I have so far is:

• $c_1=$ Staff members who bring hot dogs
• $c_2=$ Staff members who bring fried chicken
• $c_3=$ Staff members who bring salads
• $c_4=$ Staff members who bring desserts

$$N=65$$ $$N(c_1)=21,\quad N(c_2)=35,\quad N(c_3)=28,\quad N(c_4)=32$$ $$N(c_1c_2)=13,\quad N(c_1c_3)=10,\quad N(c_1c_4)=9,\quad N(c_2c_3)=12,\quad N(c_2c_4)=17,\quad N(c_3c_4)=14$$

Am I on the right track or way off course?

-
Offtopic, but I couldn't help thinking of this... youtube.com/watch?v=On7U-x_s_EE – SJuan76 Jun 17 '13 at 15:32
What you have done is just writting the problem description in a different, more algebraic form... what do you plan to do from here? – SJuan76 Jun 17 '13 at 16:00
a) N(c1c2c3c4)= 65-[21+35+38+32]+[13+10+9+12+17+14]-[4+6+5+7]+2 65-116+75-22+2= 4 for the 1st part.. does this sound correct – Dale Bryant Jun 17 '13 at 16:15
You know from the problem description that $N(c1c2c3c4)=2$ – SJuan76 Jun 17 '13 at 16:19
Right.. I mispasted the first part... I couldn't get the - accents above the c1c2c3c4... (b) bring only hot dogs? N(c ̅_2 c ̅_3 c ̅_4 )=N-[N(c_2 )+N(c_3 )+N(c_4 )]+[N(c_2 c_3 )+N(c_2 c_4 )+N(c_3 c_4 )]-N(c_2 c_3 c_4 ) N(c_1 c ̅_2 c ̅_3 c ̅_4 )=N(c_1 )-[N(c_1 c_2 )+N(c_2 c_3 )+N(c_1 c_4 )]+[N(c_1 c_2 c_3 )+N(c_1 c_2 c_4 )+N(c_1 c_3 c_4 )-N(c_1 c_2 c_3 c_4 ) 21-[13+10+9]+[4+6+5]-2 21-32+15-2=2 See how the accents paste in.. – Dale Bryant Jun 17 '13 at 16:25

You need to complete the list and apply the formulas, but you seem to be on the right track.

Using the Generalized Principle of Inclusion-Exclusion, we compute:

$N(0)=65$
$N(1)=21+35+28+32=116$
$N(2)=13+10+9+12+17+14=75$
$N(3)=4+6+5+7=22$
$N(4)=2=2$

$65\binom{0}{0}-116\binom{1}{0}+75\binom{2}{0}-22\binom{3}{0}+2\binom{4}{0}=4$ bring nothing
$\hphantom{65\binom{0}{1}-}116\binom{1}{1}-75\binom{2}{1}+22\binom{3}{1}-2\binom{4}{1}=24$ bring one item
$\hphantom{65\binom{0}{1}-116\binom{1}{1}+}75\binom{2}{2}-22\binom{3}{2}+2\binom{4}{2}=21$ bring two items
$\hphantom{65\binom{0}{1}-116\binom{1}{1}+75\binom{2}{2}-}22\binom{3}{3}-2\binom{4}{3}=14$ bring three items
$\hphantom{65\binom{0}{1}-116\binom{1}{1}+75\binom{2}{2}-22\binom{3}{3}+}2\binom{4}{4}=2$ bring four items

Counting only people who brought hot dogs (and possibly other items):

$N(0)=21+0+0+0=21$
$N(1)=13+10+9+0+0+0=32$
$N(2)=4+6+5+0=15$
$N(3)=2=2$

$21\binom{0}{0}-32\binom{1}{0}+15\binom{2}{0}-2\binom{3}{0}=2$ bring nothing else (just hot dogs)
$\hphantom{21\binom{0}{1}-}32\binom{1}{1}-15\binom{2}{1}+2\binom{3}{1}=8$ bring one item (in addition to hot dogs)
$\hphantom{21\binom{0}{1}-32\binom{1}{1}+}15\binom{2}{2}-2\binom{3}{2}=9$ bring two items (in addition to hot dogs)
$\hphantom{21\binom{0}{1}-32\binom{1}{1}+15\binom{2}{2}-}2\binom{3}{3}=2$ bring three items (in addition to hot dogs)

a) $4$ people brought nothing
b) $2$ people bring only hot dogs
c) $24$ people bring only one food item