Find a recurrence relation for $a_{n,k}$ , the number of ways to order n doughnuts from k different types of doughnuts if

Question

Find a recurrence relation for $a_{n,k}$ , the number of ways to order n doughnuts from k different types of doughnuts if two or four or six doughnuts must be chosen of each type.

I need help understanding the answer to this.

So I know the answer to this is

$a_{n,k}=a_{n-2,k-1} + a_{n-4,k-1}+a_{n-6,k-1}$

so I know that $a_{n-2,k-1}$ means you start by picking $2$ donuts of one type, then you pick the remaining $n-2$ donuts from the other $k-1$ types

$a_{n-4,k-1}$ means you start by picking $4$ donuts of one type, then you pick the remaining $n-4$ donuts from the other $k-1$ types

$a_{n-6,k-1}$ means you start by picking $6$ donuts of one type, then you pick the remaining $n-6$ donuts from the other $k-1$ types

But how does this satisfy the constraint that two or four or six doughnuts must be chosen of each type? That's what I'm confused by. Can't you just pick any amount of each type of donut from the other $k-1$ types, not just two or four or six.

If someone can explain this to me, I would really appreciate it.

Answer 1

The definition of $a_{n,k}$ requires 2, 4, or 6 donuts of each of the $k$ types. The recurrence relation is just splitting up the possibilities according to the number of donuts of type $k$. Once you have decided whether that is 2, 4, or 6, you have a smaller problem with fewer donuts and only $k-1$ types of donuts. The constraint on number of donuts of each type still applies to $a_{n-2,k-1}$, and $a_{n-4,k-1}$, and $a_{n-6,k-1}$. If the constraints applied only to type $k$, the recurrence would instead be \begin{align} a_{n,k} &= b_{n-2,k-1} + b_{n-4,k-1} + b_{n-6,k-1} \\ b_{n,k-1} &= \sum_{j=1}^n b_{n-j,k-2} \end{align} where $b_{n,k}$ is the (unconstrained) number of ways to order $n$ donuts of $k$ types.

Note: as a sanity check, you should find that $a_{n,k}=0$ when $n$ is odd.