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.

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

share|improve this question
    
@joriki. I have fixed the typo. Thanks for pointing out –  user434345 Mar 1 '13 at 8:19

1 Answer 1

up vote 2 down vote accepted

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\;. $$

share|improve this answer

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.