Pigeonhole bounds, overlap counts and repeated selections

A counting guarantee is a worst-case statement

If N objects are assigned to k≥1 boxes, some box contains at least ceil(N/k) objects. A guarantee must hold for every assignment. It is not the likely occupancy of a randomly chosen box, and it need not hold in every box

Thirty-one objects are assigned to six boxes. What is the largest guaranteed lower bound on the occupancy of some box?

How many objects are needed to guarantee at least five in some one of six boxes?

Prove a sharp pigeonhole bound, ungraded

Let N objects be assigned to k≥1 boxes, and let t≥1 be a whole number. Prove the bound ceil(N/k) and show it is sharp by a construction. Then prove k(t−1)+1 is the smallest total forcing occupancy at least t

Model: contradiction and an avoiding assignment

Let g=ceil(N/k). If every occupancy were at most g−1, the total would be at most k(g−1)<N, a contradiction. Write N=qk+r with 0≤r<k. Put q+1 in r boxes and q in the others; the largest occupancy is g, proving sharpness. To avoid t in any box, at most t−1 may go in each, allowing k(t−1). That assignment exists; one extra object forces the claimed threshold

Two-set inclusion–exclusion removes one duplicate

Adding |A| and |B| counts every element of A∩B twice. Subtract the intersection once to count the union. The symbol ∩ includes every element satisfying both conditions

If |A|=17, |B|=14 and |A∩B|=6, find |A∪B|

Three sets require adding the triple intersection back

Add the three set sizes, subtract all three pairwise intersection sizes, then add the triple intersection. Pairwise intersection counts include the central triple region. “Exactly A and B” excludes C and is a different count

In the displayed diagram, how many objects belong to A∩B, including the central region?

For three sets, |A|=12, |B|=19, |C|=12, |A∩B|=5, |A∩C|=3, |B∩C|=7 and |A∩B∩C|=1. Find the union count

Prove three-set inclusion–exclusion, ungraded

Consider an arbitrary element that lies in exactly one, exactly two or all three sets. Show its total contribution to the formula is one, and an outside element contributes zero

Model: count each element’s contribution

An element in exactly one set contributes 1. One in exactly two contributes 2−1=1. One in all three contributes 3−3+1=1. An outside element appears in no term and contributes zero. Thus every union member is counted exactly once

Selections with repetition count multiplicity vectors

Choose r objects from k distinguishable types with unlimited supply, treating objects of a type as identical and ignoring order. A choice is a vector (x₁,...,xₖ) of nonnegative integers with sum r. It is different from an ordered string, which would have kʳ possibilities

Choose five objects from three unlimited types, recording only how many of each type. How many selections exist?

Stars and bars gives a bijection

Write r stars and place k−1 bars among them, allowing bars next to each other and at either end. The star counts before, between and after bars give the ordered type multiplicities. There are r+k−1 positions and the bar positions determine the allocation

Derive stars and bars and its lower-bound extension, ungraded

Prove the correspondence is one-to-one in both directions, including zero counts and r=0. Then derive the count when every type must occur at least ℓ times

Model: bijection and a change of variables

Given a multiplicity vector, write x₁ stars, a bar, x₂ stars, and so on; this constructs one unique string. Reading star runs recovers the vector, so the correspondence is bijective. Adjacent/end bars allow zero counts. With r=0, all k−1 positions are bars and there is one allocation. For xᵢ≥ℓ, put yᵢ=xᵢ−ℓ. Then the yᵢ are nonnegative and sum to r−kℓ. If that residual is negative there are no allocations; otherwise the count is C(r−kℓ+k−1,k−1)

Choose five objects from three unlimited types, with at least one of every type. How many selections exist?

An upper bound can be handled by complement

For nonnegative multiplicities totalling r, count all allocations then subtract those with x₁≥b+1. Substituting z₁=x₁−(b+1) turns the excluded cases into the same problem with r−(b+1) units. A negative residual gives zero excluded cases. Apply any lower-bound shift before this step

Choose five objects from three unlimited types, with at most two of the first type. How many selections exist?

Derive Pascal’s identity, ungraded

For 1≤k≤n, prove C(n,k)=C(n−1,k)+C(n−1,k−1) by deciding whether a fixed element is selected. Also derive the sum of C(n,k) over k=0..n

Model: partition and a second count

For a fixed distinguished element, k-element subsets either exclude it, giving C(n−1,k), or include it, leaving k−1 choices from n−1. These disjoint cases prove Pascal’s identity. All subsets can be counted by their size, giving the sum of C(n,k), or by making an include/exclude choice for each of n elements, giving 2ⁿ. The empty and full subsets are included