### AngelKnows's blog

By AngelKnows, history, 4 months ago,

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?

• +14

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