Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinations with Irregular Repetition

  1. Jul 20, 2013 #1
    Hey folks, I believe this is the correct thread for this topic. I was debating between general mathematics and statistics. I believe it falls here.

    So, I play the card game Magic: The Gathering, and one of the core tenants of the game is building a deck from a large variety of cards. The deck is then randomized (shuffled) and the actual game involves doing your best with the cards you've drawn, as well as knowing what you are likely to draw (reminiscent of poker.) Interestingly, in building a deck, knowledge of statistics is very useful as some cards you may want to see more than others.

    One thing I've always been curious of, though, is how many possible decks can be created. It would seem like a simple combination problem, or even Combination with Repetition, except for a problem. Most cards you may have no more than four of in your deck, but there are five cards that you may have any number of in your deck.


    So, here's the question:

    A deck consists of 60 cards.
    There are 1729 cards of which you may have 0 to 4 copies each in your deck.
    There are 5 cards of which you may have any number of copies in your deck.

    How many unique decks can be built?


    More than the answer (though I'd be excited to see it,) I'd like to know how to frame an equation that would handle a situation like this. Any thoughts are welcome!

    Last edited: Jul 20, 2013
  2. jcsd
  3. Jul 20, 2013 #2


    User Avatar
    2017 Award

    Staff: Mentor

    If the problem is too complex to find a direct formula, split it in sub-problems:

    Assume N of those 60 cards are used which cannot appear more than 4 times, and M different cards of that type are used (##M\geq \frac{N}{4}##).
    This gives well-known problems for the number of combinations for those N cards and the 60-N other cards. I am too lazy to look up the formulas.
    Afterwards, you can sum over all N and M.
  4. Jul 20, 2013 #3
    Mfb, thanks for your reply!

    I actually was not aware there were formulas for combination with limited repetition like this. I had searched around online briefly but wasn't able to find anything that would quite work, even as a partial solution. Are there some particular keywords I could search under to find them?
  5. Aug 23, 2013 #4
    One way is using generating functions, so the solution is the coefficient of x^60 in (1+x+x^2+x^3+x^4)^1729/(1-x)^5
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook