Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am getting curious about this question. If any mathematical formula can be derived.

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
share|improve this question
    
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 a*x and b*x 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
2  
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

1 Answer 1

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.

$G(2,3,30)$

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.