1

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.

Please help.

Thanks

user434345
  • 113

1 Answers1

2

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)\;, $$

and indeed

$$ (n+1)\binom{n+1+k-1}{n+1}=(n+k)\binom{n+k-1}n\;. $$

joriki
  • 238,052