Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Some combinatorics proofs

  1. Feb 3, 2006 #1
    Hi. We are doing permutations and combinations in class and we were given some formulas without proof to remember. I was able to derive most of them but was unable to derive 3 of them. But I would like to see how do I derive them for sake of fun (also if I forget them what will I do. :) ).

    1. A number is expressed in the form of product of it's prime factors
    N = a^x b^y c^z etc.
    Then the number N can be resolved as a product of 2 factors in how many ways?
    [Ans : If N is not a perfect square 0.5(x+1)(y+1)(z+1)
    If N is a perfect square 0.5[(x+1)(y+1)(z+1)+1]

    All I can think is to take it to be of this form xy = N.
    Then what do I do next.

    2. This one is similar to first. The number of ways in which a composite number N can be resolved into 2 factors which are co prime to each other is 2^(n-1) , where n is number of different factors in N (eg: as in last case n=x+y+z)

    3. Number of ways of arranging n differnet objects in r boxes where arrangement matters within a box
    [(n+r-1)!] / [(r-1)!]

    Any help?
  2. jcsd
  3. Feb 4, 2006 #2


    User Avatar
    Science Advisor
    Homework Helper

    #3 looks to me like the definition of the phrase "arrangement matters." I am not sure how one would prove a definition.
  4. Feb 4, 2006 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, that's a bad thing to do, because x and y already have a meaning in your problem! (They're exponents in the prime factorization of N)

    The idea is fine, you just need to use different letters. Say... pq = N.

    It seems obvious to me that the next thing to do is to figure something out about p and q.
  5. Feb 4, 2006 #4
    If I had figured that out I would not have bothered to post it here, would I? :)
  6. Feb 4, 2006 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, you know something about N, right? And since pq = N...
  7. Feb 5, 2006 #6
    Any help, please? I have thought a lot over this but I can't just get it. What do I do next after I take pq = N.
    And what about the other question.
  8. Feb 5, 2006 #7


    User Avatar
    Science Advisor

    I don't know how you could formally prove the formula (well, I have a vague idea), but you can understand it. Think about what it takes to determine ONE of the factors p or q from the prime factorization of N. Consider the exponents on the factorization. Then refine the idea.

    For #2, I don't think you have stated that correctly. In this case the "number of different factors in N" would be n = 3. You can think about #2 in the same way you can think about #1.

    The third one involves a trick that I don't think you would ever figure out on your own. The key is like this: think about the spaces _between_ containers. So if there are 5 containers, you would have 4 spaces, which you could represent like ////. Now if you have 7 objects then one arrangement of the objects in the containers would go like 132//7/654/ so that container 1 gets "132," containers 2 and 5 get nothing, container 3 gets 7, and container 4 gets "654." You can work out the general formula from there.
    Last edited: Feb 5, 2006
  9. Feb 5, 2006 #8
    Well. You find the number of factors of N. If N = pq, then for each p and q are considered as the factors of N. So half the number of factors to N is the number of solutions.
    N = a^x*b^y*c^z, number of factors = (x+1)(y+1)(z+1)
    Third one I would like to be very explanatory.
    If n differant objects are to be grouped into r groups, then the sum of r numbers which is the number of objects each group contain sums upto n.
    Now the number of possible whole number solutions for two variable are n+1. For three, its the summation of n+1 to 1, and thus (n+1)(n+2)/2.
    Thus number of boxes r = 1 or 2 andthe total number of objects are n, then the total number of solutions = (n+r-1)C(r-1).
    Now for any r, use Induction - polynomials - telescoping and summation to prove that
    Sum k = 0 to n [(k+r-1)C(r-1)] = (n+r)C(r)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook