Consider a subset $S$ of positive integers. A number in $S$ is considered pure with respect to $S$ if, starting from it, you can continue taking its rank in $S$, and get a number that is also in $S$, until in finite steps you hit the number $1$, which is not in $S$.
When $n$ is given, in how many ways can we pick $S$, a subset of $\{2, 3, ..., n\}$, so that $n$ is pure, with respect to $S$? n is present in $S$
Source: Google code jam
This is a problem that can be solved using dynamic programming in general. But it has a more mathematical answer using enumeration and combinatorics. Can't figure it out. Any hints?
For rank clarification For s={2,3,7} 7 has rank =3 ....... 3 has rank=2 ...... 2 has rank=1
Let $\Omega(n,m)={\large\{}S|S\subset \{2,3,...,n\}, n\text{ is pure with respect to }S\text{, }m\text{ numbers including }n\text{ are reached before hitting }1{\large\}}$
and $\Omega(n)=\cup_{m=1}^{n-1}{\Omega(n,m)}$.
We have to determine $|\Omega(n)|$. Suppose $S\in \Omega(n,m)$ so that $n$ is pure with respect to $S \subset \{2,3,...,n\}$ and $m$ numbers (including $n$) are reached before hitting $1$. Denote these decreasing numbers $k_0=n,k_1,...,k_{m-1}$, and $k_m=1$. Consider $0<i<m$. The number $k_{i-1}$ has rank $k_i$ while the number $k_i$ has rank $k_{i+1}$. So there are $k_i-k_{i+1}-1$ numbers in $S$ that are between $k_{i-1}$ and $k_i$. So $k_{i-1} \ge k_i + 1 + (k_i-k_{i+1}-1)$. That is, $k_{i-1} = 2k_i -k_{i+1}+d_{i-1}$ where $d_{i-1} \in \{0,1,2,3,...\}$.
Defining $\Delta_i=k_i-k_{i+1}$ for $0<i<m$ and $\Delta_m=1$, the above difference equation simplifies to $\Delta_i=\Delta_{i+1}+d_i$ so $\Delta_i=d_i+d_{i+1}+...+d_{m-1}+1$. Then,
$n=k_0=\Delta_0+\Delta_1+...+\Delta_{m-1}+k_m=d_0+2d_1+3d_2+...+md_{m-1}+m+1$
or $n-m-1=d_0+2d_1+3d_2+...+md_{m-1} \tag{1}$
The values of $(d_0,d_1,...d_{m-1})$ satisfying (1) have a one-to-one correspondence with values of $k_0=n,k_1,...,k_{m-1}$ in sets $S\in\Omega(n,m)$. Each such value of $k_0=n,k_1,...,k_{m-1}$ can be associated with multiple sets $S\in\Omega(n,m)$ which differ in set elements other than $k_0=n,k_1,...,k_{m-1}$. Let us consider the number of ways in which these elements can be chosen. As discussed above, for $0<i<m$, $S$ includes exactly $k_i-k_{i+1}-1=\Delta_i-1$ numbers out of $k_{i-1}-k_{i}-1=\Delta_{i-1}-1$ numbers between $k_{i-1}$ and $k_i$. This choice can be made in ${{\Delta_{i-1}-1} \choose {\Delta_{i}-1}}$ ways. So number of $S\in\Omega(n,m)$ associated with any value of $(d_0,d_1,...d_{m-1})$ satisfying (1) is
$\prod_{i=1}^{m-1}{{{\Delta_{i-1}-1} \choose {\Delta_{i}-1}}}=\prod_{i=1}^{m-1}{\frac{(d_{i-1}+d_i+...+d_{m-1})!}{d_{i-1}!(d_i+...+d_{m-1})!}}=\frac{(d_{0}+d_1+...+d_{m-1})!}{d_{0}!d_{1}!...d_{m-1}!}. \tag{2}$
Note solutions of (1) represent partitions of $n-m-1$ into numbers less than or equal to $m$. From (2), the number of solutions (members of $\Omega(n,m)$) associated with a partition of $n-m-1$ into $d_0$ $1s$, $d_1$ 2s,...,$d_{m-1}$ $m$s, equals the number of permutations of $d_0$ objects of one kind, $d_1$ of another kind, and so on, where objects of one kind are identical and are distinguishable from objects of any other kind. So $|\Omega(n,m)|$ equals the number of compositions (ordered partitions) of $n-m-1$ into numbers not exceeding $m$. This equals the coefficient of $x^{n-m-1}$ in the geometric series expansion of $\frac{1}{1-x-x^2...-x^m}$ (See Heubach and Mansour (2004)). So $|\Omega(n)|=\sum_{m=1}^{n-1}{\left(\text{Coefficient of }x^{n-m-1}\text{ in }\frac{1}{1-x-x^2...-x^m}\right)}$.
A solution to (1) can also be seen as a partition of $n$ into a single $m+1$ and other numbers less than or equal to $m$. Viewed this way, $|\Omega(n,m)|$ equals the number of compositions of $n$ in which the first term is $m+1$ and the other terms are less than $m+1$. Summing across different values of $m$, $|\Omega(n)|$ equals the number of compositions of $n$ in which the first term exceeds the remaining terms. This problem is addressed by Knopfmacher and Robbins (2005) and the integer sequence, as pointed out in the answer by Henry, is available in OEIS at A079500. Based on the generating function provided, $|\Omega(n)|$ equals the coefficient of $x^n$ in $(1-x)\sum_{k\ge 0}{\frac{x^k}{1-2x+x^{k+1}}}$.