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?
Auto comment: topic has been updated by AngelKnows (previous revision, new revision, compare).
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.
The answer is $$$n^n - (n-1)^n$$$.
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$$$.
If N is small, I can think of using inclusion-exclusion, what are the constraints of this problem?