Number of elements in cartesian power with a majority constraint

Question

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 majority constraint: how many elements in $X^n$ have a (relative) majority of one element of the set (say $x\in X$)?

On top of that, I'd like to fix one element in the cartesian power to a certain value (say the second), and count the number of possibilities with this fixed value.

Simple example: with $X=\{A, B, C\}$ and $n=4$. The question is: how many four-letter words with an $A$ in the second position have a (relative) majority of $A$'s? And how many have a (relative) majority of $B$'s?

Solution for the simple example: We can iterate on the total number $k$ of the element we want as a (relative) majority (say $A$).

• With $k=4$ elements being $A$, there is 1 option ($A$ is the majority, and $A$ is in the second position)

$AAAA$

• With $k=3$ elements being $A$, there are three possibilities for locating $A$'s. The second element is $A$ by constraint. The two extra $A$'s can be in position $(1,3), (1,4)$ or $(3,4)$. And there is one free position, where it can be everything but $A$: 2 possibilities. In total: $3\times 2=6$ possibilities.

$AAAB, AAAC, AABA, AACA, BAAA, CAAA$

• With $k=2$ elements being $A$'s, there is an extra-challenge: the two remaining positions should not be the same, otherwise $A$'s are not a majority anymore. About locating the $A$'s, one is fixed in the second position and the other $A$ can be in position $(1)$, $(3)$ or $(4)$: 3 possibilities. In the two remaining positions, there are 2 possibilities for the first one ($B$ or $C$ but not $A$) and 1 possibility for the second one (not $A$ and not the same than the first one). Total: 6 possibilities.

$AABC, AACB, BAAC, CAAB, BACA, CABA$

• With $k=1$ element being $A$, there are zero possibilities for $A$ to be a majority (three remaining possibilities, with only two letters, $B$ and $C$, so necessarily a majority of $B$ or $C$).

So with $n=4$ and 3 elements in the original set, there are 13 possibilities.

General solution? Is there a closed form formula to compute this number?

Same problem, expressed in a network formulation: In a network with 3 rows ($\{A, B, C\}$) and $n=4$ columns, assuming paths from left to right (e.g., using node $A_1$, then $B_2$, then $A_3$ and finally $C_3$), the question becomes: how many paths are going through node $A_2$ and have a (relative) majority of $A$ nodes?

Same problem, expressed in a voting context: Calculate winning outcomes of plurality voting

Answer 1

Let $|X|=m$ (the number of candidates) and $n$ be the number of voters. For the first question, by the basic theory of exponential generating functions, the number of ways for candidate $A$ to get a plurality of votes is the coefficient of $\frac{x^n}{n!}$ in the sum $$\sum_{k\ge0} \frac{x^k}{k!}\left(1+x+\frac{x^2}{2!}+\cdots+\frac{x^{k-1}}{(k-1)!}\right)^{m-1}.$$ To see this, sum over all possible numbers $k$ of votes that $A$ gets; the other $m-1$ candidates can get up to $k-1$ votes each. (Some terms in this sum are zero, but that's OK.)

For the second question, if you fix one of the votes, there are two possibilities, depending on whether you're fixing a vote for $A$ or for another candidate. In the former case, the answer will be $$\left[\frac{x^{n-1}}{(n-1)!}\right] \sum_{k\ge0} \frac{x^{k-1}}{(k-1)!}\left(1+x+\frac{x^2}{2!}+\cdots+\frac{x^{k-1}}{(k-1)!}\right)^{m-1} $$

(the notation $[z^n]f(z)$ denote the operation of extracting the coefficient of $z^n$ in the formal power series $f(z)=\sum f_n z^n$ in analytical combinatorics. See Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press (2009), p.19))

(the coefficient $A_n$ in an exponential generating function is recovered by $A_n=n!\cdot [z^n]A(z)$, since $[z^n]A(z) = A_n/n!$ (ibid., p.98))

since we now have to place $k-1$ votes for $A$. (This gives the same $13$ as in your example.) Similarly, if you're fixing a vote for one of the other candidates, the expression becomes $$\left[\frac{x^{n-1}}{(n-1)!}\right] \sum_{k\ge0} \frac{x^{k}}{k!}\left(1+x+\frac{x^2}{2!}+\cdots+\frac{x^{k-1}}{(k-1)!}\right)^{m-2}\left(1+x+\frac{x^2}{2!}+\cdots+\frac{x^{k-2}}{(k-2)!}\right). $$

Answer 2

• If $k>n/2$:

For non-fixed elements of the majority ($k-1$), there are $\binom{n-1}{k-1}$ possibilities (it works in the simple example with $k=4$: $\binom{3}{3}=1$; and $k=3$: $\binom{3}{2}=3$).

The number of "free" positions (for other elements than the majority) is $n-k$. For each position, there are $|X|-1$ possibilities (all elements in $X$ but the majority one). So, $(|X|-1)^{n-k}$ possibilities.

In total: $(|X|-1)^{n-k} \cdot \binom{n-1}{k-1}$ possibilities

• If $k<n/2$:

Same reasoning for the positioning of "majority" elements: $\binom{n-1}{k-1}$ possibilities.

The number of free positions for other elements is also $n-k$. But no element in these combinations must appear more than $k$ times. One way of computing this is to (1) count all possibilities: $(|X|-1)^{n-k}$ and (2) remove all possibilities with $k, k+1, k+2, ..., n-k$ of one element, for each element.

Step (2) as a subquestion here: Number of elements in cartesian power with a maximum constraint

• Step (2) for one given other element

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

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

  • ...

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

So, for one specific other element: $\sum_{j=k}^{n-k} (|X|-2)^{n-k-j}\cdot \binom{n-k}{j}$ possibilities. BUT double counting (see Number of elements in cartesian power with a maximum constraint), so $j$ in the sum has a different starting point: $j=k + \lfloor \frac{n-k-k}{2} \rfloor=k + \lfloor \frac{n-2k}{2} \rfloor = k + \lfloor \frac{n}{2} - k \rfloor = \lfloor \frac{n}{2} \rfloor$, and so for one specific element: $\sum_{j=\lfloor \frac{n}{2}\rfloor}^{n-k} (|X|-2)^{n-k-j}\cdot \binom{n-k}{j}$

• Step (2) for all other elements:

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

Final answer: $\sum_{k=1, k>n/2}^n (|X|-1)^{n-k} \cdot \binom{n-1}{k-1} + \sum_{k, k\leq n/2} \Bigg((|X|-1)^{n-k}-(|X|-1)\sum_{j=\lfloor \frac{n}{2}\rfloor}^{n-k} (|X|-2)^{n-k-j}\cdot \binom{n-k}{j}\Bigg)\cdot \binom{n-1}{k-1}$

With the simple example and $k=2$, the equation gives us $(|X|-1)^{n-k}-(|X|-1)\sum_{j=\lfloor \frac{n}{2}\rfloor}^{n-k} (|X|-2)^{n-k-j}\cdot \binom{n-k}{j} = (2^2-2)\cdot 3=6$, which is correct.