I was thinking about the match-ups in Starcraft and visualizing them as a Triangle where all the lines connecting the corners represent the possible match-ups, plus adding the number of corners to represent the mirror matches. Then I thought about how a square and a pentagon would also show the number of different match-ups if you had 4 or 5 races respectively.

Then I noticed that the number of match-ups increases in the sequence 1,3, 6, 10, 15 etc which is the same way the number of balls in a pool table increase with each row added. It's obviously 1 + 2 + 3 + 4 + 5 etc. See picture below. [image loading]

My question is, what has the number of permutations got to do with how the balls make up the triangle? Explain this to me with maths please.

infinitestory

United States4053 Posts

April 17 2012 02:08 GMT

say there are n factions
pick 1st faction: n ways
pick a different faction: n-1 ways
each matchup will be counted twice, hence n(n-1)/2 for all non-mirrors, which is also the triangle numbers formula

deathly rat

United Kingdom911 Posts

April 17 2012 02:34 GMT

The number in the triangles includes the mirror matches, so it would be n(n-1)/2 + n. You got the right formula, but I don't understand it, or what this has to do with the triangles.

Myrddraal

Australia937 Posts

April 17 2012 03:10 GMT

Not really explaining it with maths, but this is how it makes sense to me. Each row you add, you are adding the same amount as was in the previous row + 1, meaning you are accounting for each non mirror +1 for the mirror.

0
0 + 1 = 1
1 + 1 = 2
2 + 1 = 3
3 + 1 = 4
4 + 1 = 5

Anacletus

United States733 Posts

April 17 2012 03:39 GMT

The above equations ar ecorrect, and I'd like to expand upon them. You should notice that the area increases exponentially as you add items. You should also notice that any side is equal to the number of items, and going from that chosen side across is one less than the previous. This is because as mentioned in previous posts you don't repeat a permutation if it has already been done but in the opposite order; example: (using your example of race match ups) ZvT =TvZ.

Basically compare each row as one race vs the others and move up from there removing duplicates.

PvP
ZvZ + ZvP
TvZ + TvT + TvP

Does that help explain this concept?

Sorry if my post is sloppy - it was painstakingly made via android phone - feel free to pm me if you had any other questions

Happy posting!

EtherealDeath

United States8366 Posts

April 17 2012 03:48 GMT

The summation simply matches that for the triangular numbers is all, due to non-repetition of matchups essentially turning a combinatorics problem into a sum of successive integers starting from 1 (thus the triangular numbers appear).

Nehsb

United States380 Posts

April 17 2012 04:24 GMT

Here's a combinatorial bijection if you're familiar with bijections: (taken from http://mathoverflow.net/questions/8846/proofs-without-words) If you're not, bijections work to show that two sets A, B have equal size by pairing elements from A with elements in B; If you can pair all the elements in A with elements in B and have none left over, then the sets have equal size.

[image loading]

For every yellow ball in the picture, it corresponds to a choice of "matchup" between two of the purple balls at the bottom. So the number of matchups will equal the number of yellow balls.

Heres another way that might or might not be more clear for you (It's essentially the same thing, but the different presentation might help some)

A
B x
C x x
D x x x
o A B C D

In this, if you want to look at say the matchup between B and C, then there's exactly one x in the chart that has row/column B and C. Same for any other matchup, so the number of matchups = number of x's.

(Sorry, I'm really tired so I might be explaining things horribly.)

xxpack09

United States2160 Posts

April 17 2012 05:21 GMT

It's part of a larger pattern that can be seen in Pascal's triangle.

[image loading]

Look at the diagonals. One goes 1,1,1,1,1... the next 1,2,3,4,5... the next 1,3,6,10,15... the next 1,4,10,20,35.... etc.

The nth element in the mth diagonal represents the number of combinations in a game with n races and (m-1) simultaneous players. So for starcraft, we have 2 players (3rd diagonal) and 3 races (3rd element) which = 6.

Rannasha

Netherlands2398 Posts

April 17 2012 08:14 GMT

On April 17 2012 12:39 Anacletus wrote:
The above equations ar ecorrect, and I'd like to expand upon them. You should notice that the area increases exponentially as you add items

It increases quadratically, which is far from exponentially.

allluckysevens7777

United States53 Posts

April 17 2012 11:27 GMT

#10

If you want arithmetical reasoning, you're doing (n choose 2) + n to find the number of matchups (n choose 2 for non-mirror, plus n mirrors). n choose r is n!/(r!(n-r)!), where ! denotes the usual factorial. n choose 2 happens to work out to n(n-1)/2. Adding n, you have (n(n-1)+2n)/2 = n(n+1)/2, which can easily be shown by induction (or informally by gauss' pairing argument) to be the sum of the numbers from 1 to n inclusive, a triangle number.

deathly rat

United Kingdom911 Posts

April 17 2012 11:31 GMT

#11

Nice, thankyou maths enthusiasts. This is all very interesting

Anacletus

United States733 Posts

April 17 2012 11:47 GMT

#12

On April 17 2012 17:14 Rannasha wrote:

Show nested quote +

It increases quadratically, which is far from exponentially.

Yeah my mistake, I was pretty tired when posting and was doing my best to exemplify the situation in terms that would be familiar to him thus the given parameters and unit names and just overlooked some technical vocabulary. My bad!

deathly rat

United Kingdom911 Posts

April 17 2012 12:41 GMT

#13

On April 17 2012 11:08 infinitestory wrote:
say there are n factions
pick 1st faction: n ways
pick a different faction: n-1 ways
each matchup will be counted twice, hence n(n-1)/2 for all non-mirrors, which is also the triangle numbers formula

ok, I was trying to understand why this formula works, and I made this picture which helped me visualise it.

[image loading]

Glacierz

United States1240 Posts

April 17 2012 16:00 GMT

#14

Proof by induction:
Base case: 1 race, 1 matchup (mirror)
Assume there are n races, adding 1 more race creates n+1 number of additional matchups, therefore forming a triangle.

Pretty simple math, no need for complex diagrams

If you are looking for formula:
for n races, the number of matchups are:
(1+n)*n/2

Please or register to reply.

Live Events Refresh