2
$\begingroup$

I was wondering how can I get the number of index in a multi-index notation?

if $\alpha \in \mathbb{N_0^n}$ is multi-index such that $ | \alpha|= \sum_{i=1}^{n} \alpha_i$

How many index do I have if $|\alpha|=d$ ?

$\endgroup$

1 Answer 1

3
$\begingroup$

Try induction. For $d=0$, you have $m_0 = 1$ possibilities.

For $d=1$, there are $m_1 = n = \frac{(1+1)n}{2}$ possibilities.

For $d=2$, there are $m_2 = \frac{n(n-1)}{2} + n = \frac{(n+1)n}{2}$ choices, from either putting $1$s in two slots or a $2$ in a single slot.

Now assume that for $d=k$, you have $m_k$ possible multi-indices.

Then $$m_{k+1} = \frac{(m_k+1)n}2 = \frac{m_kn}{2} +\frac{n}2.$$ This holds because from each index of order $k$, you can get one of order $k+1$ in $n$ different ways, by adding a $1$ to one of the $n$ entries. When you do this over all $m_k$ indices of order $k$, you get $m_kn$ indices. But most of them are double counted -- in fact all except the ones where only one entry is nonzero. Divide by two to account for the double counting and then add back $\frac{n}2$ to account for the special indices which weren't double counted.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .