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

2
votes
0answers
22 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
2answers
45 views

Help me understanding what actually i counted with inclusion-exclusion

I tried to solve following task: Count number of $8$-permutations from $2$ letters $A$, $2$ letters $B$, $2$ letters $C$ and $2$ letters $D$ where exactly one pair of same letters are adjacent in ...
1
vote
2answers
108 views

Combinatorial proof of $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!$, using inclusion-exclusion

If $l$ and $n$ are any positive integers, is there a proof of the identity $$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!\;$$ which uses the Inclusion-Exclusion Principle? (If necessary, ...
1
vote
1answer
25 views

Calculating intersection cardinalities of cover sets

I'm having trouble automating calculation of intersection cardinalities of particular sets. Here are some definitions. Number of available elements is $n$, size of a particular set $S \in \...
4
votes
2answers
85 views

How many integers $\leq N$ are divisible by $2,3$ but not divisible by their powers?

How many integers in the range $\leq N$ are divisible by both $2$ and $3$ but are not divisible by whole powers $>1$ of $2$ and $3$ i.e. not divisible by $2^2,3^2, 2^3,3^3, \ldots ?$ I hope by ...
0
votes
0answers
18 views

Is Site Percolation with Bernoulli variables i.i.d. independent and identically distributed?

I cannot understand the identically distributed part in the i.i.d assumption. Consider a site percolation where each event is a Bernoulli variable. Does this mean ...
0
votes
1answer
41 views

How many integers in $\{500,…,1000\}$ are not divisible by 3, 7 or 13?

I am wondering what the best way to approach this question is. I thought that I would calculate the number of integers that aren't divisible by 3, 7 or 13 in $\{1,2,...,1000\}$ as well as the number ...
0
votes
1answer
54 views

Find the value of P(Y|X)

If $$P(X)=\frac{1}{4},$$ $$P(Y)=\frac{1}{3},$$ and $$P(X \cap Y) =\frac{1}{2}.$$ $$P(Y | X)= \frac{P(X \cap Y)}{P(X)}$$ But by using this formula, I got an incorrect answer. $1/3$ is the right ...
0
votes
1answer
50 views

Is this equation true?

As the question states, does this equation hold true? $\sum_{j=0}^n \sum_{E \in {n \choose j}} (-1)^{|E|}(n-|E|)! = \sum_{j=0}^n(-1)^j(n-j)!{n \choose j} $ From what I understand, this holds true at ...
0
votes
3answers
37 views

How many fix point free permutations of 5 elements are there? [duplicate]

I am trying to find out how many fix point free permutations of 5 elements there are. A permutation is fix point free, if $\pi (i) \neq i$. I am trying to solve this problem using the inclusion ...
3
votes
2answers
104 views

How many positive integers from set $\{1,2…,10^{30}\}$ can't be represented as 2nd, 3rd, or 5th power of some positive integer?

An interesting problem I ran across. My guess is that it can be solved somehow using inclusion-exclusion principle. It would be a fun thing to learn how to do this, so I could use that knowledge in ...
11
votes
6answers
210 views

Proving $\sum_{k=1}^{n}{(-1)^{k+1} {{n}\choose{k}}\frac{1}{k}=H_n}$

I've been trying to prove $$\sum_{k=1}^{n}{(-1)^{k+1} {{n}\choose{k}}\frac{1}{k}=H_n}$$ I've tried perturbation and inversion but still nothing. I've even tried expanding the sum to try and find ...
0
votes
0answers
45 views

Counting GF($q=8$) matrices with a certain property

Let us denote by $\boldsymbol{v}_i$ the columns of an $m \times n$ GF($8$) matrix. The field elements are enumerated $\{0,1,2,...,q-1\}$. To define the arithmetic operations between field elements, we ...
6
votes
3answers
94 views

Probability of choosing $n$ numbers from $\{1, \dots, 2n\}$ so that $n$ is 3rd in size

We uniformly randomly choose $n$ numbers out of $2n$ numbers from the group $\{1, \dots, 2n\}$ so that order matters and repetitions are allowed. What is the probability that $n$ is the $3^{\text{rd}}$...
0
votes
0answers
53 views

How many strings of 12 lowercase letters with repetitions

Consider strings of 12 lowercase letters, such as aksdjmnuuyio. How many strings either are a repetition of 2 strings of 6, such as aksdjmaksdjm, or a repetition of three strings of 4, such as ...
1
vote
0answers
32 views

Inclusion-exclusion formula and its alias names

I am reading Probability by A. N. Shiryaev. One of the problems refers to "inclusion-exclusion formulas", also known as Poincaré’s formulas, Poincaré’s theorems, Poincaré’s identities. One of my ...
1
vote
1answer
32 views

Combined probability of hit in look up tables with some common index bits

Consider two tables A and B consisting of $l_a$ and $l_b$ counters respectively - $l_a$ and $l_b$ are powers of two and the counters are initialized to zero. Each table has its own index ...
7
votes
4answers
153 views

Find the probability that a word with 15 letters (selected from P,T,I,N) does not contain TINT

If a word with 15 letters is formed at random using the letters P, T, I, N, find the probability that it does not contain the sequence TINT. (I just made up this problem.)
0
votes
1answer
38 views

Naive question about 3 sets intersection point

I have three intersecting in at least one point sets $A$, $B$, $C$ with arbitary finite countable cardinality. The known facts are: $$ |A|, |B|, |C| $$ $$ |A \cap B| $$ $$ |B \cap C| $$ $$ |C \cap A|...
5
votes
2answers
82 views

Inclusion–exclusion: Matrices

Let $A$ be an $n\times n$ matrix that contains all the numbers $1,2,\ldots,n^2$ (each one appears one time). Count the number of $n \times n$ matrices $B$ that contain all the numbers $1,2,\ldots,n^2$ ...
1
vote
1answer
40 views

Use inclusion-exclusion to find explicit formula for $P(A_k)$. Where is independence used?

Probability with Martingales This was answered here using bounds and here using PGF. I would like to try inclusion-exclusion. Let $H_1, H_2, ...$ be independent events with $P(H_k) = p$ where $...
0
votes
3answers
75 views

Three people each choose five distinct numbers at random from the numbers 1, 2, . . . , 25, independently of each other.

What is the probability that the three choices of five numbers have no number in common? I know I have to use inclusion-exlcuion here and that using the compliment is probably the best way to solve ...
1
vote
1answer
48 views

Inclusion-Exclusion principle and finite product identity

On this page, there is a proof that uses the inclusion-exclusion principle to provide a formula for the value of Euler's totient function. I would be grateful if someone could explain the reasoning ...
2
votes
1answer
38 views

Probability of complete coupon set in $K$ boxes where a box has $N$ distinct coupons?

Say there is a contest to collect a full set of $M$ coupons. Each box of product has $N$ distinct coupons of the $M$ possible coupons in it, selected uniformly without replacement from the $M$ ...
0
votes
0answers
12 views

inclusion-exclusion formula and Mobius inversion formula

Could any one explain to me what is the Mobius inversion formula and what is it connection with the principle of inclusion and exclusion? My understanding is that Mobuis inversion formula can find ...
6
votes
1answer
54 views

Generalised inclusion-exclusion principle

In answers to combinatorial questions, I sometimes use the fact that if there are $a_k$ ways to choose $k$ out of $n$ conditions and fulfill them, then there are $$ \sum_{k=j}^n(-1)^{k-j}\binom kja_k ...
1
vote
1answer
50 views

How many sequences $a_1,a_2,…,a_n$ in length $k$ so $a_i \in \{1,2,3,4…,n\}$ satisfy

I have the follow two questions : How many sequences $a_1,a_2,...,a_n$ in length $k$ so $a_i \in \{1,2,3,4....,n\}$ satisfy : 1) $a_1<a_2<....<a_k$ while $(a_{i+1} \neq a_i+1)$ 2) $a_1 \...
0
votes
1answer
32 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 ...
2
votes
1answer
41 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
26 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 $$\Big|\bigcup_{i=1}^{n}A_i\Big|=\sum_{k=1}^{n}(...
1
vote
1answer
45 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
88 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
42 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
56 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 ...
1
vote
1answer
102 views

Probability that duplicates are still in the deck after X card drawn

Deck has 30 cards, out of which 5 cards have duplicates (20 cards are unique, 5 cards have 2 copies each). If you draw X cards from the deck (without returning), what is the probability that there ...
5
votes
1answer
56 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
vote
2answers
44 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
56 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
69 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
64 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
99 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
80 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
28 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
14 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 ...
1
vote
1answer
40 views

Probability of chosen urns being filled after randomly throwed 2 balls k times

We have n urns. Repeat next process k times: choose 2 distinct urns, throw ball into each. What is the probability of choosing 2 urns with at least 1 ball in it? (e.g. we have 8 urns. Then choose 3 ...
1
vote
2answers
150 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
133 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
46 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 $N/...
2
votes
2answers
48 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
12 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 ...