# Google Question: Number of ways to select sets such that n is pure

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

• What's the rank of $k\in S$? – Jonathan Y. Nov 4 '13 at 17:35
• @JonathanY. I guess $\operatorname{rank}(k)=|\{\,x\in S\mid x\le k\,\}|$. – Hagen von Eitzen Nov 4 '13 at 17:35
• Is it correct that $n$ need not be in $S$? For instance, can you say that $8$ is also pure with respect to $S = \{2, 3, 7\}$, because the rank of $8$ is $3$ (is it?), and so on? I assume the answer is no (i.e. $n$ has to be in $S$ for rank to be defined). – ShreevatsaR Nov 4 '13 at 18:13
• No n has to be in S – user103260 Nov 4 '13 at 18:34
• no, lets say n=10 consider S={4,6,9,10} it satisfies – user103260 Nov 4 '13 at 21:02

## 2 Answers

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}}}$.

There is a clear recursion: taking any set with largest number $n$ and $k$ elements with $n$ pure and removing all elements larger than $k$ will leave a set with largest number $k$ and $k$ pure.

Suppose the smaller set has $j$ elements. Then there are $k-j-1$ other elements strictly less than $n$ and greater than $k$ in the large set, and they can be chosen from $n-k-1$ possibilities.

So if $f(n,k)$ is the number of sets with largest number $n$ and $k$ elements with $n$ pure, we have

$$f(n,k)=0 \text{ if } n \le k$$

$$f(n,1)=1 \text{ if } n \ge 2$$

$$f(n,k)= \sum_{j=1}^{k-1} {n-k-1 \choose k-j-1} f(k,j) \text{ if } n \gt k \ge 2$$

Then taking $\sum_k f(n,k)$ gives the sequence starting at $n=2$ of:

$1, 2, 3, 5, 8, 14, 24, 43, 77, 140, 256, 472, 874, 1628, 3045, 5719, 10780, 20388, 38674, 73562, 140268, 268066, 513350, 984911, 1892875, 3643570, 7023562, 13557020, 26200182, 50691978, 98182666, 190353370, 369393466, 717457656$

which seems to be essentially OEIS A007059 or A079500.