The inclusion-exclusion principle states that the number of elements in the union of two given sets is the sum of the number of elements in each set, minus the number of elements that are in both sets.

learn more… | top users | synonyms

-1
votes
1answer
51 views

Intermediate Counting Question

Two Americans, two Canadians, two Mexicans, and two Jamaicans are seated around a round table. People from the same country are distinguishable. In how many ways can all eight people be seated such ...
0
votes
1answer
20 views

Finding number of combinations for similar items

I have 4 types of popsicle colors: Red, white, yellow, green. In the grocery store, there's 11 popsicles of each type, all together 44 popsicles. I need to find the number of combinations for choosing ...
3
votes
1answer
26 views

Counting problem involving candy and overcounting

I have $40$ chocolates, $29$ gumdrops, and $38$ lollipops. Why is it that the total number of ways to select $41$ candies from this set is: $$\binom{41+3-1}{3-1} - \binom{0 + 3 - 1}{3 - 1} - ...
3
votes
1answer
59 views

Are there further transformation principles similar to the Inclusion-Exclusion Principle (IEP)?

This question is motivated by the elaboration of the question Combinatorial Proof of Inclusion-Exclusion Principle (IEP). Let's consider the following two aspects: 1.) IEP transforms at least ...
0
votes
1answer
37 views

Combinatorics: help with the Inclusion-exclusion principle

