Maths WorkshopMaths problems with full solutions

Inclusion-exclusion

64 problems · Principle of inclusion-exclusion and derangements.

Ex.243The two-set inclusion-exclusion formula
#inclusion-exclusion #two sets #union
Inclusion-exclusion
High school
High school
Ex.244Disjoint unions
#IE #disjoint #sum
Inclusion-exclusion
High school
High school
Ex.245Proof of the two-set formula
#IE #two sets #proof
Inclusion-exclusion
High school
High school
Ex.479The three-set inclusion-exclusion formula
#inclusion-exclusion #three sets #union
Inclusion-exclusion
High school
High school
Ex.480Counting complement via IE
#complement #IE #at least one
Inclusion-exclusion
High school
High school
Ex.481Derangements of $3$ elements
#derangements #$D_3$ #list
Inclusion-exclusion
L1
L1
Ex.482Derangements of $4$ elements
#derangements #computation #fixed point
Inclusion-exclusion
L1
L1
Ex.483Even vs odd subsets
#even subsets #odd subsets #IE
Inclusion-exclusion
High school
High school
Ex.484Exact intersection count
#IE #intersection #count
Inclusion-exclusion
High school
High school
Ex.485Summary of inclusion-exclusion
#summary #IE #formulas
Inclusion-exclusion
High school
High school
Ex.486Non-constant functions to $\{0,1\}$
#IE #functions #non-constant
Inclusion-exclusion
High school
High school
Ex.487Nested sets
#IE #nested #specific
Inclusion-exclusion
L1
L1
Ex.488Surjections to $\{0,1\}$
#surjections #IE #onto
Inclusion-exclusion
High school
High school
Ex.701Derangements of four objects
#inclusion-exclusion #permutations
Inclusion-exclusion
L2
L2
Ex.986Permutations with at least one fixed point
#IE #fixed point #permutations
Inclusion-exclusion
L1
L1
Ex.987Binomial identity via IE
#IE #binomial #identity
Inclusion-exclusion
Olympiad
Olympiad
Ex.988Coprime to $100$
#IE #coprime #totient
Inclusion-exclusion
L1
L1
Ex.989Numbers coprime to $30$ up to $100$
#IE #coprime #totient
Inclusion-exclusion
L1
L1
Ex.990Counting numbers with at least one property
#IE #counting #divisibility
Inclusion-exclusion
L1
L1
Ex.991Derangements of $5$ elements
#derangements #$D_5$ #computation
Inclusion-exclusion
L1
L1
Ex.992Derangements of $6$ elements
#derangements #$D_6$ #computation
Inclusion-exclusion
L1
L1
Ex.993Derangement recurrence
#derangement #recurrence #IE
Inclusion-exclusion
L1
L1
Ex.994Derangements
#derangements #permutations #no fixed point
Inclusion-exclusion
L1
L1
Ex.995Euler's totient via inclusion-exclusion
#Euler totient #IE #coprime
Inclusion-exclusion
L1
L1
Ex.996Exactly one property
#IE #exactly one #properties
Inclusion-exclusion
L1
L1
Ex.997The general inclusion-exclusion formula
#inclusion-exclusion #general #n sets
Inclusion-exclusion
L1
L1
Ex.998Items with no defect
#IE #complement #no defect
Inclusion-exclusion
L1
L1
Ex.999Letters and envelopes
#IE #derangements #letters
Inclusion-exclusion
L1
L1
Ex.1000Elements with none of the properties
#IE #complement #none
Inclusion-exclusion
L1
L1
Ex.1001Surjections from $5$ to $3$
#surjections #IE #count
Inclusion-exclusion
L1
L1
Ex.1002Inclusion-exclusion in a survey
#IE #survey #population
Inclusion-exclusion
High school
High school
Ex.1003Counting with divisibility
#IE #divisibility #counting
Inclusion-exclusion
L1
L1
Ex.1004The sieve of Eratosthenes as IE
#IE #sieve #primes
Inclusion-exclusion
L1
L1
Ex.1005Surjections from $4$ to $3$
#surjections #IE #count
Inclusion-exclusion
L1
L1
Ex.1006Counting surjections via inclusion-exclusion
#surjections #onto #IE
Inclusion-exclusion
L1
L1
Ex.1007Partial three-set data
#IE #three sets #intersection
Inclusion-exclusion
L1
L1
Ex.1008Exactly one of two properties
#IE #exactly one #properties
Inclusion-exclusion
L1
L1
Ex.1009Two triples
#IE #triples #sets
Inclusion-exclusion
L1
L1
Ex.1010IE with complements
#IE #complements #sets
Inclusion-exclusion
L1
L1
Ex.1235Derangements and the number 1/e
#inclusion-exclusion #permutations #derangements
Inclusion-exclusion
Olympiad
Olympiad
Ex.1255Stars and bars with upper bounds
#stars and bars #inclusion-exclusion #counting #compositions
Inclusion-exclusion
M1
M1
Ex.1256Surjections and splitting a set into three groups
#Stirling numbers #inclusion-exclusion #surjections #set partitions
Inclusion-exclusion
Olympiad
Olympiad
Ex.1712Four-set inclusion-exclusion
#IE #four sets #union
Inclusion-exclusion
L1
L1
Ex.1713Application to probability
#IE #probability #events
Inclusion-exclusion
L1
L1
Ex.1714At least two properties
#IE #at least two #intersection
Inclusion-exclusion
L1
L1
Ex.1715Inclusion-exclusion in ballot problems
#IE #ballot #paths
Inclusion-exclusion
Olympiad
Olympiad
Ex.1716Colorings avoiding patterns
#IE #coloring #grid
Inclusion-exclusion
Olympiad
Olympiad
Ex.1717Numbers coprime to $210$
#IE #coprime #totient
Inclusion-exclusion
L1
L1
Ex.1718Path counting via IE
#IE #paths #obstacles
Inclusion-exclusion
Olympiad
Olympiad
Ex.1719Derangements via double counting
#derangements #double counting #IE
Inclusion-exclusion
Olympiad
Olympiad
Ex.1720Pairwise but not triple
#IE #triple #void
Inclusion-exclusion
L1
L1
Ex.1721A multi-property application
#IE #application #multi
Inclusion-exclusion
L1
L1
Ex.1722Committees by inclusion-exclusion
#IE #committees #at least one
Inclusion-exclusion
L1
L1
Ex.1723Combining multiple IE applications
#IE #combining #multi-step
Inclusion-exclusion
Olympiad
Olympiad
Ex.1724Probability a permutation has a fixed point
#IE #probability #fixed point
Inclusion-exclusion
L1
L1
Ex.1725Proof of inclusion-exclusion
#inclusion-exclusion #proof #indicator
Inclusion-exclusion
L1
L1
Ex.1726Sieve formula
#IE #sieve #formula
Inclusion-exclusion
L1
L1
Ex.1727Colorings with constraints
#IE #coloring #constraints
Inclusion-exclusion
L1
L1
Ex.1728Avoiding two letters
#IE #words #avoiding letters
Inclusion-exclusion
L1
L1
Ex.1729Two obstacles via IE
#IE #paths #obstacles
Inclusion-exclusion
Olympiad
Olympiad
Ex.1730Words avoiding letters
#IE #words #letters
Inclusion-exclusion
L1
L1
Ex.2155Both rows and columns
#IE #matrices #both
Inclusion-exclusion
Olympiad
Olympiad
Ex.2156Exactly $k$ properties
#IE #exactly k #sieve
Inclusion-exclusion
Olympiad
Olympiad
Ex.2157The ménage problem (statement)
#ménage #IE #arrangements
Inclusion-exclusion
Olympiad
Olympiad