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

0
votes
1answer
25 views

Problem on Inclusion & Exclusion Principle

Book has the following & solution to it too, pls clear my confusion: On rainy day , five gentlemen A, B, C,D, E attend a party after leaving their umbrellas in a checkroom. After the party is ...
0
votes
0answers
22 views

Inclusion-Exclusion principle for n events [on hold]

Adam's database of friends contains n entries, but due to a software glitch, the addresses correspond to the names in a totally random fashion. Alvin writes a holiday card to each of his friends and ...
2
votes
1answer
33 views

Probability - Combinations

I am having big problems with this exercise: There are $n$ customers and $k$ types of products and number $i$, where $n \ge k \ge i$. I have to find the probability of the situation where ...
0
votes
1answer
25 views

How to get this complementary form of derangement written in a Wikipedia article?

In this article, how do they get the complementary form of $$\Big|S\setminus\bigcup_{i=1}^{n}A_i\Big|=\sum_{k=0}^{n}(-1)^k\binom{n}{k}\alpha_k$$ from ...
1
vote
1answer
42 views

Related problem to covering a circle with random arcs

I have a problem setup wherein we have (the following are all integers) a sequence of length $G$, and $N$ reads of length $L$. I'm interested in the problem where we consider the sequence to be ...
2
votes
3answers
80 views

Inclusion–Exclusion Identical Computers Problem

Find the number of ways to distribute 19 identical computers to four schools, if School A must get at least three, School B must get at least two and at most five, School C get at most four, and ...
0
votes
0answers
37 views

Using the Inclusion-Exclusion Principle

I'm having some trouble with the following homework problem: Given that $A_1, A_2, ..., A_n$ are some collection of subsets of S, and no element of S lies in more than two of these sets, write an ...
3
votes
2answers
48 views

Combinatorics - Number of Paths in a Grid with a Hole

Given a $12\times12$ grid with a hole of $4\times4$ in its middle, how many short paths (right or up only) are there from $(0,0)$ to $(12,12)$. I tried using inclusion-exclusion by counting the ...
5
votes
1answer
51 views

How many $5$ card poker hands contain at least $1$ red and $1$ black card?

How many $5$ card poker hands contain at least $1$ red and $1$ black card? I used inclusion-exclusion to calculate my answer. The number of total poker card hands are:$$52\choose 5$$I have $26$ red ...
-1
votes
0answers
233 views

Find the number of arrays with coprime entries

I want to find the number of arrays of size $N$ and with elements $1 \le A_i \le M$, where $(A_i)_{1 \le i \le N}$ are the elements of the array, such that $\gcd(A_i, A_j) = 1$ for each pair $A_i, ...
1
vote
2answers
36 views

Minimizing the intersection of three sets

Let the sets $A,B,C$ which are all subsets of a larger set $N$. If $N(A), N(B), N(C), N$ are the populations respectively, then i need to find the minimum value of the population of their intersection ...
1
vote
2answers
52 views

The inclusion and exclusion criteria

I've learned that in probability course, in the exercise we are asked to prove that: given $n$ sets $A_1,\ldots,A_n$, $$ \left|\bigcup_i A_i\right| \ge \sum_i|A_i| - \sum_{i\ne j}|A_i\cap A_j|\;.$$ ...
1
vote
1answer
68 views

Luis Suarez goalscoring record.

Problem: The $2013-14$ season was a short-lived ray of hope in an otherwise long dark night for the world’s greatest football team. The team played $38$ league games and the main contributing ...
1
vote
1answer
61 views

How many ways to arrange these gifts? (Inclusion-exclusion\derangement)

Each one of 30 people has bought 2 identical presents for the poor (every person's gifts are different from everyone else's). All the gifts were put in a large bag. In turns, 30 poor people ...
0
votes
2answers
96 views

Inclusion - Exclusion Problem - Suppose that a person with seven friends…

Can someone please explain to me how to approach this problem: Suppose that a person with seven friends invites a subset of three friends to dinner every night for one week (seven days). How many ...
1
vote
1answer
77 views

How many ways are there to order a subset of 30 such tickets with the constraint that each of the eight musicals appears on at least one ticket?

There are 8 Broadway musicals and they offer a special three-night package (Friday, Saturday, Sunday nights) where one can order one ticket that is good for 3 different musicals on successive nights ...
0
votes
1answer
27 views

Chances for $3$ 6-sided die and $2$ 8-sided die to have a sum of $12$

If $5$ dice are rolled, $3$ 6-sided die and $2$ 8-sided die, how do I come up with the chances that the sum will be $12$? I've figured that there are $13824$ total combinations, but can't figure out ...
1
vote
0answers
12 views

