Need some explanation on the combinatorics formula nCr= n-1Cr + n-1Cr-1

nCr= n-1Cr + n-1Cr-1 is a famous recursive equation for computing nCr , where nCr means number of ways selecting r objects from n objects.
I have read in high school the logical meaning of this formula.
I remember my teacher saying that to calculate number of ways of selecting r objects from n objects(nCr) , we can either discard object at r postion(i.e n-1Cr-1) , or we can include the object at r position (i.e n-1Cr).but I don’t understand this logic now …!! can someone plz explain me this with some example or any editorial…??
Thank you.

2 Likes

@va1ts7_100 It can be understood as, suppose you want to select a group of r students out of N students, which can be done in \binom{N}{r} ways. Then, for each student there are two possibilities that either it would be selected in that group of r students or it will be rejected. Let, out of these N students there is a student ’A’ which will either be selected in group of those r students or won’t be selected. If you select A in the group then you have total N-1 students left and you have to select remaining r-1 students, which can be done in \binom{N-1}{r-1} ways, and if you don’t select ’A’ then you have total N-1 students left and you have to select r students from it which can be done in \binom{N-1}{r}. So, the total number of ways of selecting r students out of N students is equal to \binom{N-1}{r} + \binom{N-1}{r-1}.

21 Likes

good explanation… lucid … :slight_smile: thanks :slight_smile:

2 Likes

Really, wonderful explanation. Thank you very much, bro.

Amazing explanation! Thank you.

1 Like