$A=\{1,2,3,4\}$ $B=\{5,6,7,8,9\}$ $K$ is a relation from $A$ to $B$ ($K\subseteq AXB)$ in how many $K$'s - $1 \notin domain(K)$ ? in how many $K$'s - $\{1,2,3\}\subseteq domain(K)$ (use the ...
0
votes
2answers
45 views

Lower bound on union of finite sets (inclusion-exclusion principle)

I have the following problem emerged. Let's say we have $l$ finite sets $A_1, A_2, \ldots, A_l$ with cardinality of $n_1, n_2, \ldots\, n_l$, respectively. We know that $| A_i \cap A_j | \le a_{ij}$ ...
1
vote
0answers
36 views

Deriving the formula for derangements: $\text{Round}\left[\frac{n!}{e}\right]$ [duplicate]

I saw on wikipedia that a formula for derangements is $\text{Round}\left[\frac{n!}{e}\right]$ However, how did they arrive at this elegant formula? Does it have to do with $ !n=n! \sum _{k=0}^n ...
1
vote
1answer
54 views

MathCounts 1993 National Sprint #28

Here is the problem: In a small town of 100 men, 85 are married, 70 have a telephone, 75 own a car, and 80 own their own home. On this basis, what is the smallest possible number of men who are ...
1
vote
1answer
25 views

List 4 partitions of the alphabet containing 3 sets. How many different partitions can be made?

The first part of the question is easy; there are many right answers but I put down: $$(a), (b), (c..z)$$ $$(a,b), (c), (d..z)$$ $$(a,b,c), (d), (e..z)$$ $$(a,b,c,d), (e), (f..z)$$ The part I am not ...
4
votes
3answers
225 views

# of counts of an element - Combinatorial Proof of Inclusion-Exclusion Principle (IEP) [Ross P31]

Let $A_{1},\ A_{2}$, , $A_{n}$ be $n$ sets. Then $|A_{1}\cup A_{2}\cup ... \cup A_{n}|= \sum_{i}|A_{i}|-\sum_{i<j}|A_{i}\cap A_{j}|+ \cdots + (-1)^{n-1}|A_{1}\cap A_{2}\cap\ \cap A_{n}|. $ ...
1
vote
0answers
23 views

Divisibility via Inclusion-Exclusion

Let $N$ be a large natural number, let $A$ be a subset of naturals, and ask: How many numbers $n\leq N$ are divisible by one or more numbers in $A$. This is a classical application of the ...
0
votes
0answers
36 views

How many ways can this quadrilateral be formed if no two of its vertices are next to each other?

A quadrilateral is formed by joining four vertices of a convex decagon. In how many ways can such a quadrilateral be formed if no two of its vertices are next to each other (that is, no two vertices ...
0
votes
0answers
26 views

Inclusion/Exclusion Probability for Devices

I'm having a hard time understanding the inclusion/exclusion principle. I was wondering if someone could help me out with this simple problem. Each of seven jobs in a computer system requests one ...
1
vote
1answer
49 views

Inclusion-exclusion principle: finding the number of solutions

Given the equation $\begin{cases} x_1+x_2+x_3+x_4 =18\\ 0\leq x_i\leq 7 \text{ with } x_i \in \mathbb{N} \text{ and } 1\leq i\leq 4 \end{cases}$ how do I calculate the number of solutions with the ...
0
votes
0answers
33 views
0
votes
2answers
40 views

Distributing different toys

Find the number of ways in which 12 different toys may be distributed among 4 children so that each child gets at least 2 toy.
0
votes
2answers
37 views

The attendance at a school party is 17, 12,16, 14, 20, for Monday thru Friday. ..

The logics for this question is quite hard for me. I hope someone could help. The attendance at a school party is 17, 12,16, 14, 20, for Monday thru Friday. What's the least number of student the ...
1
vote
2answers
46 views

Inclusion/Exclusion Principle for indistinguishable balls into two different types of boxes

The problem asks me how to distribute n balls into h boxes where each must get at least 1 n and t boxes where each can be left empty What I have, and where I seem to have stalled is how to ...
3
votes
0answers
52 views

Proving the inclusion exclusion principle from the definition of the cardinality

I want to prove the inclusion exclusion principle: $|A\cup B| = |A| + |B| - |A\cap B|$ where $A$ and $B$ are finite sets. I proved the addition rule by contructing a bijection to a subset of ...
1
vote
1answer
59 views

Determining number of solutions with inclusion-exclusion

NOTE: I know there are similar questions to this, but the ones on this website are much more complex, and I'd like to get a basic understanding before moving on to them. Please do not mark this as a ...
0
votes
1answer
45 views

Finding the number of onto maps from $A = \{1,2,3,4,5\}$ to $B = \{a,b,c\}$

I'm trying to catch up in my discrete math class right now and I came across a practice question: Use inclusion-exclusion to find the number of onto maps from $A = \{1,2,3,4,5\}$ to $B = ...
2
votes
1answer
60 views

Inclusion and Exclusion Word Problem: Discrete Math

I am having trouble understanding how to solve this question: Some five courses are offered in a semester. The group of students who take at least one of these courses consists of 155 students. ...
3
votes
3answers
327 views

Prove: Number of Derangement is odd if and only if number of items is even .

let $D_n$ be a number of Derangement of n items . prove that $D_n$ is odd if and only if n is even . i was trying to use induction on the $!n=(n-1)(!(n-1)+!(n-2))$ recurrence relation but i cant ...
2
votes
0answers
43 views

We are giving $m$ prizes to $n$ people at lottery…

We are giving $m$ prizes to $n$ people at lottery... Question A: What is the probability that no one will get more then one prize (assume that $n\ge m$). Question B: What is the probability the ...
1
vote
1answer
41 views

Help with using the “Inclusion–exclusion principle”

I have question at probability that I need to use the "Inclusion–exclusion principle"... Hand of bridge is 13 cards that picked up randomly. What is the probability that we will have a King and Ace ...
0
votes
1answer
35 views

Number of k-permutations that have odd number of an element

I want to find a recurrence relation $h_k$ for the number of k-permutations of $\{\infty a,\infty b, \infty c, \infty d \}$ that have an odd number of a's. I let $h_0=0$ because there is no odd ...
0
votes
1answer
58 views

How many permutations of the sequence 1, 2, 3…N where none of the first K numbers in the original sequence is in it's place?

For the sequence 1, 2, 3 ... N there are of-course N! permutations. But for a given K, where 1 < K ≤ N how many permutations are there given none of ...
0
votes
1answer
93 views

In how many ways can the Letters of the Alphabet be permuted such that it does not contain CAR,DOG,PUN,BYTE

Im using the principle on inclusion and exclusion to solve this There are 4 cases C1,C2,C3 ,C4 respectively So taking the case where CAR DOG and BYTE comes together ...
0
votes
2answers
43 views

Principle of Inclusion and Exclusion

Im trying to derive $N(A\cup B\cup C)$ with the help of Venn Diagram. $$|A\cup B\cup C| = |A| + |B| + |C| - |A\cap B| - |B\cap C| - |A\cap C| + |A\cap B\cap C|$$ I have reached the step where ...
4
votes
2answers
249 views

A die is thrown five times, what is the probability that you get 20 as the sum of the values

This is supposed to be a Inclusion-Exclusion problem. We have $6^5=7776$ different results. Now, with the Inclusion-Exclusion principle i resolve the number of solutions for the equation: ...
0
votes
0answers
44 views

Explicit formula for inclusion/exclusion

I've been searching for a formula for the cardinality of the union of $n$ sets but all the formulas I can find incorporate the symbol (...) and summations that have limits of the form ...
5
votes
1answer
114 views

We have a $n \times m$ grid. How many ways to put $p$ points on it, so that every column and row had at least one point.

We have a $n \times m$ grid. How many different ways can we put $p$ coins on it, so that every coin was in a unique cell in the grid, and every column of the grid and every row had at least one coin. ...
2
votes
1answer
49 views

Combinatorics - inclusion exclusion, check my answer

It's my second try to solve the question I posted here Combinatorics question - How many different ways to change sitting order I got some really good advice, but no one said the answer, I solved it, ...
1
vote
3answers
64 views

In how many ways can one distribute ten distinct pizzas among four students with exactly two students getting nothing?

In how many ways can one distribute ten distinct pizzas among four students with exactly two students getting nothing? How many ways have at least two students getting nothing? For the first part I ...
2
votes
3answers
96 views

What is the number of ways to represent the $n$ element set as a union of distinct non-empty subsets

edit: I do not mean the number of partitions $B_n$ here. The title says it all. The n element set is $[n]=\{1,2,\dots,n\}$. One representation (the one using the most sets) for example is the union ...
1
vote
1answer
80 views

Generalization of principle of inclusion and exclusion (PIE)

The PIE can be stated as $$|\cup_{i=1}^n Y_i| = \sum_{J\subset[n], J\neq \emptyset} (-1)^{|J|-1} |Y_J|$$ where $[n]=\{1,2,...,n\}$ and $Y_J=\cap_{i \in J} Y_i$. Problems using it are usually reduced ...
1
vote
5answers
202 views

How many permutations of {1,2,…, 9} are there that do not start or end with an even number?

How many permutations of $$1,2,..., 9$$ are there that do not start or end with an even number? This is my attempt Condition 1 [Starts with even] => $$4 * 8!$$ Condition 2 [Ends with even] => $$4 * ...
0
votes
2answers
97 views

Determine the number of positive integer x where x<= 9,999,999 and the sum of the digits in x equals 31.

Determine the number of positive integer x where $$x\le 9,999,999$$ and the sum of the digits in x equals 31 How do you approach this question? TEXTBOOK SOLUTION: Let x be written in base ...
1
vote
2answers
50 views

Number of solutions to equation - is there a better way of solving this than inclusion-exclusion?

We are asked to find the number of solutions for $a+b+c+d+e+f=20$ when $2 \leq a,b,c,d,e,f \leq 6$ Is there a better way of solving it than what I did ? because it an exam, this seems like a very ...
0
votes
1answer
130 views

When to use inclusion exclusion principle in solving combinatorics problems

I am just learning about the inclusion exclusion principle while studying basic combinatorics. But I'm finding it extremely difficult to solve problems involving the inclusion exclusion principle ...
0
votes
2answers
331 views

In a survey of 270 college students, it is found that 64 like brussels sprouts

In a survey of 270 college students, it is found that 64 like brussels sprouts, 94 like broccoli, 58 like cauliflower, 26 like both brussels sprouts and broccoli, 28 like both brus- sels sprouts and ...
1
vote
1answer
57 views

A marketing report concerning personal computers/Inclusion–Exclusion

A marketing report concerning personal computers states that 650,000 owners will buy a printer for their machines next year and 1,250,000 will buy at least one software package. If the report states ...
2
votes
1answer
112 views

Question on Principle of Inclusion Exclusion

In how many ways can we seat 3 pairs of siblings in a row of 7 chairs, so that nobody sits next to his or her sibling? [One chair will be empty] I got that there are $7!$ ways of seating ...
3
votes
1answer
73 views

Example of a matrix with a gersgorin disk that does not contain any eigenvalue

I am looking for an example of a matrix $A\in\mathbb{C}^{n\times n}$ with the property that at least one Gersgorin Disk $\Gamma_i$ contains no eigenvalue of $A$ for a non-empty proper subset $S$ ...
3
votes
2answers
57 views

Numer of possibilities of placing people of different nationalities

How many ways of sitting 3 people of nationality A, 3 of nationality B and 3 of nationality C there are if no two people of the same nationality can sit near each other (so such placings are ...
0
votes
1answer
54 views

Probability of specific result of dice rolling using inclusion-exclusion principle

I have two dices and I roll them ten times. What's the probability that I will throw all pairs (i,i), where i=1,...,6 at least once? I would appreciate any kind of help and hints!
1
vote
1answer
41 views

ordering 3 couples in 3 rows

I have the following question: ...
0
votes
2answers
85 views

Intuitive understanding of inclusion exclusion principle

I am finding it very difficult to understand the inclusion exclusion principle and how to apply it in even simple combinatorics problems. Can someone please supply the intuition behind this principle ...
0
votes
3answers
37 views

Inclusion-Exclusion proof for two sets

I know this might sound silly but, it's easy to convince myself that $|A\cup B|=|A|+|B|-|A\cap B|$ but i'm not sure how i would go about proving it. Suppose $A'=A\setminus\{a\}$ and $|A|=n+1$ for ...
2
votes
0answers
40 views

Combinatorics - find $n!$ using inclusion-exclusion [duplicate]

difficult question I need help with. We are asked to show that $n! = \sum_{k=0}^n (-1)^k\binom{n}{k}(n-k)^n$ There is also a hint "try to think of the number of permutations of n elements using ...