1
00:00:00,230 --> 00:00:07,190
In this video, let's step aside for a moment to quickly discuss what NCR is.

2
00:00:07,220 --> 00:00:16,550
So NCR is a notation that indicates the number of ways in which you can choose our things from n things.

3
00:00:16,550 --> 00:00:23,060
For example, if n is five and r is two, you would get five, c two and five.

4
00:00:23,090 --> 00:00:29,810
C two represents the number of ways in which you can choose two items out of five items.

5
00:00:29,810 --> 00:00:32,540
For example, let's say you have five people over here.

6
00:00:32,540 --> 00:00:39,260
And if you want to create a group of two people, then to identify the number of ways in which you can

7
00:00:39,260 --> 00:00:41,930
do this, you can just do 5C2.

8
00:00:41,960 --> 00:00:43,850
Now there is a formula for this.

9
00:00:43,850 --> 00:00:45,650
We'll come to that in a minute.

10
00:00:45,650 --> 00:00:52,250
But to first build a solid understanding of what NCR is let's take an example.

11
00:00:52,250 --> 00:00:55,130
So over here I have a b c d e.

12
00:00:55,250 --> 00:01:00,020
Now let's say I want to choose two letters out of these five letters.

13
00:01:00,020 --> 00:01:06,830
Now the different ways in which I can do that is I could have a and B, a and C, a and d or a and e

14
00:01:06,860 --> 00:01:11,780
b and c, b and d b and e c, d, c and d.

15
00:01:11,870 --> 00:01:13,970
So over here I have four ways.

16
00:01:13,970 --> 00:01:16,610
We have three ways then two and one.

17
00:01:16,610 --> 00:01:24,860
So the total number of ways in which I can choose two items out of five items is equal to ten.

18
00:01:24,860 --> 00:01:31,910
So there are ten ways of doing it now because writing out things in this manner is difficult and not

19
00:01:31,910 --> 00:01:33,260
always practical.

20
00:01:33,260 --> 00:01:37,910
There is a formula that we can use to calculate 5C2.

21
00:01:37,910 --> 00:01:46,160
So NCR is actually equal to n factorial by r factorial into n minus r factorial.

22
00:01:46,490 --> 00:01:52,100
So 5C2 would be five factorial divided by two factorial.

23
00:01:52,100 --> 00:01:58,640
Because r is equal to two and then you have n minus r factorial which is five minus two factorial.

24
00:01:58,640 --> 00:02:02,570
Now five factorial is just five into four into three into two into one.

25
00:02:02,780 --> 00:02:06,110
And then you have two factorial and you have three factorial over here.

26
00:02:06,110 --> 00:02:10,700
So five into four into three into two into one.

27
00:02:10,700 --> 00:02:16,880
And then two factorial is just two into one which is two and three factorial is three into two.

28
00:02:16,910 --> 00:02:22,730
Now on simplifying notice that this becomes five into two which is equal to ten.

29
00:02:22,730 --> 00:02:25,490
And that's what we got over here so quickly.

30
00:02:25,490 --> 00:02:33,110
Recapping NCR represents the number of ways in which we can choose our things out of n things.

31
00:02:33,110 --> 00:02:41,510
And to find NCR you can just do n factorial divided by r factorial into n minus r factorial.

32
00:02:41,540 --> 00:02:48,530
Now, the reason why I have discussed this over here is because this concept is helpful when we discuss

33
00:02:48,530 --> 00:02:54,320
the time complexity of the approach that we have discussed so far for solving the palindrome partitioning

34
00:02:54,320 --> 00:02:54,800
question.

35
00:02:54,800 --> 00:02:57,650
Let's see more of that in the next video.