# Thread: counting and inclusion-exclusion problems

1. ## counting and inclusion-exclusion problems

Hello, I'm new member, I found this website is very helpful. I need help with 2 review problems from my discrete class, please help me, thank you.

1) Use inclusion-exclusion to find the number of 4-digit numbers with at least one 8 ( hint: let A_j = the set of all 4-digit numbers with an 8 in position i).

here is my answer : 9 x 10 x10 x10 - 8 x 9 x 9 x 9 = 3168 , I'm not sure i get it right.

2) Find the number of ways each situation below can occur:
a) A ticket office has 5 reserved seat tickets and 8 general admission tickets to sell to 15 customers.
b) Billy gets to pick 9 candy bars from the candy rack, which has Snickers,Mars,Payday, Mounds, and Crunch.

I don't know how to do part a. For part b, I got P(9,5) = 15120

2. ## Re: counting and inclusion-exclusion problems

Originally Posted by Tiome
1) Use inclusion-exclusion to find the number of 4-digit numbers with at least one 8 ( hint: let A_j = the set of all 4-digit numbers with an 8 in position i).

here is my answer : 9 x 10 x10 x10 - 8 x 9 x 9 x 9 = 3168 , I'm not sure i get it right.
Your solution is correct and is much simpler than the one that uses the inclusion-exclusion principle. Nevertheless, since the problem asks to use the principle: You need to find

$|A_1\cup A_2\cup A_3\cup A_4|=$
$|A_1|+|A_2|+|A_3|+|A_4|-$
$|A_1\cap A_2|-|A_1\cap A_3|-|A_1\cap A_4|-|A_2\cap A_3|-|A_2\cap A_4|-|A_3\cap A_4|+$
$|A_1\cap A_2\cap A_3|+|A_1\cap A_2\cap A_4|+|A_1\cap A_3\cap A_4|+|A_2\cap A_3\cap A_4|-$
$|A_1\cap A_2\cap A_3\cap A_4|$

It's pretty easy to find each of these terms.

3. ## Re: counting and inclusion-exclusion problems

Originally Posted by Tiome
2) Find the number of ways each situation below can occur:
a) A ticket office has 5 reserved seat tickets and 8 general admission tickets to sell to 15 customers.
There will be 5 who get reserved, 8 who get general and 2 who get no ticket at all.
How many ways can you rearrange the string $RRRRRGGGGGGGGNN~?$

Originally Posted by Tiome
2) Find the number of ways each situation below can occur:
b) Billy gets to pick 9 candy bars from the candy rack, which has Snickers,Mars,Payday, Mounds, and Crunch.
I don't know how to do part a. For part b, I got P(9,5) = 15120
This is a multi-selection question. We are choosing nine from five kinds.
This webpage explains the idea.

4. ## Re: counting and inclusion-exclusion problems

I got it, the link is very helpful, thank you so much.

for 2a) i did 15!/(5!*8!) = 270270
2b) C(9,5) = 9!/(5!*4!) = 126

I have one more problem that i have no idea how to do it, if you can explain and help me , that would be great, thank you.
Grid problem