Playing with the pack of cards on my desk, something just happened that I didn't expect!
Look at the deck with the cards face-up. Here's a rule: look at the top card. Draw that many cards from the deck. Repeat until the deck is empty.
I did this, and dealt out exactly the right number of cards (at the end, I had 3 cards left and the top card was a 3).
What's the probability of this happening?
So I've been thinking about the problem almost like a knapsack problem. Let \(\vec{c}=[1,2,3,4,5,6,7,8,9,10,11,12,13]^T\), which is the vector of card values, and \(\vec{a}=[a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9,a_{10},a_{11},a_{12},a_{13}]^T\) where \(\forall_{i \in \{1,\dots,13\}} a_i \in \{0,\dots,4\}\), which are the number of individual cards (e.g., 4 aces, 1 twos, etc.). Then, solutions to the puzzle could be written as the following:
\(\min (\vec{c}^T\vec{a}-52)^2\)
s.t.
\(\vec{a}^T\textbf{1} \leq 52\)
Thus, any solution found by this minimization problem would have \(\vec{c}^T\vec{a}=52\). Then, given a solution, the number of combinations for the solution is as follows:
\((\vec{a}^T\textbf{1})! \times (52-\vec{a}^T\textbf{1})! \times \prod_{i \in \{1,\dots,13\}}(4 nCr a_i)\)
The total number of combinations is the sum of all of these values.
Of course, solving the minimization problem is difficult, but I would assume just like the linear knapsack problem, dynamic programming, as @narain mentioned before, would do the trick. Please let me know if I have made any mistakes.
Alright, so I went over my code with a colleague, and he found an error in my code (forgot to round my floating number before converting to integer). My original number of solutions (41,846) still holds, but my probability and combination calculations were off. My current probability now matches the simulation number of approximately 14.2%. I have uploaded my code and solution on GitHub here:
https://github.com/dataNerd23/52_card_sum_problem
The following is an updated screenshot of my solution: