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.

179 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7
votes
1answer
183 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 = ...
6
votes
1answer
131 views

Linear independence of indicator functions

Question Let $X$ be a finite set, let $\mathbf{F}$ be a field. Let $\mathcal{A}$ be a subset of the power set of $X$, i.e. $\mathcal{A}\subseteq\mathcal{P}(X)$. Let $1_A:X\to F$ denote the indicator ...
4
votes
1answer
222 views

inclusion-exclusion problem - sitting arrangement

I am not sure how to approach this question. How many ways are there to seat n couples around a circular table such that no couple sits next to each other? Since it's a part of inclusion-exclusion,...
4
votes
0answers
135 views

Find the number of $n$ husband's placing

Let there be $n$ pairs of husband-wife, and a round table with $2n$ chairs. Suppose that $n$ wives are already sat down, and between any two neighboring wives there is exactly one free chair (there is ...
4
votes
0answers
106 views

Interpretation of Eulerian numbers using the principle of inclusion-exclusion

Eulerian numbers, denoted $e_{n,k}$, are defined as the number of permutations of $[n]$={1,2,...,n} such that there are k "ascents". (For example, the permutation 23541 of [5] would have 3 ascents, ...
4
votes
0answers
286 views

Can the principle of inclusion/exclusion be used to count elements in the intersection of a sequence of sets?

The principle of inclusion-exclusion (PIE) is often used to count the number of elements in a union of $n$ sets in terms of an alternating sum of their various intersections: $$ \left |\bigcup_{i \in ...
3
votes
0answers
56 views

Reasoning about remainders and the Möbius function

This one seems counter intuitive to me but I am not seeing a mistake in my reasoning. Please let me know if you find one. Let: $x > 0$ be an integer $\mu(x)$ be the möbius function $x\#$ be the ...
3
votes
0answers
44 views

Calculate $\sum_{|S|=k}(n-|\cup S|)^m$ where $S$ is a subset of $X=\{\{a_1,a_2\},\{a_2,a_3\},\cdots,\{a_{n-1},a_n\},\{a_n,a_1\}\}$

Let $x_i=\{a_i,a_{i+1}\}\ (1 \leq i \leq n-1)$, $x_n=\{a_n,a_1\}$ and $X=\{x_1, \cdots, x_n\}$. Given $n,m$ and $k$, I'd like to ask how to calculate $\sum_{|S|=k}(n-|\cup S|)^m$ where $S$ is a subset ...
3
votes
0answers
50 views

Counting tuples of subsets for which every subtuple of a given size has union equal to the entire set

I have a question which is a refined version of the question asked here. Let $A = \{1,\ldots,n\}$, $S_r = \{a \subset A: |a| = r\}$ for $0 < r \leq n$, $S_r^m = \{(a_1,\ldots,a_m) : a_i \in S_r \}$ ...
3
votes
1answer
73 views

How many solutions are to $x_1+x_2+x_3+x_4+x_5+x_6=30$ if $x_1=6$ then $x_2\neq 4$, $x_3=6$ then $x_4\neq 4$, $x_5=6$ then $x_6\neq 4$?

How many solutions over $\mathbb N$ (includes $0$) are to $x_1+x_2+x_3+x_4+x_5+x_6=30$ if the three conditions below must hold: if $x_1=6$ then $x_2\neq 4$, if $x_3=6$ then $x_4\neq 4$, if $x_5=6$...
3
votes
0answers
140 views

counting non-negative integers <100000 (studying for intro discrete math exam)

im studying previous math exams for my discrete math finals next week, no solutions are provided for past exams so i figured id try posting here. Q: How many non-negative integers less than one ...
3
votes
0answers
59 views

Basic PIE question appears to be wrong?

First-year math students were asked whether they experience math​ anxiety, headaches, or tiredness when studying for math exams. Of the 125 students​ asked, 66 experience math​ anxiety, 22 experience​ ...
3
votes
2answers
111 views

How many arrangements of the digits $0,1,…,9$ are there that do not end with an $8$ and do not begin with a $3$?

Using inclusion exclusion principles, How many arrangements of the digits $0,1,....,9$ are there that do not end with an $8$ and do not begin with a $3$? Here are my workings, are they correct? ...
3
votes
0answers
118 views

How many permutations of the letters: DREAMORTEAM do not have identical consecutive letters?

I tried to do do this using inclusion-exclusion principle, and got something like this: $ \frac{11!}{2!2!2!2!} -\binom{4}{1} \frac{10!}{2!2!2!}+\binom{4}{2} \frac{9!}{2!2!}-\binom{4}{3} \frac{8!}{2!} ...
3
votes
1answer
438 views

Discrete Maths: Inclusion Exclusion - patterns “spin”, “game”, “path” or “net”

This is a question from Discrete and combinatorial mathematics by Ralph Grimaldi. This question is related to Inclusion Exclusion Principle. Question - Find the number of permutations of a, b, c, ...
3
votes
0answers
159 views

Inclusion-exclusion principle for multisets

Lets say I want to count the number of monic polynomials of degree $d$ in $\mathbb{F}_p[X]$ that have no roots in $\mathbb{F}_p$. Fix a $1 \leq k \leq d$ and choose $k$ distinct elements of $\mathbb{F}...
3
votes
0answers
231 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 ...
3
votes
0answers
268 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 ...
3
votes
0answers
213 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.$ ...
3
votes
3answers
429 views

Combinatorics question involving distributing 9 different candies to three different kids

Nine different chocolate bars are to be distributed to 3 different kids. a) In how many ways can this be done if there are no restrictions? b) In how many ways can this be done if the child A ...
2
votes
0answers
34 views

Counting Surjections - Combinatorics

I am working on a combinatoric proving that the number of surjective functions $f\colon [n]\to [3]$ is equal to $1/2(3^{n-1}-2^n+1)$ I approached the problem as below Let’s consider that we have a ...
2
votes
1answer
73 views

Number of permutation of $\{ 1, 2 \dots 2n\}$ with even fixpoints and relating this to derangements.

I am interested in determining $e_n$, the number of permutations of $\{ 1,2 \dots 2n\}$ where we allow even numbers to be fixed points, but where odd numbers are not allowed to be fixed points. This ...
2
votes
0answers
279 views

Inclusion/exclusion, at least and exactly arrangements?

The question is given the word "ARRANGEMENT", a) find exactly 2 pairs of consecutive letters? b) find at least 3 pairs of consecutive letters? I have the answer given from the tutor but it doesn't ...
2
votes
0answers
61 views

In how many ways can string $123456$ be rearranged if at least one character needs to move more than one place from its original position?

In how many ways can string $S=123456$ be rearranged if at least one character needs to move more than one place from its original position? For example, string $12534$ satisfies the condition ...
2
votes
0answers
77 views

Inclusion exclusion for distributing distinguishable items to indistinguishable groups

I have just learnt some great things about using Stirlings number of 2nd kind to emulate inclusion exclusion principle to find distribution of distinguishable objects to distinguishable groups from ...
2
votes
0answers
53 views

Arrangments of letters using inclusion and exclusion principles

Using inclusion exclusion principles, How many arrangements of the $26$ different letters are there that contain either the sequence "the" or the sequence "aid" Here are my workings, are they ...
2
votes
0answers
43 views

Unique pairings with repeated elements

I am looking for a generalization of the formula for the number of unique pairs of a list of elements to the case where there are multiple copies of each element. First a review of the standard ...
2
votes
0answers
143 views

Proving Möbius inversion formula for inclusion exlusion

reading in "Introductory Combinatorics" about Möbius inversion, some questions have arose: 1) Author defines function $$F(K) - \text{# of elements of S that belong to $exactly$ those sets } A_i\text{...
2
votes
1answer
47 views

Find an expression for $|S-\{A_1\cap A_2\cap \dots \cap A_n\}|$ for $ A_1,\, A_2, \dots , A_n\subset S$

Find an expression for $|S-\{A_1\cap A_2\cap \dots \cap A_n\}|$ for $ A_1,\, A_2, \dots , A_n\subset S$ . and we assume the knowledge of the size of the union of any number of $ A_i$'s but not of the ...
2
votes
0answers
51 views

Use PIE to count the number of $6$-multisets of $[6]$ in which no digit occurs more than twice.

This is one of a set of several problems in my book I am having difficulty not just solving, but also understanding the provided solutions. The given answer is $462 - 336 + 15 = 141.$ I'll try and ...
2
votes
0answers
181 views

Counting permutations of a binary string with a condition on “distance”.

At the suggestion of poster Brian M. Scott, I am posting this as a new question. Background: High school level student, self-studying combinatorics from "Introductory Combinatorics" by Brualdi loaned ...
2
votes
0answers
59 views

how many teams can be assigned to a task such that at least one team completes a task

There's a problem in my combinatorics class: there're 5 people who need to complete 4 tasks. They decided that each task will be completed by a team of 2 people. In how many ways can we assign a team ...
2
votes
0answers
67 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
1answer
188 views

Hat check problem. Ten friends total, five with sombreros, five with fedoras.

A group of ten people give their hats to the coatroom attendant. Five of the ten are wearing sombreros, and five and wearing fedoras. How many ways can the clerk return the hats so that no one gets ...
2
votes
0answers
59 views

Combinatorics submultisets Inclusion-Exclusion

Find the number of submultisets of {$25 \cdot a, 25 \cdot b, 25 \cdot c, 25 \cdot d$} of size $80$. I applied Inclusion-Exclusion to get; $$ {80+3\choose 3} - {4\choose1}\cdot{80-26+3\choose3} + {4\...
2
votes
0answers
180 views

Combinatorics Inclusion - Exclusion Principle

Find the number of integer solutions to $x_1 + x_2 + x_3 + x_4 = 25$ with $ 1 \leq x_1 \leq 6, 2 \leq x_2 \leq 8, 0 \leq x_3 \leq 8, 5 \leq x_4 \leq 9.$ Firstly, I defined $y_i = x_i - lower bound$ ...
2
votes
0answers
40 views

Number of permutations of [2n] where $x_i + x_{i+1} \ne 2n+1$

As stated in title, what is the number of permutations of $[2n]$ where $x_i + x_{i+1} \ne 2n+1 \;,\forall i\in[2n-1]$. I want to use the inclusion-exclusion theorem, and consider separately ...
2
votes
0answers
141 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 ...
2
votes
0answers
45 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 ...
2
votes
1answer
92 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 many ...
2
votes
1answer
168 views

Number of ways possible to form a number?

Suppose we need to form a 4 digit number with the restriction that ...
2
votes
0answers
78 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 ...
2
votes
1answer
333 views

Number of arrangements of $n$ couples around a circular table with restriction

A group of $n$ couples (a total of $2n$ people) sit at a circular table. Arrangements that differ by any rotation of the seating positions are considered to be the same. Find a formula for the number ...
2
votes
0answers
142 views

Number of permutations possible?

Given two permutation of $1, \ldots, N$. Where 3<=N<=1000 Example For $N=4$ First is $\begin{pmatrix}3& 1& 2& 4\end{pmatrix}$. Second is $\begin{pmatrix}2& 4& 1& 3\end{...
2
votes
0answers
209 views

Limit of generalized principle of inclusion-exclusion

If we have the inclusion exclusion principle of the following generalized form, $$P\left(\bigcup_{i=1}^n A_i\right) = \sum_{k=1}^n (-1)^{k-1} \sum_{I\subset \{1,\ldots,n \} ; \|I\| = k } P(A_I)$$ ...
2
votes
1answer
256 views

Inclusion Exclusion and lcm

I would like to show that for any positive integers $d_1, \dots, d_r$ one has $$ \sum_{i=1}^r (-1)^{i+1}\biggl( \sum_{1\leq k_1 < \dots < k_i \leq r} \gcd(d_{k_1}, \dots , d_{k_i})\biggr) ~\leq~ ...
1
vote
0answers
23 views

Inclusion–exclusion principle on multiple set maximum value?

Say there are $46$ people in a club, $35$ of them are Chess lovers, $30$ of them are sports lovers, $40$ of them are Opera lovers, $38$ of them are video game lovers. So at least how many people are ...
1
vote
1answer
65 views

What is the number of possibilities to choose $~80~$ numbers out of the set $~\{10,11,\cdots,99\}~$ with repetition and no order significant

What is the number of possibilities to choose 80 numbers out of the set $~\{10,11,\cdots,99\}~$ with repetition and no order significant. In which if an element that divides by $10$ with no Remain of ...
1
vote
0answers
27 views

Number of lattice points bounded by lines on plane.

There are given following lines on plane: $A: x=0$ $B: y=0$ $C_{i}:y=a_{i}x+b_{i}$ for $1\le i \le n$ so that these lines intersect with first two lines ($x=0,y=0$) at non-negative coordinates. Let $...
1
vote
0answers
28 views

Inclusion–exclusion principle, find the number of students

There are ten students. Eight of them have travelled to Europe, seven of them speak Spanish and six of them study math. How many students have travelled to Europe, speak spanish and study math? Well, ...