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
0answers
40 views

Number of arrangements of A,B,C,D,E,F with conditions.

How many arrangements are there of A,B,C,D,E,F if B follows immediately after A or D immediately after C or F immediately after E ? Here is my solution: let $A1$ be the set where B is immediately ...
1
vote
1answer
36 views

can inclusion/exclusion be done with set subtraction instead?

The inclusion/exclusion principle applied to the Venn diagram below (from Wikipedia) would give the value of $\left\lvert A\cup B \cup C\right\rvert$ as $\left\lvert A\right\rvert + \left\lvert ...
3
votes
4answers
241 views

Integer solutions using PIE

Find the number of integer solutions to $a+b+c+d=18$ with $ 0≤a,b,c,d≤6$. With no restrictions there are: $$\binom{21}{3} = 1330$$ Ones that are invalid are: $a, b, c, d \ge 7$. But how do I ...
2
votes
2answers
392 views

Stars and Bars vs PIE

I randomly made up this question so I could check: There are $3$ kids and $6$ gifts, how many ways to distribute so that each kid has at least one gift. Obviously, $**|**|**$ there are ...
2
votes
0answers
54 views

inclusion-exclusion principle working

We have $n$ non-negative integers $a_1, a_2, \dots, a_n$. We will call a sequence of indexes $i_1, i_2, \dots, i_k$ such that $1\le i_1 < i_2 < \dots< i_k\le n$ a group of size $k$. How many ...
0
votes
1answer
48 views

Counting functions $f: A \rightarrow B$ where $|A| \gt |B|$ and $|f(A)| = x$

I've come across an exercise like this in my discrete maths textbook (Grimaldi), and I'm thoroughly stumped. Suppose $A = \left\{1, 2,...,n\right\}$ and $B = \left\{1, 2,...,m\right\}$ where $n \gt ...
2
votes
1answer
60 views

Easiest way to find the 'area of a Venn diagram,' given certain information.

We have a bunch of intersecting regions: $$X_1,\dots, X_n,$$ all with non-negative volume, and we know $V(X_i)$ and $V\left((\cup_{a\in A}X_a)\cap (\cup_{b\in B}X_b)\right)$ for any disjoint ...
3
votes
1answer
78 views

Inclusion - exclusion-like inequality

