Combinatorics: counting sums with conditions 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?  
 A: 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*}
A: 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!!
