# Number of elements in cartesian power with a maximum constraint

Problem: I would like to know the number of elements in the cartesian power $X^n$ (cartesian product of one set $X$ by itself, $n$ times) with a maximum constraint: how many elements in $X^n$ have less than $k$ same elements $x$ of the set ($\forall x\in X$)?

Simple example: with $X=\{A, B, C\}$ and $n=3$. The question is: how many three-letter words have less than $k$ times the same letter?

Solution for the simple example:

• for $k=4$, there is no constraint: $|X|^n$, here 27 possibilities.

• for $k=3$, we just can't have three times the same letter, so $AAA, BBB$ and $CCC$ are forbidden, $27 - 3=25$ possibilities.

• for $k=2$, we can't have twice the same letter, so we only have $ABC, ACB, BAC, BCA, CAB, CBA$, 6 possibilities.

• for $k=1$, we can't build any word, 0 possibilities.

General solution? What is the general formula to compute this number as a function of $k$?

Strategy 1: all cases minus cases with more than $k$

One solution would be to count all possibilities without constraints, $|X|^n$, and then remove all cases with $k, k+1, ..., n$ repetitions of all elements.

• For one given element in $X$

• with $k$ of this element: we fix $k$ times the element: $n$ free spaces, $k$ elements, $\binom{n}{k}$ possibilities. For each possibility, we put the others: $n-k$ free spaces, $|X|-1$ elements, $(|X|-1)^{n-k}$ possibilities. In total: $(|X|-1)^{n-k}\cdot \binom{n}{k}$ possibilities for a given other element with $k$ appearances.

• For $k+1$ appearances: $(|X|-1)^{n-k-1}\cdot \binom{n}{k+1}$ possibilities

• ...

• For $n$ appearances: $(|X|-1)^{n-n}\cdot \binom{n}{n}= 1$ possibility, intuitive.

So, for one specific other element: $\sum_{j=k}^{n} (|X|-1)^{n-j}\cdot \binom{n}{j}$ possibilities

• For all elements in $X$:

There are $|X|$ elements, so the number of possibilities with more than $k$ times any other element is $|X|\sum_{j=k}^{n} (|X|-1)^{n-j}\cdot \binom{n}{j}$

Problem: some words are double counted

Strategy 1 for the simple example:

All cases: $|X|^n=3^3=27$ possibilities.

• Let's fix one element $A\in X$ and iterate over $k$.

• Let's fix $k=3$. How many sequences with 3 $A$'s? $\binom{3}{3}=1$ possibility.

• Let's fix $k=2$. How many sequences with 2 $A$'s? $\binom{3}{2}=3$ possibilities to put the $A$'s. Then, there is one extra space, that we can fill in with $B$ or $C$: two possibilities. In total: $3\times 2 = 6$ possibilities.

• Let's fix $k=1$. How many sequences with 1 $A$? $\binom{3}{1} = 3$ possibilities. Then, there are two extra spaces to fill in with $B$ and $C$. If we accept to have twice $B$, the generated word will be $ABB$, and so it's double counted with "Fix one element $B\in X$, $k=2$".

Strategy 2: (by Andrei Rykhalski)

Construct $X_k$ $\forall k=1, ..., n$ containing $k$ times each element $x\in X$.

Build words of length $n$ from alphabet of size $nk$.

Then find all possible distinct combinations of its elements of length n (exclude duplicates).

In the simple example: $X_3=\{A,A,A,B,B,B,C,C,C\}$, $X_2=\{A,A,B,B,C,C\}$, $X_1=\{A,B,C\}$.

• Haven't tried to solve the problem such way but perhaps this helps: you may construct sets $X_k$ for each $k = 1..n$ containing each element of $X$ $k$ times and then find all possible distinct combinations of its elements of length $n$. Feb 13 '15 at 15:47
• @AndreiRykhalski If I understand you well, $X_3=\{AAA, BBB, CCC\}$ and $X_2= \{AAB, AAC, ABA, ACA, BAA, CAA, BBA, BBC, BAB, BCB, ABB, CBB, ...\}$, and $X_1 = \{ABC, ABB, ACB, ...\}$. The issue is, $ABB\in X_2$ and $ABB\in X_1$. Feb 13 '15 at 15:57
• Nope, $X_3 = \{A,A,A,B,B,B,C,C,C\}, X_2 = \{A,A,B,B,C,C\}$. So you are building words of length $n$ from alphabet of size $nk$ and after that need to exclude duplicates. Feb 13 '15 at 16:02

$|X|^n - |X|\sum_{j=k+\lfloor\frac{n-k}{2}\rfloor}^{n} (|X|-1)^{n-j}\cdot \binom{n}{j}$
Same answer than in the question (strategy 1) but $j$ starts not at $k$ but in the middle of the interval $\lfloor k+\frac{n-k}{2}\rfloor$. Justification: by removing all words with $n$, $n-1$, etc. till the middle, we already removed all the other ones, with $k$, $k+1$, ... repetitions.