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.

  • 1
    $\begingroup$ Your first attempt ignores that we could flip the staff upside-down and it should count as "the same" staff. Your second attempt and last attempt should have both been correct, however you made a mistake when counting. Notice that $\{AB,AC,\dots, AH\}$ have only seven possibilities, not eight. $H$ is the eighth letter of the alphabet and this batch started counting from $AB$, not $AA$. That would make the total instead $9+7+6+5+\dots+1=37$, the same answer as the second method. $\endgroup$ – JMoravitz May 25 '18 at 20:34
  • $\begingroup$ @JMoravitz Thanks for the proofreading. I was expecting some answer delving deep into probability theory. Instead it was a simple counting error. I need to be more careful with letters and ...s. $\endgroup$ – DrZ214 May 25 '18 at 20:41

One way to do this is to break it down into 3 cases. The staff can have: 0 staffheads, 1 staffhead, or 2 staffheads. In each case you have 8 options but are only choosing 0, 1, or 2. So your total would be:

(8 choose 0) + (8 choose 1) + (8 choose 2) = 1 + 8 + 28 = 37

  • $\begingroup$ Yep, this is a much better way to think of it. Thanks. $\endgroup$ – DrZ214 May 25 '18 at 20:42

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.