Let $(\Omega,\mathcal{F},\mathbb{P})$ be some probabilistic space and $A_1,\ldots,A_n\in \mathcal{F}$. Is it true that: $$\sum\limits_{i=1}^{n} \mathbb{P}(A_i)^2 - \sum\limits_{1\le i<j\le ...
0
votes
1answer
61 views

How to interpret the Generalized Version of Inclusion-Exclusion Principle

This is a follow-up question on the previous post. Let's say there are $n$ properties which are numbered $1,\cdots,n$. And let $A$ be a set of elements which has some of these properties. Then the ...
5
votes
1answer
84 views

Counting square free numbers co-prime to $m$

Counting square free numbers $\le N$ is a classical problem which can be solved using inclusion-exclusion problem or using Möbius function (http://oeis.org/A071172). I want to count square free ...
0
votes
2answers
31 views

Student card handing Inclusion–exclusion principle

I got the following question and would very much appreciate any help with understanding it solution. "5 Student cards are handed to 5 students so that each student gets 1 student card, what is the ...
19
votes
4answers
211 views

Inclusion-exclusion-like fractional sum is positive?

Let $A_1,A_2,\ldots,A_n$ be finite nonempty sets. Is it true that $$\sum_{i=1}^n\frac{1}{|A_i|}-\sum_{1\leq i<j\leq n}\frac{1}{|A_i\cup A_j|}+\sum_{1\leq i<j<k\leq n}\frac{1}{|A_i\cup ...
12
votes
4answers
432 views

How do I prove this combinatorial identity using inclusion and exclusion principle?

$$\binom{n}{m}-\binom{n}{m+1}+\binom{n}{m+2}-\cdots+(-1)^{n-m}\binom{n}{n}=\binom{n-1}{m-1}$$ Note that we can show this with out using inclusion and exclusion principle by using Pascal's Identity ...
0
votes
2answers
65 views

Applying Inclusion-Exclusion principle

How to apply principle of inclusion-exclusion to this problem? Eight people enter an elevator at the first floor. The elevator discharges passengers on each successive floor until it empties on ...
1
vote
0answers
30 views

Product of Dependent Bernoulli variables

Let $B_{i,n}$ with $i=1,...,n$ be the triangular Bernoulli array defined as $$ B_{i+1,n} = B_{i,n}\,R_{i+1,n}+\left(1-R_{i+1,n}\right)\,F_{i+1,n}, $$ where $R_{i,n}$ and $F_{i,n}$ are iid Bernoulli ...
3
votes
1answer
138 views

A Generalized version of Inclusion-Exclusion Principle?

I recently read Doron Zeilberger's paper on Inclusion-Exclusion Principle. Let's say there are $n$ properties which are numbered $1,\cdots,n$. And let $A$ be a set of elements which has some of ...
14
votes
3answers
210 views

Count permutations of $\{1,2,…,7\}$ without 4 consecutive numbers - is there a smart, elegant way to do this?

Here's a problem I've solved: Count permutations of $\{1,2,...,7\}$ without 4 consecutive numbers (e.g. 1,2,3,4). So I did it kinda brute-force way - let $A_i$ be the set of permutations of $[7]$, ...
2
votes
0answers
29 views

What determines the number when excluding in Inclusion Exclusion problems

My question might be a bit poorly articulated as I am not sure what I'm asking is actually called. I am faced with an Exclusion/Inclusion problem that goes like this: You have $25$ identical cakes ...
0
votes
1answer
27 views

Calculating the probability of getting a full bucket in a hash table with open addressing

I have a problem where I'm trying to calculate the probability of getting a full bucket when I use a hash table with open addressing. What I have: A hash table with 128 buckets, each bucket can ...
2
votes
1answer
88 views

Integers divisible by 4 but not by 3 and 16

For $n \leq 1000$ I am interested in the integers who are divisible by 4 but not by 3 and 16. Say $a_i$ is the property that an integer is divisible by $i$. Inclusion-Exclusion gives us: \begin{align} ...
2
votes
1answer
34 views

Using Inclusion-Exclusion Principle to find number of ways to distribute envelopes

I have encountered this problem on a past paper: In how many ways can 675 identical envelopes be divided, in packages of 25, among four student groups so that each group gets at least 150, but no ...
3
votes
1answer
61 views

Inclusion-Exclusion: INTELLIGENT permutations

How many ways are there to arrange the letters in INTELLIGENT with at least two consecutive pairs of identical letters? I got an answer of ...
0
votes
1answer
61 views

number of ways to choose pairs of nonadjacent people from $2k$ people sitting in a circle

The following is problem 19 in Chapter 2 from Richard Stanley's Enumerative Combinatorics, vol. 1 (2nd ed.): Suppose that $2k$ persons are sitting in a circle. In how many ways can they form pairs if ...
0
votes
0answers
30 views

Given $d>8$ boxes and $n$ balls. . What is $P(A \cup B \cup C)$?

Given $d>8$ boxes and $n$ balls. Consider event $A$=boxes numbered $1,2,3,4$ receive 0 balls.$B=3,4,5,6$ receive 0 balls, $C=5,6,7,8$ receive zero balls. What is $P(A \cup B \cup C)$? ...
6
votes
1answer
84 views

Summation of a function

Let $n$ is a positive integer. $n = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$ is the complete prime factorization of $n$. Let me define a function $f(n)$ $f(n) = p_1^{c_1}p_2^{c_2}...p_k^{c_k}$ where $c_k = ...
0
votes
1answer
35 views

What can you say about this set operation using principle of inclusion/exclusion

Given: A = [ Aaron features ], B = [Bob features], X = [all countries in Europe ] What must be true if: |A ∩ B ∩ X| = 1 Even though I don't see the relation between cardinality of sets, I ...
20
votes
5answers
525 views

In how many ways can $1000000$ be expressed as a product of five distinct positive integers?

I'm trying to solve the following problem: "In how many ways can the number $1000000$ be expressed as a product of five distinct positive integers?" Here is my attempt: Since $1000000 = 2^6 \cdot ...
1
vote
1answer
35 views

Inclusion Exclusion with 4 sets: How many integers between 1 and 100 are divisible by 2 or 3 or 5 or 7?

How many numbers between 1 and 100 are divisible by 2 or 3 or 5 or 7? The solution I had gives a different answer from what was provided, so I was wandering if anyone could tell me what mistake I ...
0
votes
0answers
52 views

inclusion–exclusion principle formula in probability for general case

For the system reliability analysis of complex systems, I'll use the formula below after a point in a custom computer code. I know that for the n=2 case, formula result is $P_1+P_2-P_1.P_2$ ($P$ : ...
0
votes
2answers
54 views

Prove the inclusion-exclusion formula

We just touched upon the inclusion-exclusion formula and I am confused on how to prove this: $|A ∪ B ∪ C| =|A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|$ We are given this hint: To do ...
0
votes
1answer
61 views

Number of permutations of $A=\{1,2,3,\dots,n\}$ such that $|x_i-x_j|\ne|i-j|$ of every $i,j\in A$

Let $B$ be the permutation of $A=\{1,2,3,\dots,n\}$ such that $|x_i-x_j|\ne|i-j|$ of every $i,j\in A$ where $x_k$ is $k-th$ element of $B$. How many different $B$ exist? On first sight it doesn't ...
1
vote
1answer
51 views

Inviting 4 friends out of 8 for a week such that each friend visits at least once

Dave is inviting 4 friends out of 8 for a week how many possibilities there are such that each friend visit at least once. Let's number the friends for brevity, 1 to 8. This is like asking how ...
0
votes
1answer
39 views

Probability of placement in a random ordering of integers (inclusion-exclusion rule)

Problem Let $a_1, ..., a_n$ be a random ordering of integers $1,...,n$. What is the probability that there exists no $1 \leq i \leq n$ such that $a_i = i$? Attempted solution For #1: let $A_i = ...
0
votes
2answers
36 views

Summation with Multiple Indices

How would the following summation work? $\sum_{r,s,t \ge 0_{r+s+t=n}} \binom{m_1}{r} \binom{m_2}{s} \binom{m_3}{t}$ How would you choose the value for the next integer in the series? For example, ...
1
vote
1answer
95 views

Inclusion-Exclusion question

A careless payroll clerk is placing employees’ paychecks into pre-labeled envelopes. The envelopes are sealed before the clerk realizes he didn’t match the names on the paychecks with the names on the ...
4
votes
1answer
57 views

Determine the number of ways for n couples to stand in a line so that no one stands beside his or partner (explanation for the answer)

I'm not quite sure if I'm understanding solution to following problem: "Determine the number of ways for n couples to stand in a line so that no one stands beside his or her partner." The general ...
4
votes
2answers
82 views

number of pairs formed from $2n$ people sitting in a circle

I am trying to understand the solution to the following problem: Suppose that $2n$ persons are sitting in a circle. In how many ways can they form $n$ pairs if no two adjacent persons can form a ...
1
vote
1answer
57 views

Question about probability theory inclusion/exclusion

So, I've been trying to teach myself probability theory, and I think I have the idea down, but I wanted to make sure I am on the right track. Thus, I was wondering if people here could confirm that I ...
0
votes
3answers
117 views

There are 5 students. Must form 3 teams and every team must have 2 students in common.

This is the problem. Suppose there are 5 students and we are trying to form 3 distinct scientific teams such that Every student must join into at least one team (no student should left without a ...
0
votes
1answer
71 views

Ways to distribute candies using inclusion/exclusion

I have 173 million pieces of candy. There are 5 students. In how many ways can this distribution be made, assuming that each student receives at least 1 million candies, Student B receives at most 10 ...
2
votes
1answer
92 views

How to extend the Inclusion Exclusion Principle to an XOR situation

For calculating the probability of the union of independent events, $P(A_1\cup A_2\cup A_3\cup A_4)$ one can use the Inclusion Exclusion principle: $$ \eqalign{ P\Bigl(\bigcup_{i=1}^n A_i\Bigr) = ...
1
vote
1answer
33 views

Number of ordered quadruples sets

I'm trying to tackle the following question, but got no clue how to do so (I know it is not very popular not showing any effort, but this time I really don't know what to do). Iv'e seen a solution ...
5
votes
1answer
71 views

If we are given that a list of $n$ numbers has $11,660$ derangements, what is the value of $n$?

The Full Question For the positive integers $1,2,3,\dots n-1,n$, there are $11,660$ where $1,2,3,4,5$ appear in the first five positions. What is the value of $n$? My Work First I considered all ...
0
votes
2answers
33 views

Simple combinatorics - inclusion and exclusion problem

There are 3 groups ${{A}_{1}},{{A}_{2}},{{A}_{3}}$ What we know about them : \begin{align} & |{{A}_{1}}|=|{{A}_{2}}|=|{{A}_{3}}|=n \\ & |{{A}_{1}}\cup {{A}_{3}}|=2n-q \\ & ...
0
votes
1answer
30 views

# of Numbers from 1 to 2400 which are divisible by (8 or 5) or not by 6

I need to apply the Principle of Inclusion-Exclusion here: Hence I get $$|A_8| + |A_5| + |\neg A_6| - |A_8 \cap A_5| - |A_8 \cap \neg A_6| - |\neg A_6 \cap A_5| + |A_8 \cap A_5 \cap \neg A_6|$$ I ...
1
vote
1answer
83 views

Understanding inclusion exclusion principle (with example question).

Hi here is a question that i solved with generating functions , and i try to solve the same question with the inclusion exclusion principle. Question: We have four type of balls - ...
1
vote
1answer
119 views

let s be a set with N elements and A1,…,A101 be 101 (possibly not disjoint) subsets of S

So the question I'm having problem with is the following: let s be a set with N elements and A1,...,A101 be 101 (possibly not disjoint) subsets of S with the following 5 properties: each elements ...
0
votes
1answer
108 views

How many lattice paths with step S and W are there that begin at (0,0), end at (-12,-12)

How many lattice paths with step $S$ and $W$ are there that begin at $(0,0)$, end at $(-12,-12)$ and do not go through any of the points $(-1,-4), \space (-5,-3), \space (-9,-11)$? I'm unsure of how ...
3
votes
1answer
135 views

Distribute $10$ distinct prizes to $4$ students

Inclusion Exclusion Used Theorem 8.1 The Question: In how many ways can one distribute $10$ distinct prizes to $4$ students with exactly $2$ students getting nothing. b) How many ways have at ...
0
votes
1answer
115 views

How Many Ways Can 3 x's 3 y's and 3 z's be arranged so that no consecutive triple of the same letter appears

My Question I want to know two things: is my solution correct, and is there another, more clever, way to solve it? My Solution There are a total of $\frac{9!}{3!3!3!}$ arrangements of $xxxyyyzzz$. ...