TT's Maths Thread

[TrueTears]

Awesome, thanks kamil

[TrueTears]

For positive integers , define

Show that


I swear that looks so similar to haha

[kamil9876]

an observation: so perhaps show that you are counting P(x,n) in small parts.

[TrueTears]

Sorry I edited the question, had a typo

[TrueTears]

1. Let denote the number of ways in which a set of elements can be partitioned into non-empty subsets. For example, , corresponding to:











Find a recurrence relation for .

Consider the specific case for .

Let us consider this element set:

Obviously the element must be in every partition.

Let us denote the set that the element is in 'size ' where tells us how many elements are in that partitioned set.

For example, the partitioned set has size .

Consider size 1, we have:



But how many ways can we partition ? Well there are ways to partition it.

Thus for size 1 there are ways.

Consider size 2, we have:



For the 'some other element' we have choices and then for the 'Three element set' we have ways to partition it.

In total we have ways

Consider size 3.

We would have ways

Size 4: ways

Size 5: ways

In total:

Now let's generalise:

Say we have a element set.

Haha, just realised that this is the bell number sequence. http://en.wikipedia.org/wiki/Bell_number

[Ahmad]

Algebra.

It's true for n=1. Suppose that,



then we have,









we can start the left sum off from k = 1 since the summand for k = 1 is zero. Same goes for the right sum going until k = n+1 since that summand is zero too.



we can use the recursion on the previous page of this thread giving



which completes the induction

[Ahmad]

Combinatorics.
Outline: I'm going to prove that for positive integer values of both sides of the identity agree. Since both sides are polynomials in x if they agree on the positive integers then they must be identical (why?).

Suppose is a positive integer. I claim both sides count the number of functions . We can map 1 to any of x values, 2 to any of x values and so on, hence there are such functions, which is the left hand side. We can also condition on the number of elements of the image/range. If the range contains k elements, then we can partition the domain into k sets, and assign to each set a particular distinct value of the range. There are ways to partition the domain into k sets, and there are ways to assign a distinct element of the codomain to each of these k sets, that is easy to see: label the sets of the partition , then can be assigned any of x elements, can be assigned any of x-1 elements and so on, and this constructs a function which has a range containing exactly k elements. Btw, when I say for example is assigned to 3, that means we're considering the function which maps each element of to 3. Summing over the possible values of k gives the right hand side and hence proves the result.  

[TrueTears]

haha awesome, thanks Ahmad, the combinatorial way is so much easier

[TrueTears]

Just started number theory  8-)

Firstly can anyone show me why ?

You can assume the FTA to be true while showing this (I haven't seen the proof for FTA yet )

[Ahmad]

haha awesome, thanks Ahmad, the combinatorial way is so much easier

I personally found the algebraic way easier because it didn't require much thinking on my part. I knew what to do immediately, and the rest was just having enough technique to go through it. The combinatorial way is nicer though

[Ahmad]

I'll do an example and hopefully this will make it clear.

12 = 2^2 x 3
42 = 2 x 3 x 7

To find the gcd of the two of these numbers you take the smallest power of each prime divisor. For example, take the prime p = 2, then 12 has a factor of 2^2 and 42 has a factor of 2^1, so you take 2 to the power of min(2,1) = 1. So gcd(12,42) will have a factor of 2^min(2,1) = 2^1. Similarly, it will have a factor of 3^1 and 7^0. Hence gcd(12,42) = 2^1 x 3^1 x 7^0 = 6. On the other hand to work out the lcm you take the maximum power of each prime divisor, so we'd take 2^max(2,1) = 2^2, 3^max(1,1) = 3^1 and 7^max(0,1) = 7^1. Then the relationship given is just expressing the fact that, . This is true exactly because min(a,b) + max(a,b) = a+b, for example looking at powers of 2, .

[TrueTears]

I'll do an example and hopefully this will make it clear.

12 = 2^2 x 3
42 = 2 x 3 x 7

To find the gcd of the two of these numbers you take the smallest power of each prime divisor. For example, take the prime p = 2, then 12 has a factor of 2^2 and 42 has a factor of 2^1, so you take 2 to the power of min(2,1) = 1. So gcd(12,42) will have a factor of 2^min(2,1) = 2^1. Similarly, it will have a factor of 3^1 and 7^0. Hence gcd(12,42) = 2^1 x 3^1 x 7^0 = 6. On the other hand to work out the lcm you take the maximum power of each prime divisor, so we'd take 2^max(2,1) = 2^2, 3^max(1,1) = 3^1 and 7^max(0,1) = 7^1. Then the relationship given is just expressing the fact that, . This is true exactly because min(a,b) + max(a,b) = a+b, for example looking at powers of 2, .

Ahh thanks the min(a,b)+max(a,b)=a+b was the essential part

[TrueTears]

Show that if and and then

Is this proof valid?

Assume where and

Then let us denote the PPF of as and the PPF of as where is the greatest common factor for and and is a product of primes in and 's PPF respectively.

Then





But if and only if (In fact as well)

Thus

[zzdfa]

yes. a more general way to do it is to note that

if d|a and d|b


then

d|a*x
d|b*y

where x,y are integers


and hence

d|(a*x+b*y)


to apply this to the above example, just let d=(a,b).

we get

(a,b)|(a*x+b*y)

stated in words, any common divisor of a,b must divide any linear combination of a,b.

[TrueTears]

Thanks zzdfa