1
$\begingroup$

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$ and $\forall i\not=k, cnt(i)\not=i$. Let $f(n,k)$ be the number of all $k$-good arrays of length $n$ whose elements are between $1$ and $n$.

For example, $4,2,3,3,3$ is a $k$-good array for $n=5,k=3$, but $2,2,3,3,3$ is not a $k$-good array for $n=5,k=3$, because $cnt(2)$ also equals to $2$ so you can't tell from what $k$ the array is derived.

I am wondering if there is a recursive formula for $f(n,k)$.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ Hao, you may want to ask on math.stackexchange.com which is for "math at any level" (while MathOverflow is for "research level mathematics"). Before you do that, you'll want to clarify your question a little. Your quantity probably depends on both $n$ and $k$ so better call it $f(n,k)$. You could also work out some small cases manually and check if your sequence is in OEIS (oeis.org). $\endgroup$ Commented Jan 27, 2021 at 11:22
  • $\begingroup$ I find a related problem in math.stackexchange.com/questions/3509979/…, the only difference between them is that my problem requires only one k satisfying $cnt(k)=k$ which make it much harder. $\endgroup$ Commented Jan 27, 2021 at 11:35
  • $\begingroup$ Unless $n$ is a triangle number, there are 0 arrays. Then, if it is a triangle number, then the answer is a multinomial coefficient. $\endgroup$ Commented Jan 27, 2021 at 11:52
  • $\begingroup$ @PerAlexandersson Could you explain the details? At least $1,2,3,3,3$ is a good array for $n=5,k=3$ though $5$ is not a triangle number. $\endgroup$ Commented Jan 27, 2021 at 12:25
  • $\begingroup$ The question has been clarified but I still don't quite understand it. If the condition for $k$-good is that there are $k$ occurrences of $k$, then [2,2,3,3,3] is both 2-good and 3-good. Do you mean that there has to be exactly one such $k$ for the array to be $k$-good? This is not quite what the definition says. $\endgroup$ Commented Jan 27, 2021 at 12:26

1 Answer 1

Reset to default
5
$\begingroup$

By standard properties of exponential generating functions, e.g., Sections 5.1-5.2 of Enumerative Combinatorics, vol. 2, $f(n,k)$ is the coefficient of $x^n$ in $$ n!\frac{x^k}{k!}\prod_{\substack{i=1\\ i\neq k}}^n \left( e^x-\frac{x^i}{i!}\right). $$

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.