Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
    
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
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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