Let's say you have a staff and 8 staffheads. You can only put 1 staffhead on each end. But you can also put no staffhead on 1 or both ends. Every staffhead is unique.
How many possible configurations are there? Note that order is not important here. You can just flip the staff 180 degrees.
I tried to solve this in 3 different ways and got 3 different answers, so now I'm really confused.
First I thought it was just 9*8 = 72, because you can choose 9 things for the first end, and only 8 are left to choose from for the second end. But then I realized you can reuse the "nothing" option, so it should be 73.
Then I remembered there is a nCr function. I googled "9 choose 2" and it said 36. This makes me think my first way of doing it included order, which is not what I want. But again, since you can reuse the "nothing" option, the answer would actually be 37.
Then I finally spelled things out using N and A to H.
NN, NA, NB, NC, ... , NH = 9
AB, AC, ... , AH = 8
BC, BD, ... , = 7
... = 6+5+4+3+2 = 20
GH = 1
I summed them all up and got 45.
So now I'm pretty confused. Which one is correct and why? Or are all of them incorrect?
Note: I put tags for combination and permutation because I'm not 100% sure which one really applies to this question.