1
$\begingroup$

As you may know, in order to find the number of factors for natural number X, we take the prime factorization, add one to each exponent, and multiply, as such.

$200 = 2^3*5^2$

$(3+1)(2+1) = (4)(3) = 12$

If you were to manually list the factors, you would end up with 12. However, it's unclear to me why the following method does not work.

If we are faced with a set N (don't know the set notation from memory) there will be X subsets of N where X is $2^N$. This makes sense, we have the choice to include or not include an element (hence the 2) N times.

If we expand $2^3*5^2$ into a set (the prime factorization of 200) we get the set (2, 2, 2, 5, 5). We can either include or not include each of these elements. After all, a factor of a number is just a combination of the same primes numbers that make up a larger number; they are just in smaller amounts/quantities. We can take up to 3 2's and 2 5's from this set. There are 32 subsets of (2, 2, 2, 5, 5) ($2^5$ = 32). Yet, there are 12, not 32 factors, of 200. I do understand this method does not work, however I'm unclear on why it does not work, as the logic seems sensible to me.

I feel I'm missing something obvious :P

$\endgroup$
9
  • 1
    $\begingroup$ Counting, say, the first $2$ (and nothing else) gives the same factor as counting the second $2$ and nothing else. $\endgroup$
    – lulu
    Jun 16, 2016 at 1:56
  • 2
    $\begingroup$ Just saying, $\lbrace 2, 2, 2, 5, 5\rbrace$ is not a set $\endgroup$ Jun 16, 2016 at 1:58
  • $\begingroup$ @lulu Ah I see, it's related to counting permutations vs. combinations? $\endgroup$ Jun 16, 2016 at 1:58
  • 2
    $\begingroup$ With regards to @Ed_4434 's comment, for sets that allow multiplicity see this. $\endgroup$ Jun 16, 2016 at 2:05
  • 1
    $\begingroup$ @Ed_4434 That's why they're not called sets :) $\endgroup$ Jun 16, 2016 at 2:09

1 Answer 1

4
$\begingroup$

It is true that if you have a set $X = \{x_1, \ldots, x_n\}$ (so $|X| = n$), then the powerset $\mathcal{P}(X)$, i.e. the set of all subsets of $X$, has cardinality $2^n$. Unfortunately, you cannot use this for your intentions. Consider the simple case of $4$, which has prime factorisation $2^2$. Going along the same path as you, we get the "set" $X=\{2,2\}$. But then $\mathcal{P}(X) = \{\varnothing, 2, 2, X\}$. We can of course consider some other set $\mathcal{P}(X) \setminus \{\varnothing, X\}$ to get the "set" $\{2,2\}$, but we cannot avoid the problem of counting the same factor multiple times, which has also happened in your case.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .