Magic Math Help

[OurSerratedDust]

Let us consider that I have a magic deck I am working on. This deck has no basic lands, and 20 different possible cards that could be included in the deck. Obviously, you can have up to 4 of each card.

How many different decklists can you make using these 20 to add up to 60 cards? I cannot for the life of me think of a way to calculate this. Thanks guys!

[LennonMarx]

The easiest way to think about this is instead of having 20 different card with up to 4 copies each, treat it as though you just have 80 unique cards. As such, the first card in the deck has 80 choices, the 2nd has 79, and so on. So that math is:

80 x 79 x 78 x ... x 22 x 21 which works out to....


29417320058814110230954525683465000000000000000000000000000000000000000000000000000000000000000000000 different possible combinations of cards. I have no idea what that number even is, aside from huge. Now, there is the issue here that some of those combinations will be the same deck just with different cards picked in different orders. I'm not sure how to work that out, but I'm sure its a smaller yet still really really large number.

[lordofthepit]

Never mind, incorrect. I'll think about it.

[clavio]

I got 3.18X10^10 which is (39 choose 20) - (20*1855967520). I'm only kind of sure.

Since you have 80 total cards and your deck is 60 figuring out the number of different 20 cards you're not using is the same as figuring out the 60 that you are. I found http://crab.rutgers.edu/~guyk/dmlec/lectures/lec05/l5.pdf. With 20 buckets and 20 different marbles, there should be 39 choose 20 possibilities.

Unfortunately this doesn't take into account the fact that you can only play 4 copies of each card. For this I worked out a bunch of smaller cases and found a pattern in Pascal's triangle. I'm sure there is a "real" way to figure it out but I couldn't figure it out so I'm giving up for now.

[Guy I Don't Know]

3,556,116,619,501

How is that useful, I don't know. Please don't playtest that many options....


EDIT: Should explain,

Can have 0-4 of a card and there are 20 cards. So 5^20 possibilities. Probability that their is 60 cards is .0372885854041

(5^20)*.0372885854041= 3,556,116,619,501

[clavio]

Probability that their is 60 cards is .0372885854041



How did you find this?

[Guy I Don't Know]

How did you find this?

Dice calculator :)

[lordofthepit]

I got 3.18X10^10 which is (39 choose 20) - (20*1855967520). I'm only kind of sure.

Since you have 80 total cards and your deck is 60 figuring out the number of different 20 cards you're not using is the same as figuring out the 60 that you are. I found http://crab.rutgers.edu/~guyk/dmlec/lectures/lec05/l5.pdf. With 20 buckets and 20 different marbles, there should be 39 choose 20 possibilities.

Unfortunately this doesn't take into account the fact that you can only play 4 copies of each card. For this I worked out a bunch of smaller cases and found a pattern in Pascal's triangle. I'm sure there is a "real" way to figure it out but I couldn't figure it out so I'm giving up for now.

How did you get the -(20 * blah) term?

I'm having trouble identifying the number of indistinguishable elements in your 60-card (or 20-card) deck. Also getting a Pascal's triangle of summed combinations. My friend (a math major) tells me he doesn't think there's a trivial way of calculating it.

Edit: at this point, I'm leaning towards this as my response:

http://i52.tinypic.com/az6tjn.jpg

Call me a quitter.

[Mostly_Harmless]

What you're looking for are compositions (http://en.wikipedia.org/wiki/Composition_%28number_theory%29) of 60 (basically ordered sums). To make things easier to write out, let's pretend you only have a 6 card deck, instead of 60. In addition, let's say you only have three different cards: brainstorm, force of will and mental misstep. The composition 4+1+1 would correspond to 4 brainstorms, 1 force of will and 1 mental misstep. Unfortunately, we don't want to count all of the compositions. For instance, 5+1 would be illegal because we would be playing 5 brainstorms. You also don't want 2+1+1+2, because that would use a fourth card. We need to find the total number of compositions of 6 with no more than 3 parts and no part greater than 4.

For your problem, we need the number of compositions of 60 with no more than 20 parts and no part greater than 4. The calculations are pretty unwieldy, but I found a handy app (http://www.btinternet.com/~se16/js/partitions.htm) that will do it for you. The answer is 12,904,241,029.

[OurSerratedDust]

Thanks for the responses, guys. I just finished a Goblin Charbelcher piloting simulation, and I was trying to find a systematic way to optimize the deck. I now know that I will definitely need to be more creative than just trying each of billions of combinations (by the way, I'm open to ideas if anyone has any.)

[Guy I Don't Know]

Reduce the possibilities by finding out what cards are definites. For example, Goblin Charbelcher is a four-of. At least 2/3 of the deck is already determined and the last 1/3 you can try all the combinations. If you know you want to play 4-ofs of 10 cards then you only have 364,146 possibilities left to choose from! That 's manageable :P

[lordofthepit]

What you're looking for are compositions (http://en.wikipedia.org/wiki/Composition_%28number_theory%29) of 60 (basically ordered sums). To make things easier to write out, let's pretend you only have a 6 card deck, instead of 60. In addition, let's say you only have three different cards: brainstorm, force of will and mental misstep. The composition 4+1+1 would correspond to 4 brainstorms, 1 force of will and 1 mental misstep. Unfortunately, we don't want to count all of the compositions. For instance, 5+1 would be illegal because we would be playing 5 brainstorms. You also don't want 2+1+1+2, because that would use a fourth card. We need to find the total number of compositions of 6 with no more than 3 parts and no part greater than 4.

For your problem, we need the number of compositions of 60 with no more than 20 parts and no part greater than 4. The calculations are pretty unwieldy, but I found a handy app (http://www.btinternet.com/~se16/js/partitions.htm) that will do it for you. The answer is 12,904,241,029.

Thank for this response. I didn't realize there was a term to describe this type of problem/sum.

Edit: Question for Mostly_Harmless. I see that we're computing the number of compositions of 60 (first setting), with maximum number of terms 20 (second setting), with each term no more than 4 (third setting). This yielded the same answer you got.

Shouldn't we get the same answer if we were computing the number of compositions of 20 with maximum terms 20, each no more than 4? Since choosing a 60 card deck from 20 distinct cards, each with between 0 and 4 copies, is equivalent to choosing a 20 card deck to exclude. I'm not getting the same answer on the calculator.

[Mostly_Harmless]

That's an excellent point. I cheated. The problem is that compositions don't count 0+4+2 and 4+2+0 separately. That means I undercounted by quite a bit. I'll think about it some more and see if I can fix the method.

Edit: Well, there might be a more elegant solution, but this should work:
Let's call c(N,k,r) the compositions of N with exactly k terms (notice that this is different from the previous method) and each term no more than r. So, c(60,16,4) is the compositions of 60 that use 16 different card names. Note that c(60,k,4)=0 if k<15, since you need at least 15 four-of's. For each k (15<=k<=20) we want to know how many combinations of card names we could choose. That's 20 choose k (I'm going to denote that by 20 C k). The answer we're looking for should be the sum from k=15 to 20 of (20 C k)*c(60,k,4). I get 35,561,166,195.

[Guy I Don't Know]

That's an excellent point. I cheated. The problem is that compositions don't count 0+4+2 and 4+2+0 separately. That means I undercounted by quite a bit. I'll think about it some more and see if I can fix the method.

Is there any problems with my calculations?

[lordofthepit]

That's an excellent point. I cheated. The problem is that compositions don't count 0+4+2 and 4+2+0 separately. That means I undercounted by quite a bit. I'll think about it some more and see if I can fix the method.

After discussing this with my friend, he pointed out the same thing (if I understand correctly). This is because it doesn't have enough "0" place holders, such that 4 + 1 should actually represent 20 compositions instead of just 2.

The easiest "hack" is to shift the problem to allow for {1..5} copies of each 20 different card, forming an 80 card deck instead (i.e., the same deck, except with 1 extra copy of each of the original 20 card). This is inputted as compositions of 80, exactly 20 terms, each no more than 5.

This is no longer symmetric the same way that C(N, n) = C(N, N-n). But if you think logically about "choosing a 20 card deck", as posed above, in this case, you are now choosing a 40 card deck since you're adding 1 extra copy of each card (i.e. compositions of 40, exactly 20 terms, each no more than 5).

Both methods yield a value of 35561166195, which is a nice sanity check. My friend is running a slow recursive program that he wrote to confirm this, but it might take a while. :laugh:

[lordofthepit]

Is there any problems with my calculations?

This is uncanny, but my 11-digit answer using your calculator matches the first 11 digits of your 13-digit answer exactly. I have verified that it is not a truncation error. I'm sure this is not just a coincidence. I'll think about your solution again, but I'm wondering if one of us made a number error (i.e. using a percentage instead of a decimal)?

Edit: The probability of rolling a 60 with 20 dice from 0..4 is .0372885854041%, not .0372885854041. So everything check out.

[Guy I Don't Know]

This is uncanny, but my 11-digit answer using your calculator matches the first 11 digits of your 13-digit answer exactly. I have verified that it is not a truncation error. I'm sure this is not just a coincidence. I'll think about your solution again, but I'm wondering if one of us made a number error (i.e. using a percentage instead of a decimal)?

Edit: The probability of rolling a 60 with 20 dice from 0..4 is .0372885854041%, not .0372885854041. So everything check out.

I used another calculator and it had the same numbers but over two places. First calculator it was unclear if it was % or decimal. So yea, you got the right answer.

[Mostly_Harmless]

The easiest "hack" is to shift the problem to allow for {1..5} copies of each 20 different card, forming an 80 card deck instead (i.e., the same deck, except with 1 extra copy of each of the original 20 card). This is inputted as compositions of 80, exactly 20 terms, each no more than 5.

Ooh, that's classy. I like it much better than my method (I was a little slow with my edit, so in case you didn't see it it's in the last post).

I also verified with my method that sum from k=15 to 20 of (20 C k)*c(60,k,4) = sum from k=5 to 20 of (20 C k)*c(20,k,4). Along with Guy I Don't Know's calculations, I'd say we can be pretty confident about the answer.