Combinatorics in ML: Counting Points with co-ordinates from among a set.

Question

I'm trying to re-prove a theorem in the book Understanding Machine Learning: From Theory to Algorithms by Shalev-Schwartz et. al to aid my understanding of the material. The proof in the book derives a crude bound, and I'd like to derive a tighter one by counting the relevant quantities.

General Version of Problem:

Given a finite domain $X$ of size $M$, I'd like to consider points in the $n$-fold product of X; these points have n-coordinates, each an element of X. There are a total of $M^{n}$ such points.

Now, I'd like to partition these points into $n$ sets. The first set, $S_{1}$, will contain all points that contain exactly 1 unique element of $X$ among its co-ordinates. The second set, $S_{2}$, will contain all points that contain exactly two unique elements, and so on.

I would like to determine $|S_{i}|$ for $1\leq i \leq n$.

$|S_{1}| = M$, since, there are exactly $M$ points with one unique member of $X$ among their co-ordinates. Similarly, $|S_{n}| = \frac{M!}{(M-n)!}$.

Using the inclusion-exclusion formula, I've been able to derive a long and messy formula for $|S_{i}|$. I'm wondering if anyone knows a simple way to do this, or a standard reference where this problem is solved.

Here's an example:

Let $M = 6$, and the members of $X$ are just labelled with integers. Also, suppose $n=3$.

The point (1,1,1)) would belong to $S_{1}$. The point (6,2,2) would belong to $S_{2}$. The point (1,5,3) would belong to $S_{3}$.

This case can be solved explicitly, since $|S_{1}|$ = 6, $|S_{3}|$ = 120, and $|S_{1}|+|S_{2}|+|S_{3}|$ = 216

I'm not very good at counting, and hope that there is a simple way to do this. Thank you!

Answer 1

An $n$-tuple can be interpreted as a function $f : \{1,\dots,n\} \to X$. Namely, $(f(1),f(2),\dots,f(n))$. What you are asking is to count all such functions whose image has $i$ elements. The image is a subset of $X$ and there are $\binom{M}{i}$ subsets with $i$ elements. Then you want a surjective map onto this set.

Surjective functions $g : A \to B$ where $|A| = n$ and $|B| = k$ are counted by Stirling numbers. (See Twelvefold way for details.) Namely there are

$$ k!\left\{ \begin{array}{c} n \\ k \end{array} \right\} = \sum_{j=0}^k (-1)^{k - j} \binom{k}{j}j^n $$

surjective functions $A \to B$. You can also obtain this from inclusion-exclusion.

Therefore

$$ |S_i| = i!\binom{M}{i} \left\{ \begin{array}{c} n \\ i \end{array} \right\} = \binom{M}{i} \sum_{j = 0}^i (-1)^{i - j} \binom{i}{j}j^n. $$