Counting number of sets I encountered the following problem:
Given two positive integers $n$ and $k$ with the same parity, count the number of sets, $S = \lbrace0< s_1 < s_2 < \dots < s_k = n\rbrace $ such that $s_1, s_3, \dots $ are odd numbers and $s_2,s_4,\dots$ are even numbers.
I can see the trivial cases when $n = 1$ and when $n = 2$ but have no idea how to extend it to a general $n$ and $k$. Any help is greatly appreciated. Thanks!
 A: Instead of finding $s_1,s_2,\dots s_k$ focus on the differences between them: $a_1,a_2,\dots,a_{k-1}$ where $a_j=s_{j+1}-s_j$.
These uniquely determine each $s_j$.
We need for all of the $a_n$'s to be odd, and their sum must be at most $n-1$.
How many solutions in non-negative odd integers are there to $a_1+a_2+\dots+a_{k-1}\leq n-1$? Suppose $a_j=2c_j+1$.
We need $(2c_1+1)+(2c_2+1)+\dots + (2c_{k-1}+1)\leq n-1\iff c_1+c_2+\dots+c_{k-1}\leq \frac{n-k}{2}$. And here the $c_k$ are just non-negative integers.
The number of solutions to $c_1+c_2+\dots + c_{k-1}\leq \frac{n-k}{2}$ in non negative integers is equal to the number of solutions in non-negative integers to $c_1+c_2+\dots+c_k=\frac{n-k}{2}$.
This is given by stars and bars, we have $\frac{n-k}{2}$ stars and $k-1$ bars. So the answer is $\binom{(n+k-2)/2}{k-1}$.
A: We  can reformulate  this  problem  as first  choosing  an odd  number
followed  by $k-1$  odd  gaps between  consecutive  numbers (odd  gaps
change parity). This gives the generating function
$$\frac{z}{1-z^2} \left(\frac{z}{1-z^2}\right)^{k-1}.$$
We multiply  by $1/(1-z)$ to sum  the contributions ending  in at most
$n$ and obtain
$$\frac{1}{1-z} \frac{z^k}{(1-z^2)^k}.$$
Extracting coefficients we get
$$[z^n] \frac{1}{1-z} \frac{z^k}{(1-z^2)^k}
= [z^{n-k}] \frac{1}{1-z} \frac{1}{(1-z^2)^k}.$$
This is
$$\sum_{0\le 2q\le n-k} {k-1+q\choose q}.$$
This sum can be evaluated by inspection or we may use
$${k-1+q\choose q} = [z^q] \frac{1}{(1-z)^k}$$
to get
$$[z^0] \frac{1}{(1-z)^k} \sum_{0\le 2q\le n-k} z^{-q}
= [z^0] \frac{1}{(1-z)^k} 
\frac{1/z^{\lfloor (n-k)/2\rfloor+1}-1}{1/z-1}
\\ = [z^{-1}] \frac{1}{(1-z)^{k+1}} 
(1/z^{\lfloor (n-k)/2\rfloor + 1}-1)
\\ = [z^{\lfloor (n-k)/2\rfloor}] \frac{1}{(1-z)^{k+1}}.$$
We thus get for the end result 
$$\bbox[5px,border:2px solid #00A000]{
{\lfloor (n-k)/2\rfloor +k \choose k}.}$$
Here is a simple Maple  program to help clarify what interpretation of
the question is being used.

with(combinat);

ENUM :=
proc(n, k)
option remember;
local choice, res, pos;
    res := 0;

    for choice in choose(n, k) do
        for pos to k do
            if pos mod 2 <> choice[pos] mod 2 then
                break;
            fi;
        od;

        if pos = k+1 then
            res := res + 1;
        fi;
    od;

    res;
end;

X1 := (n,k) ->
add(binomial(k-1+q,q), q=0..floor((n-k)/2));

X2 := (n,k) -> binomial(floor((n-k)/2)+k, k);

Remark. I somehow overlooked the  fact that the largest element in
the  set is  in fact  fixed and  equal to  $n.$ This  yields  the even
simpler count
$$[z^n] \frac{z^k}{(1-z^2)^k}
= [z^{n-k}] \frac{1}{(1-z^2)^k}.$$
As $n$ and $k$ have the same parity this becomes
$${(n-k)/2 + k-1\choose k-1}.$$
