I have to count some vectors $\lambda=(\lambda_1,\ldots,\lambda_n)\in\mathbb{N}^n_{\geq0}$. Futhermore thier coordinates should fullfill:
$$0=\lambda_1=\lambda_2=\cdots=\lambda_{k-1}=\lambda_k<\lambda_{k+1}<\cdots <\lambda_{n-1}<\lambda_{n}\leq n$$
for $k=1,\ldots,n$. My paper says that there are $2^{n}$ of them (might be wrong, already found some other mistakes in there) but I have no clue how the autor worked that out. I would be really gratefull if one of you could help me out with that.
On
My argument is the follwoing. If we fix some $k$, and $\lambda_{n}= n-k$, then $\#(vectors) =1$. If we have $\lambda_{n} = n-k+1$, than we can have only one "missed" value, that is we will have $\#(vectors) =n-k+1$. For the next we will have, that if $\lambda_{n} = n-k+2$, than we will have to missing values. So $\binom{n-k+2}{2}$. And for the fixed $k$, we will have $\#(vectors) = 1+\binom{n-k+1}{1} + ... + \binom{n}{k}$. And for all $k$-s starting from $k=2$(as for sure $\lambda_{1}=0$, as you have written), we will have $$\#(vectors) = \sum_{k=2}^{n}\sum_{i=0}^{k}\binom{n-k+i}{i}$$
We can write a recurrence. Define $N(p,n)$ as the number of strictly increasing sequences of length $p$ with maximum term no more than $n$ and minimum term at least $1$. $p$ here corresponds to $n-k+1$ in your question. The recurrence is $N(p,n)=N(p-1,n-1)+N(p-1,n-1)$ where the first term covers the sequences that end in $n$ and the second term covers those that do not end in $n$. The boundary conditions are that $N(k,k)=1$ as you must have the sequence from $1$ to $k$ and $N(0,n)=1$ as there is one empty sequence. The number of acceptable sequences of length $n$ is then $\sum_{i=0}^nN(i,n)$ because we can pad the ones shorter than $n$ with any number of zeros. It turns out $N(p,n)={n \choose p}$-this is Pascal's triangle. The sum just sums the entries in row $n$ in Pascal's triangle, which is known to sum to $2^n$