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

Re: counting and inclusion-exclusion problems

Quote:

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

$\displaystyle |A_1\cup A_2\cup A_3\cup A_4|=$

$\displaystyle |A_1|+|A_2|+|A_3|+|A_4|-$

$\displaystyle |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|+$

$\displaystyle |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|-$

$\displaystyle |A_1\cap A_2\cap A_3\cap A_4|$

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

Re: counting and inclusion-exclusion problems

Quote:

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 $\displaystyle RRRRRGGGGGGGGNN~?$

Quote:

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.

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.

http://mathhelpforum.com/discrete-ma...d-problem.html