Re: Need help: Binomial Coefficients Problem
- From: Ronald Bruck <bruck@xxxxxxxxxxxx>
- Date: Mon, 30 Jan 2006 20:18:52 -0800
In article <1138673025.660488.197050@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
tutorny <tutorny@xxxxxxxxx> wrote:
> I have the following problem:
>
> I solved the probability of some event to be equal to:
> C(10,2)*C(k-10,18)/C(k,20).
>
> The problem asks to find the value of k for which that probability is
> maximized.
>
> So, I set C(10,2)*C(k-10,18)/C(k,20) = 1.
>
> Can somebody help me solve this problem? I think that some rule of
> binomial coefficients must apply to make this really simple, but can't
> think of which one. The answer is k=100, but I have no idea what
> procedure to follow to get it.
For this to be a probability, we must have k >= 28.
k = 99 is also a solution. But why do you think 1 is the maximum? The
actual maximum is 101355025/318555566, and you're unlikely to get it
without some kind of computer. On the other hand, you can figure out k
= 99 with hardly any calculation.
Remember that C(a,b) = a * (a-1) * (a-2) * ... * (a-b+1)/b! Thus when
you plug in a = k-10 and b = 18 you get a polynomial in k of degree 18:
(k-10)(k-11)....(k-27)
C(k-10,18) =------------------------
18!
and similarly
k(k-1)...(k-19)
C(k,20) =-------------------
20!
Forget about the C(10,2), the 18! and the 20! -- these combine to give
only a constant multiple. When you compute your solution you get a
polynomial of degree 18 divided by a polynomial of degree 20. But
there are some factors in common: k-10, k-11, ... through k-19.
Cancelling these, your probability is of the form
(k-20)(k-21)...(k-27)
const * ---------------------
k(k-1)....(k-9)
i.e. a polynomial of degree 8 over a polynomial of degree 10. If you
set
(k-20)(k-21)...(k-27)
g(k) = ---------------------
k(k-1)....(k-9)
Now the ratio of the probabilities for k+1 and k is exactly
g(k+1) (k-9)(k-19)
------ = --------------
g(k) (k+1)(k-27)
It's easy to find where g(k+1) < g(k) and g(k+1) < g(k): for values
with k >= 28,
(k-9)(k-19) < (k+1)(k-27) <==> -28k + 171 < -27 - 26k <==> 99 < k
while
(k-9)(k-19) > (k+1)(k-27) <==> -28k + 171 > -27 - 26k <==> 99 > k.
Thus g(99) = g(100) and this is the maximum value of g on the integers
>= 28.
In this form you should be able to generalize the problem.
--Ron Bruck
.
- References:
- Need help: Binomial Coefficients Problem
- From: tutorny
- Need help: Binomial Coefficients Problem
- Prev by Date: Archimedes Pi Algorithm
- Next by Date: Re: So weak
- Previous by thread: Re: Need help: Binomial Coefficients Problem
- Next by thread: Re: Need help: Binomial Coefficients Problem
- Index(es):
Relevant Pages
|
|
