How many combinations of actions can be made with 3 buttons in Warcraft?

[Kontilera]

Hello!
I stumbled across a question in mathematics which left me confused.

Apparently there is a character in a computer game that has 10 different actions.
Which action he makes is determined by which combination of buttons that you press. You should press three buttons and gets to choose between W, Q, and P. The order of the buttons are irrelevant, i.e. WQP is identical to QWP, etc. Then also be repeated, i.e. you can press WWQ.

When I write down the combos, I find the 10 different ones.

But when I try to calculate the result, I get confused.

My first guess was to calculate 3^3 / 3!, but this doesn't even give me an integer!

Sorry for my english.
Please help.

/Kontilera
ps. This is not a homework, only friend to friend conversation that left me curious. ds.
pss. I realized the answer must be 5 nCr 3. But is there any way to get an intuition for why? dss.

 

[jedishrfu]

Aren't there some letter combinations that you are counting that aren't valid for the character?

As an example ABC is valid but DEF, EFG, FGH ... are not and the character only has 10 possible actions to begin with.

 

[WWGD]

Seems like a fit for inclusion-exclusion. Something like : Start with $3^3$ and then consider strings with 0,1 repeats? Or, isn't this also a possible problem of balls-in-boxes: You have three boxes, say 1,2,3 in which to put balls EDIT: Not quite convincing, will keep trying for a formula. EDIT2:

1) Strings with 0 repeats :1 , all permutations of WPQ
2) Strings with 1 repeat , 6: WWQ, QQP, etc. 3 choices for the repeats, 2 choices for the non-rep.
3) Strings with all repeats : 3 : WWW, PPP, QQQ
___________________________________________________
1+6+3=10.

Maybe not too elegant, but does the job.

 

[Kontilera]

Thanks!
Yeah, I am with you now.

The total number of possible setups are 3*3*3 = 27.

Then we are counting 5 extra one-of-each-button combinations since there are 3!.

We are counting 2 extra for every 2:1 combinations since there are 3 = 3 nCr 2 of them.
And there are 6 different kind of 2:1 combinations.

For the PPP QQQ and WWW we don't count any extra and there are 3 of them.

This yields:

27 - 5*1 - 6*2 - 3*0 = 10BUT!
Im sure there is a nice intuitiv interpretation of the '5 nCr 3' which yields the same result. :/

 

[WWGD]

Thanks!
Yeah, I am with you now.

The total number of possible setups are 3*3*3 = 27.

Then we are counting 5 extra one-of-each-button combinations since there are 3!.

We are counting 2 extra for every 2:1 combinations since there are 3 = 3 nCr 2 of them.
And there are 6 different kind of 2:1 combinations.

For the PPP QQQ and WWW we don't count any extra and there are 3 of them.

This yields:

27 - 5*1 - 6*2 - 3*0 = 10

But it may just be a coincidence that 5P3=10, and not necessarily from an argument
BUT!
Im sure there is a nice intuitiv interpretation of the '5 nCr 3' which yields the same result. :/

 

[pbuk]

BUT!
Im sure there is a nice intuitiv interpretation of the '5 nCr 3' which yields the same result. :/

No it's a coincidence; there is not 5 of anything involved here.

 

[Kontilera]

It's not a coincidence... There is a pattern.
The general formula for these kind of problems seems to be (n+k-1) nCr k, which must come from somewhere..
In our case we got 3 buttons (n= 3) and we want to choose 3 kinds (k=3). This gives: (3+3-1) nCr 3 = 5 nCr 3.

 

[pbuk]

Yes sorry, coincidence is not really the right word. The general solution to these type of problems is indeed _(n+k-1)C_k where n is the number of kinds of things and k is the number chosen. This is known as a "multichoose" problem, and for an intuitive explanation of the link to the binomial coefficient look up "stars and bars" (and "bars and stars" to cover that permutation).

 

[Kontilera]

I solved it myself. :)

Lets say one circle 'o' represents one pressed button.
Then since the order is irrelevant we can sort all the P's to the left, all the Q's in the middle and all the W's to the right.
The transition between to letters are represented by a line.

Thus:
oo|o|
Represents PPQ, since we have two circles to the left, one in the middle and zero to the right.

ooo||
is PPP.

o|o|o
is PQW
etc.

All possible combinations can be obtained by placing our five symbols (3 o's, and 2 lines) in a specific order where the order within the circles doesn't matter and the order within the lines doesn't matter.

Thus we need to place 3 circles in 3 out of 5 places (i.e. 3 nCr 5), or equivalently two lines in tw out of five places (2 nCr 5).

In general we need to have k-1 lines. Which yields n+k-1 symbols. And we need to select k positions.

Which gives (n+k-1) nCr k.

 

[pbuk]

Yes, this is the "stars and bars" analysis - or in your case "circles and lines".