saurabhs1206's blog

Sequences of length n with exactly k distinct elements
By saurabhs1206, history, 3 years ago, In English

I wish to find the count of sequences of length n consisting of exactly k distinct elements. Can't think of any approach to this.

  • Vote: I like it
  • -21
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

K distinct out of what? What's the total number of values for 1 element?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Assuming you want sequences with values <= X, you can solve it this way: having the k values fixed, how many sequences can you create? Well, the answer is equivalent with finding in how many ways can you write number n as sum of k positive numbers, which is C(X-1, k-1). So now in how many ways can we fix the k elements? C(n, k) is the answer. So the total answer would be C(n, k) * C(X-1, k-1)

→ Reply