So the question is:
"Find a recurrence relation for the number of ways to pick $n$ objects from $k$ types with at most 3 of any one type"
I think I figured out what it would be excluding the last restriction "at most 3 of any type," but I can't figure that part out.
Right now this is what I have (with the thought process):
Assume $a(k,n)$ is the number You can pick $n$ objects from types 1-k excluding one of the types. That would be $k \cdot a(k-1,n)$
If we have at least one from every type then we get:
$a(k, n) = k \cdot a(k-1, n) + a(k, n-k)$
I'm confused how I adjust this so that it has at most 3 of any one type.
Thank you!
We need to find the number of solutions $a(k, n)$ to
$x_1 + x_2 + x_3 + \cdots + x_k = n\tag{1}$
where $0 \le x_i \le 3$ denotes the count of objects of type $i$.
Imagine that you have all the solutions in front of you, and you proceed to sort them according to the value of $x_1$. There will be $4$ distinct groups of the form
$\begin{array}{}\color{blue}{0} + x_2 + x_3 + \cdots + x_k = n &\\\color{blue}{1} + x_2 + x_3 + \cdots + x_k = n\\\color{blue}{2} + x_2 + x_3 + \cdots + x_k = n\\\color{blue}{3} + x_2 + x_3 + \cdots + x_k = n\end{array} \iff \begin{array}{}x_2 + x_3 + \cdots + x_k = n &\\x_2 + x_3 + \cdots + x_k = n - \color{blue}{1} \\x_2 + x_3 + \cdots + x_k = n - \color{blue}{2}\\x_2 + x_3 + \cdots + x_k = n - \color{blue}{3}\end{array}\tag{2}$
This gives us the required recurrence relation
$a(k, n) = a(k-1, n) + a(k-1, n-\color{blue}{1}) + a(k-1, n-\color{blue}{2}) + a(k-1, n-\color{blue}{3})\tag{3}$
where $a(0, 0) = 1$ and $a(k, n) = 0 \text{ if }n < 0 \text{ or } k<0$
This program prints out the first few terms.