Undergrad What is the value of n in Reverse Combinatorics problem?

[hotvette]

TL;DR

Combinations with repetition

Not homework, just working odd numbered problems in the book.

Sue has 24 each of n different colored beads. If 20 beads are selected (with repetition allowed) what is the value of n if there are 230,230 possible combinations. I view this as a problem of number of integer solutions to a linear equation, thus:

$x_1 + x_2 + \dots + x_n = 20, x_i \ge 0$ has $C(n+20-1,20) = C(n+19,20) = \frac{(n+19)!}{20!(n-1)!} = 230,230$ solutions, which means the task is to solve for $n$. I managed to get the correct answer ($n=7$) by trying different values of n. What I'm wondering is if there is a reasonable way to determine $n$ algebraically. I can't see any.

 

[andrewkirk]

We can rearrange the equation to be a polynomial equation:
$$p(n)=0$$
where $p$ is the following degree-20 polynomial:
$$p(n) = \prod_{k=1}^{20} (n-k+1)- 230230\times 20!$$

We can then use techniques for root-finding to find the answer.

While that is an 'algebraic' technique it is not at all suitable to the problem. There will be up to twenty roots to be found and only one of them will be the n that we want.

It is more efficient to just start with $n=1$ and keep increasing it until the solution is found.

 

[hotvette]

Thanks!

 

[WWGD]

Maybe finding the factors of 230,230 will help narrow down the values of n.