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

  • 1
    $\begingroup$ 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$. $\endgroup$ Feb 13 '15 at 15:47
  • $\begingroup$ @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$. $\endgroup$
    – Antonin
    Feb 13 '15 at 15:57
  • 1
    $\begingroup$ 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. $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.