Questions tagged [inclusion-exclusion]

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.

3
votes
0answers
208 views

Conditions for using inclusion/exclusion principle

Suppose I have $n+1$ sets of objects, $T_0,T_1,\dots,T_n$ and that I have $n$ mappings, $\alpha_1,\dots,\alpha_n$ such that $\alpha_i(T_j) \subseteq T_{j+1}$ for all $i=1,\dots,n$ and $j=0,\dots,n-1.$ ...
1
vote
2answers
433 views

Basic inclusion exclusion problem - picking 24 balls out of four sets of 10 balls

This is probably a basic problem, but I'm having a really difficult time solving it. There are ten red balls, ten green balls, ten blue balls, and ten white balls. Balls of the same color are ...
4
votes
2answers
502 views

People being seated around a table refusing to sit next to two other people

I was going to generalize an easy counting problem and I ended up not being able to solve it: In how many ways can $n$ people $1,\dots,n$ be seated around a round table if person $i$ refuses to ...
1
vote
1answer
385 views

Combinatorics using constraints and ordered set

How would you find the number of combinations for a set of elements, where the elements have minimum and maximum values and the set is in lexicographic order. As an example: $a+b+c+d+e=635$, which ...
1
vote
2answers
140 views

Finding $\dim(A_1 + A_2 +\cdots + A_n)$ [duplicate]

Possible Duplicate: The calculation of $\dim(U + V + W)$ Given a linear space $V$ and subspaces $A_i \subseteq V$ such that $1\leq i \leq n.$ To find $\dim(A_1 + A_2 +\cdots + A_n)$ it seems we ...
0
votes
3answers
107 views

Counting travails

How many 7 digit numbers are there (no leading zero) in which the digits 6 & 9 occur together as 69 at least once. I am having difficulty in eliminating overcounting.
21
votes
1answer
611 views

Is the Maclaurin series expansion of $\sin x$ related to the inclusion-exclusion principle?

When I see the alternating signs in the infinite series expansion of $\sin x$, I'm reminded of the inclusion-exclusion principle. Could there be any way to visualize it in such a way? Also, is there ...
4
votes
2answers
379 views

Number of One to One functions such that $f(i)\neq i$

Given the sets $A=\{1,\dots,4\}$ and $B=\{1,\dots,7\}$ how many one to one functions are there from $A$ to $B$ such that $f(i)\neq i$ ? I used inclusion exclusion to first find the number of one to ...
1
vote
1answer
102 views

Arranging 3 Rows of 4 letter as triplets with restrictions

Given the following matrix: $$\begin{bmatrix} a & b & c & d\\ e & f & g & h\\ i & j & k & l \end{bmatrix}$$ how many sets of 3 letter sets using all the ...
2
votes
1answer
2k views

Number of 5 letter words over a 3 letter alphabet using each letter at least once

This is similar to my previous question, Number of 5 letter words over a 4 letter group using each letter at least once. The only difference is that there are 3 letters to choose from instead of 4. ...
3
votes
2answers
969 views

Inclusion Exclusion vs. Generating Functions

To what extent are the Inclusion Exclusion principle and Generating Functions interchangeable? Is there a general principle? For instance, I asked the following question, Number of 5 letter words ...
79
votes
9answers
9k views

100 Soldiers riddle

One of my friends found this riddle. There are 100 soldiers. 85 lose a left leg, 80 lose a right leg, 75 lose a left arm, 70 lose a right arm. What is the minimum number of soldiers losing all ...
5
votes
1answer
1k views

