# Combinatorics for multi-index set, how many elements does $\{ X^j : |j|=3, j_l \neq 0\}$ have?

Let $j \in \mathbb{R}^n$ be a multi-index with $|j|=3$. Fix an index $l$, then there are how many $X^j$ with $j_l=0$?, more precise: I want to know what $\text{#} \{ X^j : |j|=3, j_l \neq 0\}$ is.

So did the following: If $j$, $|j|=3$, then $X^j=X_{i_1} X_{i_2} X_{i_3}$ (for example $j_i=3$, then choose $i_1=i_2=i_3=i$), and $j_l=1$ means that $i_3=l$ already fixed, $X^j=X_{i_1} X_{i_2} X_l$. So if we disjunctly seperate it in the cases $j_l=1,2$ and $3$, we would have

1. $\text{#} \{ X^j : |j|=3, j_l =1 \}= \text{#}\{ X_{i_1} X_{i_2} X_l : i_1,i_2 \neq l \}=(n-1)^2$ (place 2 stones $i_1, i_2$ on a line with $n-1$ free places (place l is "occupied") )
2. $\text{#} \{ X^j : |j|=3, j_l =2 \}= \text{#}\{ X_{i_1} X_l^2 : i_1 \neq l \}=n-1$
3. $\text{#} \{ X^j : |j|=3, j_l =3 \}= \text{#}\{ X_l^3 \}=1$

So in sum $n^2-n-1$. The problem is that, if I check this, it should equal $\text{#} \{X^j : |j|=3\} - \text{#} \{ X^j : |j|=3, j_l=0 \} = n^3 - \text{#} \{ X_{i_1} X_{i_2} X_{i_3} : i_1, i_2, i_3 \neq l \}=$ $=n^3-(n-1)^3$

But $n^3-(n-1)^3=1-3n+3n^2$, so I did something wrong somewhere.. Does somebody see the mistake(s)? (Or has another way to assure the result)

-
I presume $|j| = j_1 + j_2 + \cdots + j_n$, but can you clarify that somewhere? The $|\cdot|$ sign suffers a lot of abuse :) – Srivatsan Sep 8 '11 at 12:14
yes, as you said $|j|=j_1+ \dots + j_n$ for a multi-index $j$. – Johannes L Sep 8 '11 at 12:15

You're oscillating between distinguishing by order and not. For instance, to get $(n-1)^2$, you're treating $i_1$ and $i_2$ as distinguishable from each other, but not from $l$. This should be either $3(n-1)^2$ if you want to distinguish by order, or $n(n-1)/2$ if you don't. For multi-indices, it would make sense not to; then with the correct value for 1. you have

$$\frac{n(n-1)}2+(n-1)+1=\frac{n(n+1)}2\;,$$

and the check yields

$$\begin{eqnarray} \binom {n+2}3-\binom {n+1}3 &=& \frac{(n+2)(n+1)n}6-\frac{(n+1)n(n-1)}6 \\ &=& ((n+2)-(n-1))\frac{(n+1)n}6 \\ &=& \frac{n(n+1)}2 \end{eqnarray}$$

as expected.

-
A reference to stars-and-bars may also be helpful to the OP. – Brian M. Scott Sep 8 '11 at 19:01
@joriki Thank you a lot. When I try to work with it, there is one strange point. So I have to see it like 1. is interpreted choose $k=2$ indices out of $n-1$ places (combination with repetition, $(n+k-1) \choose k$), $j_l=2$ is like choosing $k=1$ indice out of $n-1$ places. This adds up to ${n \choose 2}+{n \choose 1}$. But can I not write $\{X^j : |j|=3, j_l=0\}$ as $\{ X_{i_1} X_{i_2}, 1 \leq i_1, i_2 \leq n\}$, which would be choose $2$ out of $n$ (~> $n+1 \choose 2$), and now this would only be consistent if $j_l=3$ would correspond to $0$ elements. But shouldn't it be one? – Johannes L Sep 9 '11 at 14:30
In the above comment, $k=1$ indices out $n-1$ means $n-1 \choose 1$ instead of $n \choose 1$, and with $1$ element for the set with $j_l=3$ everything sums up nicely – Johannes L Sep 9 '11 at 15:01
@Johannes: If I understand correctly, your second comment is a correction of the first one and everything comes out right now? – joriki Sep 11 '11 at 9:21
@joriki yes, thanks for the help with your answer! – Johannes L Sep 12 '11 at 5:59