AngelKnows's blog

Seeking a better solution for a counting problem
By AngelKnows, history, 4 years ago, In English

Problem: Suppose $$$cnt(i)$$$ represents the number of occurrences of $$$i$$$ in array $$$A$$$ of length $$$n$$$ whose elements are between $$$1$$$ and $$$n$$$. An array is called a $$$k$$$-good array if and only if $$$cnt(k)=k$$$. Let $$$f(k)$$$ be the number of all $$$k$$$-good arrays. You are to calculate the $$$\sum\limits_{k=1}^n f(k)$$$.

This problem looks like some dp problems which can be reduced to a simper form and solved by Kunth's Mechanical Summation. But I haven't thought up a good solution.

Could you share your ideas about this problem?

  • Vote: I like it
  • +14
  • Vote: I do not like it

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

Auto comment: topic has been updated by AngelKnows (previous revision, new revision, compare).

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

Can you also add constraints and the problem link? People often ask for problems from a running contest, so it's good to add a link to the problem. Constraints are also important, as they tell you what kind of approaches to consider.

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

The answer is $$$n^n - (n-1)^n$$$.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    $$$ \begin{equation} \begin{aligned} \sum_{k=1}^{n}f(k)&=\sum_{k=1}^{n}\binom{n}{k}(n-1)^{n-k} \\ &=\sum_{k=0}^{n}\binom{n}{k}(n-1)^{n-k}1^k-\binom{n}{0}(n-1)^n \\ &=n^n-(n-1)^n \end{aligned} \end{equation} $$$
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't think $$$f(k)=C(n,k)(n-1)^{n-k}$$$, because there should be only one k satisfying $$$cnt(k)=k$$$. For instance, $$$2,2,3,3,3$$$ is not 3-good array because we have both $$$cnt(3)=3$$$ and $$$cnt(2)=2$$$.

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

If N is small, I can think of using inclusion-exclusion, what are the constraints of this problem?

→ Reply