1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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