Combinatorics: counting sums with conditions

Question

Hi guys, Here's a combinatorial nut to crack. I've been struggling with this one:

Count the number of ways summing a set of $n$ non negative integers $i_1, \cdots, i_n \in \{ 0, \cdots , n-1\} $ so the sum is an integer multiple of $n$; under the condition that the first $i_j$ is unique: $i_1 \neq i_2, \cdots i_n$.

The sums can obviously range from $ 0 $ to $ n(n-1)$ and we have $n$ such sums to consider. Without the uniqueness of $i_1$ the problem is pretty straight forward to solve using a generating function $(1 + x + x^2 + \cdots x^{n-1})^{mn}$ for $m = 0 , \cdots , n-1$. Any idea of what the full answer could be?

Answer 1

I don't have any idea of what the answer would be, but instead I will give you the exact answer...but don't get very excited, I didn't say "closed form" answer. Maybe "The Oracle" (Zeilberger's creations, or Mathematica or something similar) yields the definitive answer.

The idea is to apply a very nasty inclusion-exclusion argument.

For each $r,s\in\mathbb Z$ such that $0\leq r\leq n-1$ and $0\leq s\leq n-1$, let $A_{r,s}$ be the set of $n$-tuples $(i_1,\dots,i_n)\in\{0,1,\dots,n-1\}^n$ such that $i_1=r, i_1+i_2+\cdots+i_n=sn$ and $i_j\ne r$ for $j=2,\dots,n$. These sets $A_{r,s}$ are clearly mutually disjoint and their union is your required set.

Now $A_{r,s}$ corresponds to the set $$\bigl\{(j_1,\dots,j_{n-1})\in\{0,1,\dots,n-1\}^{n-1}: j_1+\cdots j_{n-1}=sn-r,$$

$$j_k\ne r\ \style{font-family:inherit;}{\text{for}}\ k=1,\dots,n-1\bigr\}\,;$$

A "bad" $(n-1)$-tuple $(j_1,\dots,j_{n-1})\in\mathbb N^{n-1}$ such that $j_1+\cdots+j_{n-1}=sn-r\ $ is one tuple such that $j_k=r\ $ or $\ j_k\geq n\ $ for some $k$. For each nonempty subset $K$ of $\{1,\dots,n-1\}$, let

$$B_K=B_{r,s,K}=\bigl\{(j_1,\dots,j_{n-1})\in\mathbb N^{n-1}: j_1+\cdots j_{n-1}=sn-r,$$

$$j_k\in\{r,n,n+1,\dots\}\ \style{font-family:inherit;}{\text{for}}\ k\in K\bigr\}\,.$$

Now for each subset $S$ of $K$ (even $S=\emptyset$) consider the subset

$$B_{S,K}=\bigl\{(j_1,\dots,j_{n-1})\in B_K: j_k=r\ \style{font-family:inherit;}{\text{for}}\ k\in S, j_k\geq n\ \style{font-family:inherit;}{\text{for}}\ k\in K\setminus S\bigr\}\subseteq B_K$$

(happily, the conditions $a=r$ and $a\geq n$ are mutually disjoint, otherwise this would be worse). It follows that the set $B_{S,K}$ corresponds to the set

$$\bigl\{(t_1,\dots,t_{n-1-|S|})\in\mathbb N^{n-1-|S|}: t_1+\cdots+t_{n-1-|S|}=sn-r-r\cdot|S|-n\cdot|K\setminus S|\bigr\}\,,$$

whose cardinality is well-known (though I always forget it), namely,

$$\binom{\bigl(n-1-|S|\,\bigr)+\bigl(sn-r-r\cdot|S|-n\cdot|K\setminus S|\,\bigr)-1\ }{\bigl(n-1-|S|\,\bigr)-1}\,,$$

which depends only on $|S|$ and $|K|\,$. Thus, the cardinality of $B_K$ is given by

$$|B_K|=\sum_{S\subseteq K}|B_{S,K}|=\sum_{p=0}^{|K|}\sum_{\substack{S\subseteq K\\ |S|=p}}|B_{S,K}|=\sum_{p=0}^{|K|}\binom{|K|}p\binom{n-2-p+sn-r-rp-n\cdot|K|+np}{n-2-p}=b_{|K|}\,.$$

Therefore, by inclusion-exclusion principle (and the fact that $|B_K|$ depends only on $|K|\,$), the number of "bad" tuples is

$$\sum_{q=1}^{n-1}(-1)^{q-1}\sum_{\substack{K\subseteq\{1,\dots,n-1\}\\|K|=q}}|B_K|=\sum_{q=1}^{n-1}(-1)^{q-1}\binom{n-1}qb_q=c_{r,s}\,.$$

Consequently we have

$$|A_{r,s}|=\bigl|\,\bigl\{(j_1,\dots,j_{n-1})\in\mathbb N^{n-1}: j_1+\cdots+j_{n-1}=sn-r\bigr\}\bigr|-c_{r,s}=\binom{(n-1)+(sn-r)-1}{(n-1)-1}-c_{r,s}=d_{r,s}\,.$$

Thus, the required number is $$\sum_{0\leq r,s\leq n-1}d_{r,s}\,.$$

Enjoy!!

Answer 2

First, observe that without the constraint on $i_1$, there are exactly $n^{n-1}$ solutions, because after choosing any combination of values for $i_1$, $i_2$, $\dots$, $i_{n-1}$, there is exactly one way to choose $i_n\in\{0,\ldots,n-1\}$ so that the sum of the $i_j$s is a multiple of $n$. Now, use the inclusion-exclusion principle. This says that, with the constraint on $i_1$, there will be $$ n^{n-1}-\sum_{1\le\ell\le n-1} (-1)^{\ell-1} \binom{n-1}{\ell} A_\ell\qquad (*) $$ solutions, where $A_\ell$ is the number of solutions in which, for a given subset of size $\ell$ of the indices $\{2,\ldots,n\}$, the $i_j$s with $j$ in this set are all equal to $i_1$. (This number does not depend on which $\ell$ indices are picked. Also, the count $A_\ell$ allows other indices $j$ besides those in the chosen set to have $i_j=i_1$.)

If $\ell\in\{1,2,\ldots,n-2\}$, there are $n$ ways to choose $i_1$. For the $\ell$ indices $j$ where $i_j$ is required to be equal to $i_1$, these $i_j$s are then fixed. $n-\ell-2$ of the remaining $i_j$s may be chosen freely, and there is exactly one way to choose the last $i_j$ so that $i_1+\cdots+i_n$ is a multiple of $n$. Therefore, $A_\ell=n^{n-\ell-1}$.

If $\ell=n-1$, then $i_1=i_2=i_3=\cdots=i_n$, and $i_2$, $\dots$, $i_n$ are all fixed after $i_1$ is chosen. Since the sum of all the $i_j$s is then $ni_1$, it is always a multiple of $n$, so $i_1$ may be chosen to have any value. Therefore, $A_{n-1}=n$. Plugging these values of $A_\ell$ into $(*)$ gives the answer \begin{eqnarray*} &&n^{n-1}-\sum_{1\le\ell\le n-2} (-1)^{\ell-1} \binom{n-1}{\ell} n^{n-\ell-1} -(-1)^{n-2} n\\ &=&\left(\sum_{0\le\ell\le n-1} (-1)^\ell \binom{n-1}{\ell} n^{n-\ell-1}\right) + (-1)^{n-1}(n-1)\\ &=&(n-1)^{n-1}+(-1)^{n-1} (n-1). \end{eqnarray*}