# Find recurrence or formula for all labelings

There is a sequence $x_1, x_2, \ldots , x_n$. A valid labeling from $[1, k]$ is defined as for any $i, j \in [1, n]$, such that $i < j$: $$\mathrm{label}[i] \leq \mathrm{label}[j].$$ For $n=2$ and $k = 2$, a valid labeling would be :- $$1 \;\;1,\\ 1 \;\;2,\\ 2 \;\;2.$$

How many such labelings are possible. I tried to find if there is a recurrence. Following attempt at it does not work. $$F(n, k) = F(n-1, k) + F(n-1, k-1)$$ $$F(1, k) = k\\ F(n, 1) = 1$$

However that will include duplicates as well.

Thanks

-
@joriki. I have fixed the typo. Thanks for pointing out – user434345 Mar 1 '13 at 8:19

You don't need a recurrence for this: The valid labelings of $n$ items with $k$ labels are in bijection with the multisets of $n$ items chosen from $k$, of which there are $\binom{n+k-1}n$.
If you want a recurrence nevertheless, note that given a valid labeling of $n$ items with $k$ labels, you can get a valid labeling of $n+1$ items with $k$ labels by inserting another label. Each of the $k$ labels can be inserted in one particular spot only, directly before its minimal upper bound among the existing labels, except each of the $n$ existing labels affords an additional opportunity of placing an identical label behind it. That makes $n+k$ ways of inserting a label. You get each valid labeling of $n+1$ items $n+1$ times in this manner (since there are $n+1$ choices which item to insert), so this yields
$$(n+1)F(n+1,k)=(n+k)F(n,k)\;,$$
$$(n+1)\binom{n+1+k-1}{n+1}=(n+k)\binom{n+k-1}n\;.$$