Combinations: How many handshakes? I need help with the following question which I cannot seem to solve:
17 students are sitting in a circle. Each person shakes hands with everyone but his/her neighbours. How many handshakes have been exchanged?
My approach: no. of ways $ = 1 + 2 + 3 + ... + 14 = 7(15) = 105 $.
Apparently my answer is wrong (correct ans is 119). But I can't seem to understand why. Could someone please explain?
 A: Here's another way to think about it.
If everyone shook hands with everyone you'd have $\frac {17*16}2 = 136$ handshakes (divide by 2 because the above is double counting A shaking hands with B and so forth).
However, there are $\frac {17*2}2 = 17$ handshakes that aren't happening because neighbors aren't shaking hands (2 neighbors for each of the 17 people, again divided by 2 to remove duplicates).
So $136-17 = 119$
Pew's response is a little more direct, but finding the number by calculating the total possibilities minus the "not allowed" interactions is sometimes a little more intuitive for some people.
A: You can think of this in graph theory as the following:

$G$ has $17$ vertices with degree $14$, since there are no loops(people self handshaking), and no vertices are adjacent to the vertices beside them. So total degree is $17\times 14$.
We know that degree is equal to $2\times\text{number of edges}$ and hence there are $\frac{17\times 14}{2}=119$ edges in total, where edges represent handshakes.
A: Each of 17 people shakes hands with 14 people (all except themselves and their 2 neighbors), so there are
$$\frac{17\times 14}{2} = 119$$
handshakes (dividing by 2 to account for symmetry, as you would otherwise count "$A$ shaking hands with $B$" and "$B$ shaking hands with $A$" as distinct events).
A: As is typical for problems with big numbers, you should always resort to a smaller number if you can't solve the full problem.
Here, 17 people at the table is a bit hard to imagine immediately.
Let's start with 3 people at the table.
How many handshakes now?
There are zero.
What about 4 people:
A B

C D

A can't shake with B or C, B can't with A or D, D can't with B or C, C can't with A or D--only A & D and B & C can shake.
So 2 shakes:
A B
 X
C D

5 people is when it gets interesting, and when you should be able to see the pattern:
      B

  A       C

    D   E

Everyone has two people they can't shake with, leaving two shakes per person--but we overcount by just multiplying 5 & 3, so we divide by two.
This is easiest to see by trying to draw the graph mentioned by @Commitingtoachalleng -- draw a line between any people who can shake hands:
        B
       / \
  A-----------C   (also C-D & A-E--a 5-point star)
     /     \
    D       E

So we hypothesize the answer is $\frac{n(n-3)}{2}$. Note that this formula holds for $n=3$ and $n=4$ as well, as we'd hope!
One final way to see this is to look again at the graphs--
you might notice that they're always complete graphs (every vertex connected to every other vertex) with the outer edges removed.
Since there are $\frac{n(n-1)}{2}$ edges in a complete graph on $n$ vertices (which you can confirm yourself by a similar process), and $n$ outer edges,
there must be $\frac{n(n-1)}{2} - n = \frac{n^2-n-2n}{2} = \frac{n(n-3)}{2}$ handshakes.
However you cut it, there are $\frac {17 \cdot 14} 2 = 119$ total handshakes.
A: I will explain for 6, same logic applies for all the numbers. 
first, 
if 6 persons shakes will all in the party, then number of shakes will be: 
A  B  C  D  E  F
A can shake with only rest of 5 persons(B,C,D,E,F) i.e, right side ppl. = 5
B can shake with only his right sides(C,D,E,F) ppl(not with A bcos,A already shook with B just now. so no repeat) = 4 
C can shake with only his right sides(D,E,F) ppl(not with A&B bcos,A&B already shook with C just now. so no repeat) = 3
D can shake with only his right sides(E,F) ppl(not with left side ppl  bcos, they already shook with D just now. so no repeat) = 2 
E can shake with only his right sides(F) ppl(not with left side ppl  bcos, they already shook with E just now. so no repeat) = 1
as all of the persons shook hand with F, He dont shake with any one now. 
So total possible shakes for 6 persons are = 5+4+3+2+1 => 15
now in questions it is given that, No one shakes hand with neighbors. 
Imagine ppls sitting around table
        A   B
      F       C
        E   D   

Please treat above image as 6 Ppl around circle :
So now, 
Invalid Shakes:
A cannot shake with B,F . I am representing it as below :
  A  -no- B & F    => 2 invalid shakes.
  B  -no- C only. Bcos  B -no- A is covered as part of first case.
                   =>  1 invalid shake
  C  -no- D only.  =>  1 invalid shake
  D  -no- E only.  =>  1 invalid shake
  E  -no- F only.  =>  1 invalid shake
  F dont shake with A is already covered as part of first invalid shakes.    
so total invalid shakes are 2+1+1+1+1 = 6   
so for 6 ppl:  out of  total 15 , 6 are invalid. So 15-6 = 9  
on the same line :   
for 17 ppl:  out of  total (16+15+...+1)=136 , 17 are invalid. So 136-17 = 119
shortcut :   For N ppl, Total shakes are  (N-1)(first term + last term)/2  Arithmetic progression sum. out of which Invalids are N.
So valid shakes =>  (Total - N)
