• Support PF! Buy your school textbooks, materials and every day products Here!

Highest value in combinations

  • Thread starter Crystal037
  • Start date
83
3
Homework Statement
If n is an even natural number, then the greatest value of nCr is nCn/2 and if n is odd, then the greatest value of nCr is nC(n+1)/2 and nC(n-1)/2
Homework Equations
nCr=n!/(n-r)!r!
I know nCn/2 = n!/((n/2)!)^2 = 2^(n/2)(1.3.5.....n-1)
but I am not getting why it's the least one.
 
83
3
For 2n, n is a natural number,
2nCn = 2n!/n!n! = Highest value of nCr
Let r=k+n for a natural number,k
2nCn = 2nCr.(n+1)(n+2)....(n+k)/n(n-1)...(n-k)
Eg, when 2n=12, n=6
highest value of 12Cr should be 12C6
12C6 = 12*11*10*9*8*7*6*5*4*3*2*1/(6*5*4*3*2*1)(6*5*4*3*2*1) =12*11*10*9*8*7/(6*5*4*3*2*1)
for any other value of r let r=9, then 9=k+6 which implies k=3
12C9=12*11*10*9*8*7*6*5*4*3*2*1/(9*8*7*6*5*4*3*2*1)(3*2*1) =12*11*10/(*3*2*1)
which is less than 12C6 by a factor of (9*8*7)/(6*5*4) = (6+1)(6+2)(6+3)/6(6-1)(6-2)
If n=2m+1, m is any natual number i.e. n is an odd no.,
nC(n+1)/2, nC(n-1)/2 =Highest value of nCr
nC(n+1)/2=nCr.((n+1)/2+1)((n+1)/2+2)....((n+1)/2+k)/((n-1)/2)((n-1)/2-1)....((n-1)/2-k)
Eg for n=11 highest value of 11Cr should be 11C6
since, n=11, (n+1)/2=6, (n-1)/2=5
11*10*9*8*7*6*5*4*3*2*1/(6*5*4*3*2*1)(5*4*3*2*1)=11*10*9*8*7/5*4*3*2*1
for any other value of r let r=9, then 9=k+6 which implies k=3
11C9=11*10*9*8*7*6*5*4*3*2*1/(9*8*7*6*5*4*3*2*1)(2*1)
which is less that 11C6 by a factor of 9*8*7/5*4*3=(6+1)(6+2)(6+3)/(6-1)(6-2)(6-3)
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
10,409
3,959
If you are trying to prove this, you could look at the general pattern that binomial coefficients, for a given ##n##, get larger until they reach a peak and then get smaller. You could think about why they get larger then smaller.
 

WWGD

Science Advisor
Gold Member
4,864
2,160
Maybe you can look at Pascal's triangle and the recursion rule. Notice each row's entries are symmetric so you dont need to consider all the entries.
 
83
3
I can't understand how to use recursion rule to say if a term is the highest
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
10,409
3,959
83
3
the answer would be k/(n-k+1), then how to proceed
 

WWGD

Science Advisor
Gold Member
4,864
2,160
I can't understand how to use recursion rule to say if a term is the highest
Write down first few , 2-3 lines explicitly and the mid terms are the largest. For the general nth row, the midterm will be the sum of the two largest in the previous row. Take,e.g., the 3rd and 4th row: 1,3,3,1 and 1 , 4, 6, 4, 1. The 6 in the 4th row is the sum of 3,3 , both largest terms , so it must be larger than all other terms in the row.
 
83
3
Oh yes, the middle terms are always greater than the other terms because they are the sum of the largest terms from the previous row. Thanks.
And the formula I wrote in #2 is that correct.
 

WWGD

Science Advisor
Gold Member
4,864
2,160
Oh yes, the middle terms are always greater than the other terms because they are the sum of the largest terms from the previous row. Thanks.
And the formula I wrote in #2 is that correct.
Yes, though the two are separate arguments.
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
10,409
3,959
the answer would be k/(n-k+1), then how to proceed
That's not right. E.g. try ##k =0##.

The idea is that ##a > b## if and only if ##a/b > 1##, assuming ##a, b## are positive. Really, you have to be able to think of something like this for yourself.

You need to decide whether to concetrate on this approach or the approach based on Pascal's triangle. I would say, however, that if you use Pascal's triangle, then you have be careful to prove everything that you are seeing from the triangle.

For example, it's been quoted that the triangle is symmetrical. But, you can't use the symmetry of the triangle unless you prove it. In fact, it's part of the symmetry of the triangle that you are trying to prove in this problem.
 

WWGD

Science Advisor
Gold Member
4,864
2,160
That's not right. E.g. try ##k =0##.

The idea is that ##a > b## if and only if ##a/b > 1##, assuming ##a, b## are positive. Really, you have to be able to think of something like this for yourself.

You need to decide whether to concetrate on this approach or the approach based on Pascal's triangle. I would say, however, that if you use Pascal's triangle, then you have be careful to prove everything that you are seeing from the triangle.

For example, it's been quoted that the triangle is symmetrical. But, you can't use the symmetry of the triangle unless you prove it. In fact, it's part of the symmetry of the triangle that you are trying to prove in this problem.
Good point, my argument does assume that symmetry. Op should prove nCk=nC(n-k).
 
83
3
That's not right. E.g. try ##k =0##.

The idea is that ##a > b## if and only if ##a/b > 1##, assuming ##a, b## are positive. Really, you have to be able to think of something like this for yourself.

You need to decide whether to concetrate on this approach or the approach based on Pascal's triangle. I would say, however, that if you use Pascal's triangle, then you have be careful to prove everything that you are seeing from the triangle.

For example, it's been quoted that the triangle is symmetrical. But, you can't use the symmetry of the triangle unless you prove it. In fact, it's part of the symmetry of the triangle that you are trying to prove in this problem.
Oh sorry
The answer should be (n-k)/(k+1)
 
83
3
Good point, my argument does assume that symmetry. Op should prove nCk=nC(n-k).
How proving nCk=nC(n-k) would help in proving the symmetry
 

WWGD

Science Advisor
Gold Member
4,864
2,160
Because this shows that the kth term in a row equals the (n-k) th term. But for induction you can just try to show that if you have the highest term in the middle in the jth row you will also have it in the (j+1)st row by adding the two central terms.
 
83
3
So using the pascal triangle we found what the highest value of nCr is.
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
10,409
3,959
So using the pascal triangle we found what the highest value of nCr is.
The triangle you're looking at is only finite. How do you know the pattern continues?
 
83
3
By using mathematical induction, can't I prove it?
 

WWGD

Science Advisor
Gold Member
4,864
2,160
We haven't done anything yet Chrystal, this was just an idea and it needs to be fleshed out. I think @PeroK. 's idea seems closer to a solution. You may, of course, work both out.
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
10,409
3,959
83
3
Using Pascal triangle ,
we know that the middle terms are greater, since they are found by adding the above middle terms which are greater & this leads us to the 2nd index where the greater term started as 2 which was due to the fact that we added the only 2 numbers in the 1st index 1 &1, which came from 0th index i.e.1
Screenshot_2019-10-14-00-17-54-721_com.google.android.apps.docs.jpg
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
10,409
3,959
That's far from a rigorous mathematical proof. The result can be seen informally by looking at the triangle. But, you need to put together a formal inductive proof.
 
83
3
What do you mean by formal inductive proof? Give me some hint on how to begin with
 

Related Threads for: Highest value in combinations

Replies
14
Views
862
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
3
Views
1K
Replies
3
Views
589
  • Last Post
Replies
4
Views
852
  • Last Post
Replies
2
Views
6K
Replies
2
Views
2K
  • Last Post
Replies
12
Views
1K

Hot Threads

Recent Insights

Top