The slips are functions

There is a deep — and surprisingly simple — way to see the four slip formulae: they count functions.

Number the slips $1,2,\dots,k$ and the people $1,2,\dots,n$. Distributing the slips means saying, for each slip, which person gets it: that is, assigning to every element of $K=\{1,\dots,k\}$ (the slips, the domain) an element of $N=\{1,\dots,n\}$ (the people, the codomain). This is exactly a function $f:K\to N$, where $f(i)$ is the person who gets slip $i$.

The two slip questions become two properties of the function:

• numbered / blank = whether the slips are distinguishable. If numbered, it matters which slip goes where: the function is what it is. If blank, the slips are interchangeable, so only how many and to whom matters, not the label: of all the functions giving the same “outcome” we keep just one, the one that sends the slips in order — a increasing function (or non-decreasing, if repeats are allowed).
• at most 1 / more than one per person = each person gets at most one slip, or as many as you like. “At most one each” means two different slips do not land on the same person: the function is injective.

Combining the two properties gives the four kinds of function — and the four formulae:

The four formulae count functions $f:K\to N$ (with $|K|=k$, $|N|=n$)

	blank slips (identical)	numbered slips (distinct)
at most 1 per person	strictly increasing functions — $\dbinom{n}{k}$	injective functions — $\dfrac{n!}{(n-k)!}$
more than one	non-decreasing functions — $\dbinom{n+k-1}{k}$	all functions — $n^k$

Let us see the four cases one by one, with an example from $k=3$ slips to $n=5$ people.

Numbered, more than one per person → all functions ($n^k$)

No constraint: each slip freely picks one of the $n$ people. Slip $1$ has $n$ choices, slip $2$ has $n$, …, slip $k$ has $n$: in all $n\cdot n\cdots n = n^k$. These are all the functions from $K$ to $N$. Arrows may cross, land on the same person, or leave others out.

Here $f(1)=2,\ f(2)=2,\ f(3)=5$: two slips on the same person, three people with nothing. Perfectly fine.

Numbered, at most 1 per person → injective functions ($n!/(n-k)!$)

Each person at most one slip: two different slips cannot land on the same person. Slip $1$ has $n$ choices, slip $2$ only $n-1$ (it must avoid the taken person), slip $3$ has $n-2$, …: $n(n-1)\cdots(n-k+1)=\dfrac{n!}{(n-k)!}$. These are the injective functions: no person receives two arrows.

Here $f(1)=4,\ f(2)=1,\ f(3)=3$: all images distinct, but the order may “cross” (slip $1$ goes lower than slip $2$). The order is free because the slips are numbered.

Blank, at most 1 per person → strictly increasing functions ($\binom{n}{k}$)

Now the slips are identical: we can no longer tell “slip $1$” from “slip $2$”. With at most one each, distributing just means choosing which $k$ people get a slip — a subset of $k$ people out of $n$. To count them without duplicates we always list them in increasing order: each choice corresponds to a unique strictly increasing function $f(1)<f(2)<\dots<f(k)$. The arrows do not cross and are all distinct. Count: $\dbinom{n}{k}$.

Here $f(1)=1<f(2)=3<f(3)=4$: increasing images, arrows that do not cross. It amounts to choosing the subset $\{1,3,4\}$ of the people.

Blank, more than one per person → non-decreasing functions ($\binom{n+k-1}{k}$)

Identical slips, but now more than one may go to the same person. Only how many times each person is chosen matters: listing the images in order again gives a non-decreasing function $f(1)\le f(2)\le\dots\le f(k)$ (the equalities are the slips given to the same person). The arrows do not cross, but may arrive together. Count: $\dbinom{n+k-1}{k}$.

Here $f(1)=1\le f(2)=1\le f(3)=4$: person $1$ gets two slips, person $4$ gets one. Non-decreasing, non-crossing arrows.

One-line summary

Going from numbered to blank turns arbitrary/injective functions into their ordered versions (non-decreasing / strictly increasing): identical slips “erase the order”, and ordering the images is how we count them only once.

Links

Topics: Combinatorics
Concepts: Binomial coefficient · Combinations · Arrangements · Domain and codomain · Injectivity · Permutations
Methods: Slips table
Skills: Combinatorial calculus · Modelling