[MOSP 2001] Counting number of sets

Let $n \in \mathbb{N}$ be odd. Let's define $O$ and $E$ as, respectively, the set of odd and even number between $1$ and $n$ . Since $n$ is odd, we have that $\displaystyle |E|=\frac{n-1}{2}$ and $\displaystyle |O|=\frac{n+1}{2}$ . We know that all the elements $k \in S$ are such that $k \geq 2|S|$ for a given $|S|$ and have the same parity, i.e.

$S_i \subset O \setminus \{k \in O : k \leq 2|S|\}$

and

$S_j \subset E \setminus \{k \in E : k \leq 2|S|\}$ .

for $i \neq j$ . In other words, for each $|S|$ there will be some $S_i$ subsets of $O$ and $S_j$ subsets of $E$ . Clearly, the number of $k \in O$ such that $k \leq 2|S|$ is

$\displaystyle |O|-|S|=\frac{n+1}{2}-|S|$

and number of $k \in E$ such that $k \leq 2|S|$ is

$\displaystyle |E|-(|S|-1)=\frac{n-1}{2}-|S|+1=\frac{n+1}{2}-|S|$ .

So, for a given $|S|$ , the number of possible $S_i$ is

$\displaystyle \binom{|O|-|S|}{|S|}=\binom{\frac{n+1}{2}-|S|}{|S|}$

and the number of possible $S_j$ is

$\displaystyle \binom{|E|-(|S|-1)}{|S|}=\binom{\frac{n+1}{2}-|S|}{|S|}$

so that the number of possible $S$ is

$\displaystyle \binom{|O|-|S|}{|S|}+\binom{|E|-(|S|-1)}{|S|}=2\binom{\frac{n+1}{2}-|S|}{|S|}$

We know that $|S| \geq 1$ , but we have to find its upper bound. From the binomial coefficient we can write that

$\displaystyle \frac{n+1}{2}-|S|=|S| \hspace{5pt} \Longrightarrow \hspace{5pt} |S|=\Bigl\lfloor \frac{n+1}{4}\Bigr \rfloor$

since $|S|$ is a positive integer. Eventually

$\displaystyle a_n=\sum_{|S|=1}^{\Bigl\lfloor \frac{n+1}{4}\Bigr \rfloor} 2\binom{\frac{n+1}{2}-|S|}{|S|} \hspace{5pt} \Longrightarrow \hspace{5pt} a_{37}=\sum_{|S|=1}^{9} 2\binom{19-|S|}{|S|}=\boxed{13528}$