Блог пользователя saurabhs1206

Sequences of length n with exactly k distinct elements
Автор saurabhs1206, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • -21
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)

→ Ответить