Calculating the number of permutations that do not have at least one set of duplicate elements adjacent.

Ok, so I've got a set of elements, some are duplicates but each are considered unique as far as set-making goes. I need to find how many permutations exist that do not put two of the duplicates next ...
-2
votes
0answers
18 views

Principle of Inclusion/Exclusion (PIE) Homework Help [duplicate]

Prompt Suppose Sue is a Mail Carrier who is crazy. He likes to ensure that none of the n houses on his delivery route get the mail they are supposed to. Your goal, should you choose to accept it, for ...
1
vote
2answers
146 views

Prove an identity in a Combinatorics method

It is a combinatorics proof. Anyone has any idea on how to prove $$\sum \limits_{i=0}^{l} \sum\limits_{j=0}^i (-1)^j {m-i\choose m-l} {n \choose j}{m-n \choose i-j} = 2^l {m-n \choose l}\;$$ We ...
3
votes
3answers
102 views

How many $5$-digit numbers (including leading $0$'s) are there with no digit appearing exactly $2$ times?

How many $5$-digit numbers (including leading $0$'s) are there with no digit appearing exactly $2$ times? The solution is supposed to be derived using Inclusion-Exclusion. Here is my attempt at a ...
3
votes
2answers
45 views

What is probability that out of the first half on N objects, none will be matched with their own label?

The problem: We have N (even) objects ordered $o_1 ... o_N$ , each having their own label. The labels are reassigned to the objects randomly. What is the probability that that neither of the first ...
2
votes
2answers
42 views

Counting the number of ways (variants)

I'm learning about combinatorics and wanted to see if I understand when to apply what methods when it comes to counting the number of ways to distribute x items. There are a lot of concepts I've ...
0
votes
0answers
10 views

Pseudoinverse: proving certain relation involving ranges

Suppose $A$ a linear transformation and $A^+$ its Moore-Penrose pseudoinverse. At this stage of the derivation in a book I am using as a reference, the operator $AA^+$ is known to be an orthogonal ...
1
vote
2answers
70 views

Setting up an inclusion-exclusion question

What is the number of one-to-one functions $f$ from the set $\{1,2,...,n\}$ to the set $\{1,2,...,2n\}$ so that $f(x) \neq x$ and $f(x) \neq 2n - x + 1$ for all $x$? I'm getting that the number of ...
3
votes
1answer
47 views

Painting a 2x2 Grid

We have a 2x2 grid and 10 different colours. I want to paint such that adjacent grids are painted with different colors. How many ways can i do this? ...
0
votes
0answers
19 views

Inclusion/exclusion argument for partitions

My question regards Frobenius partitions, or $F$-partitions for short, of a number $n$. A short explanation of the concept is linked below. Specifically, my question is as follows. $F$-partitions of ...
1
vote
2answers
17 views

Question about the exclusive or operator

Let $R_1$ be the “less than” relation on the set of real numbers and let $R_2$ be the “greater than” relation on the set of real numbers, that is, $R_1 = \{(x, y) | x < y\}$ and $R_2 = \{(x, y) | x ...
3
votes
1answer
41 views

Using the principle of inclusion-exclusion determine the number of prime numbers not exceeding 100.

Using the principle of inclusion-exclusion determine the number of prime numbers not exceeding 100. How would you approach this problem?
0
votes
0answers
35 views

Finding a probability, related to sets of permutations

Let $\Omega$ be the collection of permutations of the set $\{1,2,...,n\}$ with the normalised counting measure: $$P(A) = \dfrac{\text{ number of permutations belonging to A }}{n!}$$ For each $i$, let ...
2
votes
1answer
51 views

Probability of being able to make a given number with two out of xd6

I'm an amateur games designer, and am working on a mechanic which involves rolling on a table with numbers running from 2-12 - the full range of possibilities from adding together two six-sided dice. ...
3
votes
2answers
66 views

Distinguishable and indistinguishable objects in distinguishable containers

My question is rather simple, but I can't seem to figure out how to provide an answer. There are 5 distinguishable toys and 7 indistinguishable sweets that we try to give to 4 distinguishable ...
0
votes
0answers
26 views

Textbook's reference - Euler Totient's function (proof/derivation by the use of inclusion-exclusion princple)

Wonder, in which textbooks is a proof/derivation of formula of Euler's totient function by the use inclusion-exclusion principle from combinatorial analysis. Putting references below this post very ...
3
votes
2answers
448 views

combinatorics - why my reasoning is wrong?

we have 22 balls (5 red, 7 green and 10 blue). i wrote this as an anwser to the question : what is the probability to get 3 colors when picking 8 balls at once ? $$\frac{C_5^1 * C_7^1 * ...
2
votes
2answers
61 views

Combinatorics - Number of ways to fill a 3x3 grid with 0's and 1's such that there is at least one zero in each column and row

There seems to be a simple answer for this problem, but I just can't figure it out. I know there must be at least 3-9 zeros for a valid arrangement, and that there are $3!$ (6) possible combinations ...
3
votes
1answer
23 views

Calculate number of elements of $\mathcal{P}(\mathcal{P}(M))$ whose elements themselves are cover ing M

Given a set M. Can I easily calculate the number of elements $S_i \in \mathcal{P}(\mathcal{P}(M))$ such that $\bigcup\limits_{s \in S_i}s = M$? For example, $M = \{A,B\}$. Then the number of ...
0
votes
3answers
84 views

In how many ways can the four walls of a room be painted with three colours so that no two adjacent walls have the same colour?

In how many ways can the four walls of a room be painted with three colours so that no two adjacent walls have the same colour ? I specifically want to use inclusion exclusion principle. So ...
8
votes
1answer
145 views

Counting the number of rank $r$ binary $n \times k$ matrices that has unique columns

I'm trying to figure out how many ways there are to construct a $k \times n$ binary matrix such that it has rank $r$ and no column is repeating. I've tried a bunch of different approaches. The attempt ...
1
vote
2answers
95 views

How many ways are there to assign $20$ different people to $3$ different rooms with at least $1$ person in each room?

How many ways are there to assign $20$ different people to $3$ different rooms with at least $1$ person in each room? I know how to approach this problem using combinations:$$17!\cdot {3 \choose ...
1
vote
2answers
53 views

Inclusion-exclusion principle of professors liking $3$ different games

Suppose $60$% of all college professors like tennis, $65$% like bridge, and $50$% like chess; $45$% like any given pair of recreations:a) Should you be suspicious if told that $20$% like all three ...
0
votes
2answers
44 views

What is the probability that a $5$ card poker hand has at least one pair?

What is the probability that a $5$ card poker hand has at least one pair (possibly two pair, three of a kind, full house, or four of a kind)? I need to use the inclusion-exclusion principle. My ...
0
votes
1answer
51 views

What Is the Probability of at Least $2$ Heads (Not Neccessarily Consecutive) Will Appear When a Coin is Flipped $9$ Times?

What is the probability of at least $2$ heads (not neccessarily consecutive) will appear when a coin is flipped $9$ times? I know how to do this using Combination/Permutation with repetition, but ...
2
votes
1answer
58 views

Combinatorial Proof of Derangement Identity

Let $D_n$ be the number of derangements of n objects. Find a combinatorial proof of the following identity: $n! = D_n + \dbinom{n}{1} \cdot D_{n-1}+ \dbinom{n}{2} \cdot D_{n-2} + \cdots + ...
1
vote
0answers
60 views

A generalized version of inclusion exclusion principle using a binomial identity

I'm trying to find a way to derive a generalized inclusion exclusion principle for the number of elements which are in the intersection of at least $s$ sets from $A_1,A_2,...,A_n$ using this identity: ...
3
votes
2answers
88 views

Probability of drawing exactly two aces and two kings or one ace and three kings?

I've been trying to calculate the probability of drawing exactly two aces and two kings, or exactly one ace and three kings when the player already has an ace in hand. The player draws 24 more cards, ...
1
vote
1answer
38 views

Counting the number of permutations of a binary multiset that have >=1 partitions all ones?

Given a multiset $S$ of $O$ ones and $Z$ zeros, I'd like to count the number of permutations of $S$ that when partitioned into length $T$ segments have at least one segment that is all ones. ($T$ must ...
1
vote
1answer
28 views

Probability that all the balls are going to be in $1$ basket if it is known that there are at least $k$ empty baskets

There are $n$ identical balls and we need to put them inside $n$ baskets. What is the probability that all the balls are in $1$ basket if it is known that there are at least $k$ empty baskets ($0 \leq ...
3
votes
2answers
78 views

3 people dealt 3 cards, probability that nobody recieves 3 of a kind

If $3$ people are dealt $3$ cards from a standard deck, determine the probability that none of them is dealt three of a kind? Here is my attempt: The total number of hands is $${_{52}\mathsf ...
0
votes
1answer
60 views

Combinatorics problem, possibly inclusion-exclusion.

There are 28 people, none of whom are born on the 29th of Feb. Each individual organises a birthday party on the Sunday concluding the week of their birthday. What is the probability that at least 2 ...
1
vote
1answer
44 views

How to calculate the probability of getting at least one of each card in a given set from a deck?

I am trying to calculate the probability of getting a particular straight after drawing $x$ cards from a deck. Say, for this example, that the straight I am attempting to obtain is "2-3-4-5-6". I know ...