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

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!

• This question may be somewhat relevant, but also uses inclusion-exclusion. Your $|S_i|$ is essentially $\binom{M}{i}$ times the number of surjections from $\{1,\ldots,n\}$ to a set of size $i$. Commented Nov 3, 2017 at 23:55

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.$$

• Thank you! This is exactly what I was hoping for. I'll carefully read both articles, and try to understand the reasoning and combinatorial identities you have used. Commented Nov 4, 2017 at 1:12
• @colin I'm glad you found it helpful. If you find that an answer resolves your question, the best way to indicate that is to "accept" it by clicking on the check-mark next to the answer. Commented Nov 4, 2017 at 1:48