# Count of Subsets

How many ways can you choose a subset from the set $P = \{1, 2, 3, .. n\}$? The subset $S$ should meet the following condition:

When you choose $x \in P$ to create $S$, you cannot choose $a * x$ and $b * x$ for S.

Example :

n = 3 , a = 2, b = 3
so total subsets are 5 ,i.e, {}, {1}, {2}, {3}, {2, 3}
as if in a particular subset there is 1 so 1*2 = 2 and 1*3 cant be there.
so {1,2}, {1,3} and {1,2,3} can't be there

-
Is there a particular context that inspired your question? I suspect any formula will be a little ugly. –  Lepidopterist Mar 16 '13 at 22:14
Since you're choosing $x$, the only cases $x = a * x$ or $x = b * x$ is for $x, a, b \in \{0, 1\}$. A formula to describe this should simply include such restraint. Either you didn't mean what you wanted, or the solution should be something hereby. –  Rubens Mar 16 '13 at 22:16
Look.. we have to form different subsets and the condition is if u choose x for your subset then you can't choose ax and bx for that subset. –  Shweta Mar 16 '13 at 22:20
Ah, I must have misunderstood your post, then. –  Rubens Mar 16 '13 at 22:22
It probably will be a complicated formula. There seem to be more than $2^{\pi(n)}$ such subsets, where $\pi(n)$ is the number of primes less than or equal to $n,$ because if I understand your definition correctly, any subset $S$ which consists entirely of primes will qualify. I would think that this size is of the right order of magnitude for the answer. –  Geoff Robinson Mar 16 '13 at 23:06

If I understand the question correctly, then you're seeking a formula for $I_{a,b,n}$, the number of subsets $S \subseteq \{1,2,\ldots,n\}$ that satisfy the properties

• $x \in S \implies ax \not\in S$ and
• $x \in S \implies bx \not\in S$.

I think I have to agree with the comments thus far, you're unlikely to encounter a slick exact formula.

We can rephrase this problem as a graph-theoretic problem. Let $G=G(a,b,n)$ be the graph with vertex set $\{1,2,\ldots,n\}$ and edge set $$\big\{\{x,y\}:x<y \text{ and either } y=ax \text{ or } y=bx\big\}.$$ Then the problem asks to count the number $I_{a,b,n}$ of independent sets in this graph. (Alternatively, the number of cliques in the complement of this graph.) The graph $G(2,3,30)$ is drawn below.

We observe that the maximum degree of this graph is at most $4$ (degree $4$ occurs at vertex $v$ when $\max(a,b) v \leq n$ and $v/a \in \mathbb{Z}$ and $v/b \in \mathbb{Z}$). So, while there's lots of theoretical results discussing the difficulty of finding, enumerating, and approximating the number of independent sets, there might be some hope for an algorithmic answer for such a low bounded degree.

Extending Geoff Robinson's comment, not only does the set of primes up to $n$ form an independent set in $G$, but the set $$S_{a,b}=\{i \in \{1,2,\ldots,n\}:i \not\equiv 0 \pmod a \text{ and } i \not\equiv 0 \pmod b\}$$ forms an independent set of $G$ (since every edge has an endpoint whose index is divisible by $a$ or $b$).

Provided $2 \leq a \leq b$, we see $|S_{a,b}|$ is minimised when $a=2$ and $b=3$, so $|S_{a,b}| \geq \lfloor \tfrac{1}{3} n \rfloor$ (we include anything congruent to $\pm 1 \pmod 6$). Any subset of $S_{a,b}$ is an independent set in the graph, so there are at least $2^{|S_{a,b}|}$ independent sets in $G(a,b,n)$. So...

The number of independent sets in $G$ is at least $2^{\lfloor n/3 \rfloor}$.

The true value is probably not much more than this. As a rough guide, in a $4$-regular graph, the number of independent sets is at most $\approx 2^{0.62 n}$ (see Zhao Yufei "The Number of Independent Sets in a Regular Graph", Comb. Prob. Comp. (2010) 19, 315-320).

The reader might also be interested to note that $G$ is a subgraph of the complement of the coprime graph on $\{1,2,\ldots,n\}$, where edges $ij$ occur whenever $\gcd(i,j)=1$.

-