I am attempting to solve the following problem: Given n numbers (from 1->n), how many ways are there to select k even numbers, and j odd numbers, such that no two numbers are consecutive.
Can anyone provide a closed form for this; aka, without the use of recurrence relations or generating functions? Sigma is acceptable though.
I am aware of an existing question that tackles this, but without the even and odd distinction.
Best Answer
Well, there's a helpful recursion:
Let $S(n,j,k)$ be the answer. Then, noting that either $1$ is in the selection or it is not, we see that $$S(n,j,k)=S(n-2,j-1,k)+S(n-1,k,j)$$
This, at least, provides a way to compute many examples.