# Factorial Word Problem

Here is the problem:

"The traditional French greeting is to kiss the other person on each cheek. So, when two traditional French friends meet, one kisses the second on both cheeks and the second person kisses the first on both cheeks. a. Make an In-Out table where the In is the number of friends meeting and the Out is the total number of kisses. Your Ins should go from 1 through 6 at least. b. Write a formula for the total number of kisses, k, in terms of the number of friends, f."

So I think that the formula has something to do with factorial but I cannot find a formula. I have a table with points (1,2), (2,6), (3,24), (4,120), (5,720) and (6, 5040). Where x is the number of friends you meet with and y is the total number of kisses. Is this correct?

-

The counts do not seem to be right. If there is only $1$ person in the group, there are $0$ kisses.

If there are $2$ people in the room, there are $4$ kisses (A kisses B on both cheeks, $2$ kisses, B reciprocates, $2$ more).

Now look at the case of $3$ people, A, B, and C. Again we can make an explicit count. For A and B, we have $4$ kisses. For A and C, $4$ more, and finally for B and C, $4$ more, for a total of $12$.

If you have a certain amount of patience, you can deal with $4$ people, A, B, C, and D. First A exchanges kisses with B, C, and D. That's $12$ kisses. Now B, C, and D exchange kisses with each other. That's the case of $3$ people, which we have already solved! So they account for $12$ more, for a total of $24$.

Now deal with $5$ people, A, B, C, D, and E. First A does the kiss thing with B, C, D, and E. That's $16$ kisses. Then B, C, D, and E exchange kisses. That's already been computed, it is the $4$ people case, we get $24$. so the total is $16+24$. which is $40$.

Finally, deal with $6$ people, A to F. First A exchanges kisses with the $5$ others, total $20$. Then the remaining $5$ exchange kisses, total $40$. The sum is $60$.

To get a general formula, there are many approaches. We could follow up on our analysis above. Or we could start again.

For every pair of friends, there will be $4$ kisses. Do you know a simple formula for the number of pairs there are if there are $f$ friends in the group?

If you do not, here is a way of counting. We will call the people by the even more boring names $1,2,3,4,\dots,f$. Let us first count the number of ordered pairs $(x,y)$ that we can form. The first person in the ordered pair can be chosen in $f$ ways. For each of these ways, the second person can be chosen in $f-1$ ways. So the total number of ordered pairs is $f(f-1))$. But this is not the number of plain pairs, for it counts (Alicia, Beti) as different from (Beti, Alicia). The fix is simple: divide our count of ordered pairs by $2$. So the number of pairs of people is $$\frac{f(f-1)}{2}.$$

Now make your formula. To check for any mistakes, compare what your formula predicts with our explicit counts above.

-
I got the equation $\frac{4f(f-1)}{2}$ which simplifies to $2f(f-1)$ which is what @EnYu got. Is that correct? – Kot Nov 8 '12 at 5:37
Yes, it is correct. As I suggested, you can check it against the explicit calculations in the first part of my solution. – André Nicolas Nov 8 '12 at 5:48
If $f$ was $1$ then there would be $0$ kisses? Shouldn't there be $4$? – Kot Nov 8 '12 at 5:50
@StevenN I think the confusion here is that your $f$ and our $f$ is off by one. You seem to be referring to $f$ as the number of your friends while we refer to $f$ as the total number of friends (i.e. total number of people). – EuYu Nov 8 '12 at 5:56
If the number of friends (people) in the room is $1$, there will be no kisses: traditionally, French people do not kiss themselves. It is conceivable that "number of friends" is intended to refer to people other than oneself. If $x$ is the number of people other than yourself in the room, then the number of kisses is $2x(x+1)$. – André Nicolas Nov 8 '12 at 5:57

It is not quite related to the factorial but to the number of pairs you can form with the friends. If there are $N$ friends then how many unique pairs of friends are there? Each pair will exchange $4$ kisses so your total number of kisses is $4$ times the number of pairs.

Edit: Some elaboration.

Consider the choose function $\binom{n}{r}$. If we have $f$ friends and we need to find out the number of pairs, then that's equivalent to choosing $2$ out of the $f$ friends. Therefore the number of pairs is given by $\binom{f}{2}$. The binomial coefficients are normally given by factorials, but in this case it simplifies drastically. $$\binom{f}{2} = \frac{f!}{(f-2)!2!} = \frac{f(f-1)}{2}$$ The number of kisses is $4$ times this value, so the total number of kisses is given by $$k = 2f(f-1)$$

-
Would the formula be k=4f? Since a pair of friends will exchange 4 kisses? – Kot Nov 8 '12 at 5:09
Is $f$ the number of friends or the number of pairs? Do you know how to find the number of pairs? – EuYu Nov 8 '12 at 5:10
f would be the number of friends, and I do not know how to find the number of pairs. – Kot Nov 8 '12 at 5:12
Do you know about the choose function and binomial coefficients then? – EuYu Nov 8 '12 at 5:13
Is the choose function n Choose r (nCr)? – Kot Nov 8 '12 at 5:14