# Sara was smart and popular

Sara was very popular in her high school. She was not a cheerleader, yet everyone in the school knew and adored her – partly because she was smart and also because she was kind. She had helped so many of her classmates and junior students without putting them down. In the final school year, Sara had the top mark in every subject. Sure there were some students who were jealous of her but even they spoke highly of her because she had helped them at some point. It is for these reasons that she was the class valedictorian. After the graduation speech she gave, her stardom in the school rose to even greater heights.

Sara was in love with Johnny. They had been going together for almost four years. Johnny was also very popular because of his participation in sports and his social nature but also because his classmates knew how, in the last two years, he had transformed himself from being a C student to a student with an average of over 85%. He also graduated along with Sara.

# Joint graduation party for Sara and Johnny

Sara’s parents were very proud of their daughter’s achievements. Even more proud was her Nana who had practically raised Sara. Nana proposed a memorable graduation party for Sara and she wanted to pay for it. Johnny’s mom also wanted to have a super duper party for his graduation. Sara and Johnny proposed that the two parties should be combined because they would end up inviting almost the same people in both the parties anyway. Sara’s Nana and Johnny’s mom happily conceded to this idea. Nana also suggested that only the friends of Sara and Johnny should be invited. There was no need for parents and their friends to attend. It would be good for the young people to have some fun. She did not want Sara to have an overnight stay because of the party though. They decided on a date and a time, and then booked a place for the party. Actually, the venue for the party was a meeting room in a hotel. The room also had a large screen on one of the walls, and all the equipment to show pictures or movies. They would have this room to themselves.

# How to narrow down the list of invitees?

Sara and Johnny did not want to invite the whole world to the party, just a few very close friends. They agreed that the number of people at the party would be 12, including themselves. There was a problem – how to narrow down the list of the invitees because both were very popular but together they could invite only 10 people.

Sara: I have 50 friends at the school who would want to be invited.

Johnny: Same with me. So, together we have 100 people out of whom we want to invite 10. Do you know how many different possible combinations are there for 10 friends to be invited out of 100?

Sara: Are you joking or do you really want to figure this out?

Johnny: Just curious. Yes, I want to find out.

Sara: Have you studied this type of Math before?

Johnny: I don’t believe I have. You know all the courses I took.

Sara: If you are serious about this curiosity, I will work this out with you. But to make sense of things, let me start very small. Suppose there are 7 people, out of whom 5 are to be invited. Let’s start figuring it out by saying who sits in seat number 1.

Johnny: Any of the 7 could sit in seat 1. I don’t see a problem there.

Sara: So there are 7 possibilities. For each of these situations, how many possibilities exist for seat 2.

Johnny: For seat number 2 there are 6 possibilities because one person is already committed to seat number 1. I get it then for each of these possibilities, there would be 5 for the third seat, and so on until for the last seat there would be only 3 possibilities.

Sara: So the total number of possibilities would be 7 x 6 x 5 x 4 x 3. In Math, we use the term factorial. Factorial for an integer n is n x (n-1) x (n-2)…….1, and it is written as n! So the arrangement of seats we chose will be called the permutation ^{7}P_{5}.

^{7}P_{5} = 7 x 6 x 5 x 4 x 3 = 7 x 6 x 5 x 4 x 3 x 2 x 1/(2 x 1) = 7!/2! = 2520

Johnny: But, we don’t care about who sits in which chair, just who gets invited.

Sara: I know, I am getting there – just going stepwise. Now, let’s say if there are 5 people and 5 seats.

Johnny: Like before, there are 5 possibilities for seat 1, 4 for seat 2, 3 for seat 3 and 2 for seat 4 and only 1 for seat 5. The total possibilities for this arrangement will be 5!.

Sara: Now back to 5 people being invited out of 7. We already said that there are 5! possibilities for seating arrangements for 5 friends. We also know that the total number of possibilities for choice and seating arrangement for 5 friends out of 7 is ^{7}P_{5}. When we don’t care where anyone sits but only for who will be invited, I can divide the permutation ^{7}P_{5} by 5!. Therefore, I would say that for the invitation only the possible number of combinations is:

^{7}C_{5} = ^{7}P_{5}/5! = 2520/5! = 21

Johnny: There are a lot of different combinations for invitations even for 5 out of 7. Let me see if I can write in general what you did for n friends out of whom r are to be invited.

If we care about the seating arrangement, we write: ^{n}P_{r} = n!/(n-r)!

If we want the combinations without the seating arrangement, we write: ^{n}C_{r} = n!/((n-r)! x r!)

Sara: Johnny my love, you catch on quick.

Johnny: Because we have 100 friends and we want to invite only 10, just out of curiosity how would that work out? This would mean n = 100 and r = 10.

