7
$\begingroup$

I have the following problem:

$$ N^n(N-n)!=A $$

Where $N$ and $A$ are constants. I want to solve this equation for $n$ (for a variation of the birthday problem), but I have little experience with combinatorics.

An approximate answer is acceptable, so I've tried using Stirling's approximation, but no matter how I manipulate it, I can't get an answer to fall out.

Any guidance would be appreciated.

$\endgroup$
5
$\begingroup$

The best method is going to depend quite a bit on the relative sizes of $N$ and $A$, but here's an idea that might work well in practice.

Divide both sides of the equation by $N!$ to yield $$ \frac A{N!} = \frac{N^n(N-n)!}{N!} = \prod_{j=0}^{n-1} \bigg( 1 - \frac jN \bigg)^{-1}. $$ Take logs of both sides to obtain \begin{align*} \log \frac A{N!} &= \sum_{j=0}^{n-1} \log \bigg( 1 - \frac jN \bigg)^{-1} \\ &= \sum_{j=0}^{n-1} \bigg( \frac jN + O\bigg( \frac{j^2}{N^2} \bigg) \bigg) \\ &= \frac{n(n-1)}{2N} + O\bigg( \frac{n^3}{N^2} \bigg). \end{align*} For many ranges of $N$ and $A$, this shows that $n$ will be about $\sqrt{2N\log(A/N!)}$.

$\endgroup$
4
  • $\begingroup$ Thanks, Greg, this is very useful...I'm going to ponder this for a bit. $\endgroup$ Aug 12 '13 at 21:38
  • $\begingroup$ Thanks so much, Greg. I would like to ask you some questions about your approach and where I can learn more about some of the manipulations you used. If you're down, could you email me at e@zepln.com? $\endgroup$ Aug 13 '13 at 16:24
  • $\begingroup$ @EthanBrown: I might be a little too busy to be a good resource for you. Maybe edit this problem to include your additional questions, or start a new problem, to take advantage of crowdsourcing? $\endgroup$ Aug 14 '13 at 7:58
  • $\begingroup$ No problem, I understand how that goes! Thanks again for your answer. $\endgroup$ Aug 14 '13 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.