Can you figure out the number of combinations?
Im trying to create a new player card game and Im having trouble figuring it out... Can you tel me how many possible 4 card combinations of 16 there are using a deck of playing cards? The values of the card are the same as blackjack however Aces are only worth 1 point. And combinations dont count twice just because they are in different order so AA77 is the same as A77A and is only one combination. I actually need to figure out every possible combinations of values 4 through 40 but lets start here and see if I can even get an answer. Also an algorithm that I could use to figure out all the other values would solve everything (teach a man to fish) :) Thanks!
- husoskiLv 74 months agoFavorite Answer
One way to keep order from counting is to only count sequences that are sorted. That can help in developing an algorithm to find counts for each possible sum.
Define N(n, t, s) to be the number of sorted sequences of n cards adding up to a total of exactly t, each card no smaller than s and no greater than 10. Your answer is then N(4, 16, 1).
Not much help there, huh? But you can define N(n, t, s) in terms of smaller values of n, t and/or larger values of s, and that gives you a (recursive) algorithm. Because the values eventually have to "bottom out", you can guarantee that the algorithm terminates. (In principle, at least. :^)
The cases where n=1 are easy to state. There's one way if t is equal to some allowable card (at least s, but no greater than 10), and no way if t is out of that range:
N(1, t, s) = 1 . . . if s ≤ t ≤ 10
. . . . . . . = 0 . . . otherwise.
When n > 1 there are a few cases to consider:
N(n, t, s) = 0 whenever ns > t, since ns is the smallest total that you can make with n cards no less than s.
Otherwise the sequences can be split into two categories, those with s in the sequence and those without.
The number of sequences that don't include s is clearly N(n, t, s+1).
The number of sequences that do include at least one s is N(n-1, t-s, s). That counts the number of ways to make the rest of the sequence add up, using one card fewer and still using cards no less than s.
You can combine those. For any n>0 and non-negative t, s:
N(n, t, s) = 0 . . . . if ns > t
. . . . . . . = N(n, t, s+1) + N(n-1, t-s, s) . . . otherwise
Write that as a program, expand it on paper, use a spreadsheet. Carefully done, you'll find that N(4, 16, 1) is 30.