# 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.

877 questions
40 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 ...
16 views

### Inclusion–exclusion principle in projective geometry

In the problems that I have to apply Grassmann in projective geometry, can I use the inclusion-exclusion principle? Consider the following problem: We consider three linear varieties of dimension ...
42 views

### How many numbers between $1 - 1000$ leave no remainder when divided by $4$ and when divided by $6$ but not when divided by $21$?

Numbers between $1 - 1000$ which leave no remainder when divided by $4$ and divided by $6$ but not by $21$? I tried $$\frac{1000}{12} = 83 - \frac{83}{21} = 83-3 = 80$$ Am I correct? Can someone ...
181 views

### Showing an alternating sum is positive

I am trying to prove the following for $n > 1$. $$\sum_{k=0}^n (-1)^k \binom{n}{k} \max\{0,n-2k\}^{n-1} > 0.$$ From numerical computations, this seems to be true, but I am struggling to find ...
28 views

### Principle of I/E: In how many ways can eight cakes be distributed among four kids if every kid receives at least one cake?

Eight cakes are distributed randomly among four kids. Use I/E to determine in how many of the possible distributions every kid receives at least $1$ cake. Hint: Define $A_i$ to be the set of ...
73 views

### Counting Surjections with Inclusion-Exclusion

Compute the number of surjective functions $f : [10] → [5]$ using the I/E principle. With Stirling numbers of the second kind, we can obtain the answer with the following way $S(10,5)5!$. How I can ...
159 views

### How many numbers from 0 to 99999 contain the digits 2, 5 and 8?

I have this problem: How many integers between 0 and 99999 contain the digits 2, 5 and 8? I've tried a lot, but I don't know how resolve it. P.S. The solution should be 4350.
45 views

### What is a k-wise intersection?

I am having a hard time visualizing and conceptualizing what a k-wise intersection is. I am guessing 3-wise intersection for 3 sets: $S_1,S_2,S_3$ would be $(S_1 {\cap}S_2{\cap}S_3)$ and 2-wise ...
32 views

### Calculate the expected value of the number of different digits

Question. $n$ is a $m$-digit number. ($m$ can start with zero.) Let $P(n)$ the number of different digits in $n$. What is the expected value of $P(n)$? (For example, $P(12341234)=4$.) My approach. ...
22 views

### Is my proof valid? Let $\{A_i\}_{i=0}^{i=n}$ a series of events such that $\forall i$ $P(A_i)=1$. Show that $\bigcap\limits_{0 \leq i \leq n}A_i=1$.

Let $\{A_i\}_{i=0}^{i=n}$ a series of events such that $\forall i$ $P(A_i)=1$. Show that $\bigcap\limits_{0 \leq i \leq n}A_i=1$. My attempt: Let $0\leq k\ne j\leq n$, so $P(A_j)=1, P(A_k)=1$. ...
37 views

### Selecting conditional states depending on previous states

I've seen a post which was started as a joke saying : "Well, Guess the code ?" (4 digit code) Apart from the joke , I was thinking , well , how many combinations do we have here , knowing that <...
54 views

### 4 couples and 4 single people seated at 3 round tables

In how many ways can you seat the 12 people at 3 round tables such that: A) All couples are seated together. (the two members of each couple sit side-by-side) B) No couples sit together. I've ...
32 views

### Inclusion-Exclusion Number of Sets

Derive and prove a general formula for the number of elements which are in an odd number of the sets $A_1,A_2,...,A_n$, written in terms of $|A1|$, $|A2\cap A7|$, $|A3\cap A4\cap A9|$, etc., possibly ...
113 views

### Probability Inclusion-Exclusion With 3 Events

The question is: An urn contains 4 balls: 1 white, 1 green, and 2 red. We draw 3 balls with replacement. Find the probability we did not see all three colors. I need to define the events as W= {white ...
109 views

### Number of ways to arrange word 'KBCKBCKBC'

The word 'KBCKBCKBC' is to be arranged in a row such that no word contains the pattern of KBC. $Attempt$ Event $A$=1st KBC is in the pattern, $B$=2nd KBC is in the pattern and similar is the event C....
66 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 ...