Selecting nonconsecutive odd and even numbers 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.
 A: 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.
A: I will suppose for the moment that $n=2m+1$ is odd. 
Suppose that in the set of $k$ even numbers, there are $d$ pairs of "adjacent" even numbers, of the form $2i$ and $2i+2$. These pairs can overlap, so that $\{4,6,8,14,16\}$ has three adjacencies, $(4,6), (6,8)$ and $(14,16)$. Then it follows that there will be $2k-d$ odd numbers which are adjacent to a chosen even number, so there are $\binom{m+1-2k+d}{j}$ ways to choose the odd numbers. We just need to count the number of sets of even numbers with $d$ adjacencies, for each $d$, then sum over $d$.
There are $k-1$ possible adjacencies, so the adjacencies can be chosen in $\binom{k-1}{d}$ ways. The evens will break into $k-d$ blocks of consecutively adjacent numbers. Let $x_i$ be number of unchosen even numbers between blocks numbered $i$ and $i+1$, for $i=0,1,\dots,k-d$. Note $x_0$ is the number of unchosen numbers before the first clump, and $x_{k-d}$ is the number after the last clump. We need to have $x_i\ge 1$, for each $i=1,\dots,k-d-1$, but we only need $x_0,x_{k-d}\ge 0$. We also need $$x_0+x_1+\dots+x_{k-d}=m-k.$$ Alternatively, we have
$$
(x_0+1)+x_1+\dots+x_{k-d-1}+(x_{k-d}+1)=m-k+2,
$$with each summand is at least one. It follows from stars and bars that the number of ways to do this is
$$
\binom{m-k+1}{k-d}
$$
Therefore, the number of selections is
$$
\sum_{d=0}^{k-1}\binom{k-1}d\binom{m-k+1}{k-d}\binom{m+1-2k+d}{j}
$$
I leave it to you to see how the answer is different when $n=2m$ is even. This case seems like more of a headache; you need to condition based on whether or not $2m$ is in the chosen set of even numbers. 
