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:


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.

  • $\begingroup$ 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. $\endgroup$ – Eleven-Eleven Jul 7 '13 at 12:42
  • $\begingroup$ $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 $\endgroup$ – Dale M Jul 8 '13 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.