Seeking a better solution for a counting problem

Revision en2, by AngelKnows, 2021-01-22 07:03:34

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?

Tags #dp, #math, #combinatorics


  Rev. Lang. By When Δ Comment
en2 English AngelKnows 2021-01-22 07:03:34 5 Tiny change: 'number of $k$-good array. You are ' -> 'number of all $k$-good arrays. You are '
en1 English AngelKnows 2021-01-22 06:58:27 563 Initial revision (published)