3
$\begingroup$

Consider $n$ people at a party, each of them shakes hand to exactly $k\leq n-1$ different persons. Is there a generalized formula giving the number of possible handshakes configurations?

This is a generalization of a problem featuring 8 people shaking hands with exactly two times (with of course different persons), in this case the answer should be (according to the text) 3507 which is far from obvious to me since I thought, in this case, that one possible list of configurations should be given arranging the 8 persons at the verteces of an heptagon so that each couple of consecutive sides stands for the double handshake, suggesting that the other possible configurations might come out interchanging the vertices which is 7! (analogous to the problem concerning the number of ways in which 8 people can sit at a circular table), but 7!=5040 so that I'm baldly miscalculating... Any hint?

$\endgroup$
2
$\begingroup$

For the $(n,k)$ problem:

What you are looking for are the $k$-regular graphs of $n$ nodes, with node labels, not necessarily connected.

However I couldn't find much for this labeled case. The best I could find (after a few minutes of googling) were the top answer at this MO question and also this other MO question.

The unlabeled case seems to have more literature: A good starting reference might be this wolfram link and this OEIS link. The latter lists $\sum_k f(n,k)$ but cross-references to many different OEIS sequences for fixed $k$.

For the $(8,2)$ problem:

As others have pointed out this is equivalent to partitioning into cycles of length $\ge 3$. It might(?) be easier conceptually if we partition first, then form cycles.

A set of $k$ people can clearly form $k! / 2k$ cycles. The denominator of $k$ accounts for the different start points, and the denominator of $2$ accounts for reflection.

  • An $8$-cycle: no. of ways $= 8! / 16 = 2520$.

  • An unordered pair of $4$-cycles: First of all, no. of such partitions $= {8 \choose 4} / 2 = 35$, with the denominator of $2$ accounting for the fact choosing either of the $4$-subset results in the same partition. After partitioning, each $4$-subset gives $4!/8 = 3$ cycles, so total no. of ways $= 35 \times 3 \times 3 = 315.$

  • A $3$-cycle plus a $5$-cycle: no. of such partitions $= {8\choose 3} = 56$. The $3$-subset gives $3!/6 = 1$ cycle, and the $5$-subset gives $5!/10 = 12$ cycles. Total no. of ways $= 56 \times 1 \times 12 = 672$.

Add them up: $2520 + 315 + 672 = 3507$.

$\endgroup$
2
$\begingroup$

This is based on the answer by gandalf61, who got the general idea right but has (at the moment) errors in the details. I'll repeat the steps they made, in case the answer is deleted or heavily modified.

From gandalf61

Link each person to the two other people that they shake hands with. Then each of the 8 people is part of a cycle of at least 3 people. So either there is one 8-cycle, or two 4-cycles, or a 3 cycle and a 5 cycle.

The number of $k$-cycles (or circles of length $k$) ($k \ge 3$) from $n$ people is

$$\frac{n(n-1)(n-2)\ldots(n-k+1)}{2k}$$

Thats because you can choose one of $n$ people for the 'first' person, then one of $n-1$ people for the second person, a.s.o until you choose the $k$-th person from the remaining $n-k+1$ people, after that the cycle closes with the first person. But the resulting formula $n(n-1)(n-2)\ldots(n-k+1)$ this yields is heavily overcounting the cycles.

One effect is that cycles don't have a 'first' person, they are cycles! So if you choose person 1 first, person 2 second and person 3 last in a 3-cycle, this is the same as choosing person 2 first, person 3 second and person 1 last, and the same for person 3, then person 1 and finally person 2. Thats why we have to divide $n(n-1)(n-2)\ldots(n-k+1)$ by $k$, the number of possible ways to choose the 'first' person from the $k$ members of the cycle.

The additonal factor $2$ we have to divide by comes from the fact that the cycles also don't have a natural 'direction', the cycle $(123)$ is the same configuration as $(132)$, which is the same cycle formed in the reverse direction.

Now we can calculate the number of cycles needed:

The number of $8$-cycles among those 8 people is $\frac{8!}{2\times 8}=\frac{7!}2=2520$.