Sara: ^{100}C_{10} = 100!/(10! x 90!) is a large number. 100! is so large that many calculators will give you an error message. I am using a program on my laptop for ^{100}C_{10}. The answer is 1.73 x 10^{13 }which is more than than 17 trillion combinations. Remember, this is the number of combinations for invitations only without considering the seating preferences. If we also include the seating arrangement, this number will be even bigger. ^{100}P_{10} = 100!/ 90! or 6.28 x 10^{19}.

# So much for the curiosity

Johnny: So much for that curiosity. Let’s make it simpler. Say you choose 5 out of your 50 friends and I choose 5 out of my 50 buddies. Will the number for all possible combinations for invitations be smaller?

Sara: Only for my invitations there will be ^{50}C_{5} = 50!/(5! x 45!) or 2,118,760 possible combinations. The same for yours. Assuming that we don’t have any common friends in our list, for one of us only there will be 2,118,760 possible combinations. So the combined combinations will be 2118760 x 2118760 or 4.49 x 10^{12}. The number is slightly smaller than 1.73 x 10^{13},^{ }but still nothing we want to handle.

Johnny: Look, it’s clear that this way is not going to work. Also we should invite only the friends we like most. Why don’t we each just choose 5 persons who we like most?

Sara: Not so simple. If we invite a friend, do we also invite their girlfriend or boyfriend?

Johnny: Of course but then that limits for each of us to inviting only two friends and their dates. Each of us will still have one more person left to invite. Could we invite someone who is not dating any one?

Sara: How would they feel about it when everyone else is there with a date except for them?

Johnny: That leaves two options. One is that we invite one more couple together.

Sara: What’s the other?

Johnny: Invite the nerds Joe and Pete. They are good friends with each other. They wouldn’t care if others came with a date. In a way, they are entertaining.

Sara: Okay. You tell me your two friends you want to invite.

# Final invitees and seating arrangements

Johnny named two friends and then Sara did the same. This way there was no duplication in the list of the invited friends.

Sara: Do we want to decide on any seating arrangements? We leave space open on one side so all of us can see the screen. This way, we don’t have to think of it as a circle. For random seating there are ^{12}P_{12} possibilities. You know that comes out to almost 500 million. Besides, random seating is not going to happen even if we asked everyone to sit anywhere they like. The couples who come together will probably sit together any way. So will Joe and Pete.

Johnny: Why don’t we say sit anywhere but together to each person and their date? Same goes for Joe and Pete. That will make ^{6}P_{6} possible seating arrangements.

Sara: That number is 720 but there is a flaw in your calculations. We did not decide whether the boy will sit on the right and the girl on the left or the other way around. If we account for that detail, the number of possibilities will be 720 x 720 because any boy might sit on the right of his girlfriend or not. Each pair may have a different choice in that matter. So that becomes over half a million different permutations.

Johnny: What if we didn’t leave an area open and we were to form a circle? Would that make more combinations or fewer?

Sara: If there are n! linear permutations, there will be corresponding (n-1)! circular ones. That will change the number of permutations from 6! to 5! or 120. But if you want to distinguish between who sits left from who sits right in each pair, there will be 120 x120 or 14400 possibilities.

Johnny: That’s confusing. Do you want to let it be like that or make additional conditions in the sitting arrangement?

Sara: What about if I sit to the left of you and exactly opposite to me is Joe and opposite to you is Pete. The friends I invite sit to the left of me and those whom you invite sit to your right. They may be more comfortable that way.

Johnny: Assuming that the couples will sit next to each other, that makes 4 possibilities on your side and 4 on mine. That’s a total of 16 possibilities.

Sara: Are you comfortable with that?

Johnny: I could live with it.

All the guests were invited. Everyone came and had a good dinner. They reminisced for hours about each and every memory in their high school years. Some of them had recordings of events stored in different media and they showed them to everyone. They all enjoyed and joked around.

# Joe told a joke.

A math Prof asked his wife for the combination of a lock. She said, “35-25-15”. The Prof told his wife that the combination didn’t work. The wife asked him, “What numbers did you try?” He said,”15-25-35″. She said to the Prof, “Honey, I don’t know what I am going to do with you.” Pete started to laugh hilariously saying. “Ha, ha, combination!”

*Challenge*

* Solutions 1. *You cannot do this simply by determining the values of the two factorials using a calculator and then diving the numerator by the denominator. Try it, you will get an error message because the values are very large. Let’s do it this way

50001!/49999!. = (50001 x 50000 x 49999!)/(49999 !) = 50001 x 50000 = 2500050000.

*Challenge 2*. You have to take 5 subjects this semester. You have a total of 8 subjects to choose from except that you must take English as a compulsory subject. What are the total possible combinations for you to choose from ?

* Solutions 2. *English being compulsory is neither to be considered in the number of subjects nor in the number of choices. Therefore, you have to choose 4 subjects out of 7. The number of choices is:

^{7}C_{4 }= 7!/(4! x (7-4)!) = 7 x 6 x 5 x 4……1/((4 x 3…1) (3 x 2 x 1) = 7 x 6 x 5/ (3 x 2 x 1) = 35.