Complex Poker Probabilities (Texas Hold 'Em)

I've got two questions: What’s the probability that someone else has a flush, given that you have a flush? Notes: - there are four people at the table - we don't know anything about the kind of ...
1
vote
2answers
520 views

Inclusion-exclusion principle question

1st part of my question: I have that $$P\left(\bigcup_{i=1}^{{2^n-n}}E_i\right)$$ , how would I write it out using the inclusion-exclusion principle? I know it starts off: $$\sum_{i=1}^{2^n-n} P(E_i)...
6
votes
3answers
6k views

Demonstrate another way to solve the Inclusion–exclusion principle?

I'm attempting to solving the Inclusion–exclusion principle, which is generally described as follows... $$\begin{align} \left| \bigcup\limits_{i=1}^n A_i \right| = + \left( \sum\limits_{i=0}^n | ...
1
vote
2answers
875 views

non-routine application of inclusion-exclusion

What are the circumstances when inclusion-exclusion can't be routinely applied, and some adjustments have to be made ? This question arises from a problem of finding the probability of getting a ...
6
votes
1answer
389 views

Laguerre polynomials and inclusion-exclusion

Does anyone know a reference for the solution of the generalized derangement problem via Laguerre polynomials? The Wikipedia article here says that this is an application of inclusion-exclusion, but ...
16
votes
4answers
4k views

Famous uses of the inclusion-exclusion principle?

The standard textbook example of using the inclusion-exclusion principle is for solving the problem of derangement counting; using inclusion-exclusion (and some basic analysis) it can be shown that $D(...
5
votes
6answers
3k views

Ways to put numbered balls in boxes no box being empty

I know the formula for putting $n$ identical balls in $r$ different boxes such that each box has at least 1 ball, but what is the formula for putting $n$ different balls in $r$ different boxes, no box ...
1
vote
2answers
544 views

Using Inclusion-Exclusion on $n$ boys and $n$ girls

Consider a set of n boys and n girls. In each situation below, use inclusion-exclusion to derive formulas for the number of ways to partition the $2n$ people into pairs so that for each $i$ the $i$-th ...
8
votes
3answers
1k views

Combinatorics: Using Inclusion-Exclusion Principle

I'm not sure how to start this. I've been told to use inclusion-exclusion, but I don't know which properties to use. Intuitively, I want to solve the problem like this: $E_1$ = 1 person leaves stop ...
2
votes
3answers
1k views

Probability that two poker hands have no aces

The probability of no two hands from the same poker deck having no aces is $$\frac{{48 \choose 5} + {48 \choose 5} - {48 \choose 10}}{{52 \choose 5}}$$ I am not sure why this is the answer, as the ...
5
votes
2answers
4k views

When to use Inclusion Exclusion principle?

I'm a bit confused as to when you should use the Incl/Excl principle. Take for example the following problem: How many 13-card hands can be selected from the standard 52-card deck with exactly four ...
11
votes
3answers
333 views

Are the error terms of the partial sums of inclusion-exclusion unimodal?

I often teach inclusion-exclusion: $$|A ∪ B| = |A| + |B| − |A ∩ B|$$ by suggesting that $|A∩B|$ is a correction factor for $|A|+|B|$. Then I teach the three set version: $$|A∪B∪C| = |A| + |B| + |C| −...
1
vote
0answers
347 views

Number of solutions to an equation using the inclusion-exclusion principle [duplicate]

Possible Duplicate: Inclusion-exclusion principle: Number of integer solutions to equations This is a problem that I have had much trouble with. If you attempt in helping me with this, please ...
12
votes
3answers
7k views

Inclusion-exclusion principle: Number of integer solutions to equations

The problem is: Find the number of integer solutions to the equation $$ x_1 + x_2 + x_3 + x_4 = 15 $$ satisfying $$ \begin{align} 2 \leq &x_1 \leq 4, \\ -2 \leq &x_2 \leq 1, \\ 0 \leq &...
3
votes
2answers
369 views

Probability of having 'k' elements that occur only once in a multiset filled by sampling with replacement

Let's say that I have a set of unique elements, $P$, and a multiset $M$ that I fill with $N \leq ||P||$ elements by sampling with replacement from $P$. What is the probability that the multiset $M$ ...
5
votes
1answer
527 views

A question about the Inclusion-Exclusion principle

Grandma has 8 grandchildren, and 4 different types of popsicles: 6 Vanilla popsicles 6 Strawberry popsicles 5 Banana popsicles 3 Chokolate popsicles This morning, all of her grandchildren came ...