The number of $4$-cycles among those 8 people is $\frac{8\times7\times6\times5}{2\times4}=7\times6\times5=210$.

If we have found one $4$-cycle, we need to form a second $4$-cycle from the remaining 4 numbers, there are $\frac{4!}{2\times4}=3$ possibilities, as per the initial formula. Since we are counting pairs of $4$-cycles, we have to account for the fact that each pair of cycles is counted twice: (1234)(5678) is counted both when (1234) is in the first $210$ cycles and (5678) in the second list of 3, and when (5678) is in the first $210$ cycles and (1234) in the second list of 3.

So the number of unordered pairs of $4$-cycles is $\frac{210\times3}2=315.$

Finally we need to find the number of $5$-cycles and associated $3$-cycles. The first number is $\frac{8\times7\times6\times5\times4}{2\times5}=8\times7\times6\times2=672$. For each such $5$-cycle, the number of ways to get a $3$-cycle from the remaining 3 persons is $\frac{3!}{2\times3}=1$.

So we get $672$ ways that the links can form a $5$-cycle and a $3$-cycle.

Adding up the number shown in the fat sentences, we get that there are $$2520+315+672=3507$$ ways to get have 8 people do handshakes with each other if each person shakes hands with exactly 2 different people.

$\endgroup$
0
$\begingroup$

Link each person to the two other people that they shake hands with. Then each of the $8$ people is part of a cycle of at least $3$ people. So either there is one $8$-cycle, or two $4$-cycles, or a $3$ cycle and a $5$ cycle.

In your count of $7!=5040$, every $8$-cycle is counted twice (because $(12345678)$ is also counted separately as $(18765432)$ etc.). So the actual number of $8$-cycles is $5040/2 = 2520$.

There are $(7 \times 6 \times 5) / 2 = 105$ different $4$-cycles, and for each of these the remaining $4$ people can be arranged in $3$ different $4$-cycles (either $(ABCD)$ or $(ACBD)$ or $(ACDB)$). So this adds a further $105 \times 3 = 345$ configurations.

There are $(7 \times 6 \times 5 \times 4) / 2 = 420$ different $5$-cycles and a single $3$-cycle for each one.

There are $(7 \times 6) / 2 = 21$ different $3$-cycles and $(4 \times 3 \times 2)/2=12$ different $5$-cycles for each one.

So the total number of configurations is $2520 + 105 \times 3 + 420 + 21 \times 12 = 3507$.

I suspect your figure of $3507$ is a typo.

For the general case, see OEIS sequence A001205.

$\endgroup$
  • $\begingroup$ Great! Thanks a lot!! $\endgroup$ – PITTALUGA May 1 at 11:04
  • $\begingroup$ Please note that the mentioned sequence actually contains $3507$ and not $3570$. One error is there are only $105$ pairs of 4-cycles, as each cycle is counted twice in your method, once as the 'original' and again as the one formed by the 'remaining 4 people'. In addition, for each 5-cycle, there is only possible 3-cycle, not 2 as you implied. So you overcounted by $420+105=435$, which leads to 3135, which is still wrong and I don't yet know why. $\endgroup$ – Ingix May 1 at 11:04
  • $\begingroup$ Correct, I get it. Thanks you too! $\endgroup$ – PITTALUGA May 1 at 11:06
  • $\begingroup$ @Ingix (a) $(1234)(5678)$ is a different configuration from $(1234)(5768)$; (b) $(123)(45678)$ is a different configuration from $(12345)(678)$. OEIS agrees with $3570$, so $3507$ is almost certainly a typo.. $\endgroup$ – gandalf61 May 1 at 11:27
  • 2
    $\begingroup$ I'm treating the cycles the same as circles in the graph-theoretical sense, see my below answer. The fact that we get different formulas for their count seems to indicate that they mean something different to you and me. For example, you count 5-cycles first and find there is one 3-cycle for it. Then you count 3-cycles and corresponding 5-cycles. Why are you adding those numbers up? A given configuration in that case contains a circle of 5 people shaking hands and a circle of 3 people shaking hands. You can count either way, but not add up both ways. I still don't understand your solution. $\endgroup$ – Ingix May 1 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.