Can You Derive These Combinatorics Formulas for Fun?

[hellraiser]

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?

 

[EnumaElish]

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

 

[Hurkyl]

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

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.

 

[hellraiser]

If I had figured that out I would not have bothered to post it here, would I? :)

 

[Hurkyl]

Well, you know something about N, right? And since pq = N...

 

[hellraiser]

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.

 

[0rthodontist]

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.

 

[vaishakh]

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 different 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)