# $k$ cards summing to $n$

This was a problem posted about probability involving Fibonacci numbers that I thought was really interesting so I decided to repost a portion of it regarding a general closed formula. The problem really has nothing to do with fibonacci numbers, just probabilities involving those particular numbers

Suppose I have a deck of cards. Is there a closed formula in order to find the probability of $k$ cards summing up to a number $n$?

This problem is intriguing to me, mainly because of the closed set of cards. There are only $52$ of them, with $13$ different numbers present. Thus there are many different $k$-tuple combinations not allowed since our limitation with the cards. For example, we can only have possibility if $k=8$ and $n=13$, since $(1,1,1,1,2,2,2,3)$ is the only way to obtain a string of $8$ cards that sum to $13$ (I'm not including all $\frac{8!}{4!\cdot3!}$ permutations of the string) since we can't have such strings as $(1,1,1,1,1,1,1,6)$.

I did a bunch of analysis with $n=13$ and can't find any discernable patterns in the numbers that would make me believe there is a form at least for $n=13$, much less an arbitrary n. For example, there is one $1$-tuple {$(K)$}, six $2$-tuples {$(1,Q),(2,J),(3,10),(4,9),(5,8),(6,7)$}, fourteen $3$-tuples, eighteen $4$ and $5$-tuples, ten $6$-tuples, five $7$-tuples, and one $8$-tuple. I was not using ordered pairs, simply because once $k$ gets to $3$ and higher, all possible k-tuples become very large very fast, and have instead calculated using factorials. I also know that the lowest quantity for $n$ is $1$ and the highest is $364$. Does anyone have any idea how to begin without rigorously computing all possible quantities?

-

Let $S$ be the number of suits, $R$ be the maximum rank of the suits (all equal), therefore the number of cards in the deck are $SR$, and $n$ be the number you are seeking.

So you are looking for the solutions $M_i$ to:

$$n=\sum_{r=1}^Rs_rr\text{ where }s_r\in0,\dots,S$$

Now for each of these, the number of combinations is:

$$C(M_i)=\prod_{r=1}^{R}{{S}\choose{s_r}}$$

Nontrivial (i.e. $\ne 0$) only exist for $0\le n\le \sum_{r=1}^{R}Sr$ (note the lower bound is 0 not $S$ as stated in the question - 0 is achieved by drawing no cards and this can be done 1 way).

I suggest that you then attack this from both ends i.e. counting up from $n=0$ and down from $n= \sum_{r=1}^{R}Sr$ and see what you get.

-
in your combination formula for $C(M_i)$, 1). What does the index $i$ represent and 2). Should the lower term of the summation combination be $r$, not $s$? I think I see where you are going, but i need time to do some work. – Eleven-Eleven Jul 7 '13 at 12:42
$M_i$ are each of the solutions to the previous equation e.g. for n=2, the selections 1,1 and 2 are $M_i$'s with $s_1=2,s_2=0$ and $s_1=0,s_2=1$ respectively. I have fixed the second equation – Dale M Jul 8 '13 at 1:17