Author Topic: TT's Maths Thread (Read 150023 times) Tweet Share

TrueTears · « **Reply #225 on:** November 29, 2009, 03:31:38 pm »

Quote from: zzdfa on November 29, 2009, 09:38:17 am

yep that's correct. you can use it to prove fermat's little theorem: $a^p \equiv a \mod p$ for prime p and any integer a,
by considering the multinomial expansion of $(\underbrace{1+\cdots+1}_{\mathrm{a \, times}})^p$ .

Thanks zzdfa!

Haha Fermat's Little Theorem, how cute does that sound lolz

kamil9876 · « **Reply #226 on:** November 29, 2009, 05:04:04 pm »

and how sentimental does "last" sound

TrueTears · « **Reply #227 on:** November 29, 2009, 11:38:47 pm »

Just a few questions

1. Can someone show me a combinatorial proof of the hockey stick identity? $\binom{r}{r}+\binom{r+1}{r}+\binom{r+2}{r}+ \cdots + \binom{f}{r} = \binom{f+1}{r+1}$ . I've done it for a specific case say when $f = 5$ and $r = 2$ . But I don't know how to generalise it.

~~2. How many different ordered triples $(a,b,c)$ of non-negative integers are there such that $a+b+c=50$ ?~~

How would you do this question using partitions?

Thanks!

Ahmad · « **Reply #228 on:** November 30, 2009, 01:13:46 am »

Let me address finding the number of triples (a,b,c) of non-negative integers such that a + b + c = 5 instead of 50, as this will simplify my explanation.

This is a well known problem with a well known argument, which involves a little trick which seems somewhat new at least the first time you see it. The underlying principle is: if you're trying to count a set of objects which is hard to count, show that there is a one-to-one correspondence between this set of objects and a simpler set of objects which you can count, as both of the sets have the same number of elements you'll be done if you can count the latter set of objects.

Consider 7 objects in a row, o o o o o o o. Suppose I choose 2 of them in some way, and replace them by the symbol +. For example o + o + o o o. I can interpret this as "1 + 1 + 3" if i replace o by 1, and o o o by 3. This is convenient because 1 + 1 + 3 = 5, is a solution to our equation given by the triple (1,1,3). And a little thought shows that any way I select two objects to be replaced by + signs I get a solution to the equation, provided we interpret something like + + o o o o o as "0 + 0 + 5 = 5" which is the solution (0,0,5). Similarly, any solution to our equation gives rise to exactly one selection of two of the seven objects to be replaced by + signs. Hence we've shown that there is a one-to-one correspondence between solutions of the equation and selections of 2 objects from 7. Which means the number of such solutions is C(7, 2). And the same argument can be used to show the number of solutions to our original problem is C(50 + 2, 2)

This solution is slightly tricky to come up with. However there is a method to solve this problem routinely using the concept of generating functions, which I will not show.

kamil9876 · « **Reply #229 on:** November 30, 2009, 01:29:19 am »

1.)

ok so we got a set of f+1 objects and we want to know how many different subsets of these there are that consist of r+1 objects. We can count these subsets like this: First consider all these subsets that contain the element 'a', now because we have chosen a, there are f objects left to choose from, and we must choose r of them. Hence there are (f,r) different ways of choosing this. Now we move on to the subsets that have b, but do not have a(since we have already counted these previously), We have chosen one object b, hence we are left with r objects left to choose from f-1 objects (since we cannot pick a or b for these remaining objects). This accounts for the the (f-1,r) term.
Now we move on to the subsets that contain c, but do not contain neither a or b. Having already chosen c, we have r objects left to choose from f-2 objects (since we are not choosing a,b or c for our remaining ones) this accounts for the (f-2,r) term.

Now keep applying this d,e,f... etc until you get f-k=r. In that case there would only be one set left, the set with objects z,y,w,x.... etc that you have not chosen.

TrueTears · « **Reply #230 on:** November 30, 2009, 01:42:15 am »

Thanks Ahmad!

I noticed another less elegant way using partitions:

Let $a+b = q$

Then the equation $a+b+c=50$ becomes $q+c=50$

If we let $c = 0$ then $q = 50$ ... $[0]$

$c=1 \implies q = 49$ ... $[1]$

$c=2 \implies q = 48$ ... $[2]$

.
.
.

$c=50 \implies q = 0$ ... $[50]$

Let's look at when $c = 0$ and $q = 50$ specifically.

Once we fix in the value of $c$ we need to decide how many different pairs of $a$ and $b$ we can get to sum up to $50$ .

By listing some pairs of $(a,b)$ we get a feel of how many ordered pairs there are: $(0,50), (1,49) ... (50,0)$

$\therefore$ there are $51$ ways for $[0]$ .

Consider $[1]$ . Again listing pairs of $(a,b)$ we get: $(0,49), (1,48) ... (49,0)$

$\therefore$ there are $50$ ways for $[1]$

We see a pattern: the number of ways for each case is just $q+1$ .

Thus if we sum together all the partitions: $|[0]| + |[1]| + |[2]| + ... + |[50]| = 51+50+49+...+1 = \frac{(51)(52)}{2} = 1326$

TrueTears · « **Reply #231 on:** November 30, 2009, 02:27:00 am »

Quote from: kamil9876 on November 30, 2009, 01:29:19 am

1.)

ok so we got a set of f+1 objects and we want to know how many different subsets of these there are that consist of r+1 objects. We can count these subsets like this: First consider all these subsets that contain the element 'a', now because we have chosen a, there are f objects left to choose from, and we must choose r of them. Hence there are (f,r) different ways of choosing this. Now we move on to the subsets that have b, but do not have a(since we have already counted these previously), We have chosen one object b, hence we are left with r objects left to choose from f-1 objects (since we cannot pick a or b for these remaining objects). This accounts for the the (f-1,r) term.
Now we move on to the subsets that contain c, but do not contain neither a or b. Having already chosen c, we have r objects left to choose from f-2 objects (since we are not choosing a,b or c for our remaining ones) this accounts for the (f-2,r) term.

Now keep applying this d,e,f... etc until you get f-k=r. In that case there would only be one set left, the set with objects z,y,w,x.... etc that you have not chosen.

Oh right, thanks kamil, that was exactly the sort of combinatorial argument I was looking for

Ahmad · « **Reply #232 on:** November 30, 2009, 03:46:24 am »

I'm going to prove the result using the idea of generating functions. Hopefully this will be clear enough that you'll be able to understand it with very little background knowledge.

I've given some examples of generating functions, even though I've never told you exactly what they are. From the examples you might've picked up that they're some sort of polynomial or involve a polynomial type of expression. And since we're dealing with binomial coefficients it's natural to ask yourself where you've seen polynomials and binomial coefficients, with the obvious answer being in the binomial theorem! C(n, k) is the coefficient of x^k in (1+x)^n, which we write as C(n, k) = [x^k] (1 + x)^n.

Now that we have C(n, k) = [x^k] (1 + x)^n the problem becomes routine. We know that,

$\binom{r}{r}+\binom{r+1}{r}+\binom{r+2}{r}+ \cdots + \binom{f}{r}$

$= ([x^r] (1 + x)^r) + ([x^{r}] (1 + x)^{r+1}) + \cdots + ([x^{r}] (1 + x)^{f})$

$= [x^r] \left( (1+x)^r + \cdots + (1+x)^{f} \right)$

which we can easily sum, since it's a geometric sum

$= [x^r] x^{-1}\left( (1+x)^{f+1} - (1+x)^r \right)$

we can "absorb" the $x^{-1}$ by increasing the coefficient extraction index from r to r+1

$= [x^{r+1}] \left( (1+x)^{f+1} - (1+x)^r \right)$

$= [x^{r+1}](1+x)^{f+1} - [x^{r+1}](1+x)^r$

notice the second term here contributes nothing since $(1+x)^r$ has no $x^{r+1}$ term

$= \binom{f+1}{r+1}$

which was to be shown.

Why is this solution good?
- If you know anything about generating functions it's very simple to set up the first line of the argument
- Once you've set up the first line the rest is just mindless and simple algebra
- Adapts easily to lots of other identities (in fact there's a powerful algorithm involving generating functions which "simplifies" any combinatorial sum)

Why is this solution bad?
- It's lengthier than kamil's elegant proof
- It proves the correctness of the identity but it gives you no insight, it doesn't tell you "why" the result is true, kamil's solution does

Anyway I really ought to get to bed. Night

TrueTears · « **Reply #233 on:** November 30, 2009, 03:54:58 am »

Wow even though I haven't learn generating functions yet I understood that splendid explanation! I can see why you like generating functions so much now

TrueTears · « **Reply #234 on:** November 30, 2009, 05:05:00 pm »

Another combinatorics question:

Do there exist at least 10,000 10 digit numbers divisible by 7, all of which can be obtained from one another by a reordering of the digits?

I'm just not quite sure how to link the divisible by 7 part with the reordering of the digits. I know how to find out how many different permutations exist for each 10 digit number but how to find one that is divisible by 7?

TrueTears · « **Reply #235 on:** November 30, 2009, 07:49:40 pm »

yay thanks kamil for hint I got it

Let the set which contains numbers that can be formed by reordering their digits be called $\mathbb{S}$ .

So for example, one type of $\mathbb{S}$ can contain $1,222,333,444$ or $1,333,222,444$ etc. This $\mathbb{S}$ contains a total of $\frac{10!}{3!3!3!}$ elements.

Another type of $\mathbb{S}$ can contain $1,111,122,222$ etc which would only have $\frac{10!}{5!5!}$ elements.

Therefore to count the number of multiples of $7$ between $1$ and $9,999,999,999$ would be denoted by $\left \lfloor \frac{9,999,999,999}{7} \right \rfloor$

Thus using the pigeon hole theorem, if we have $\left \lfloor \frac{9,999,999,999}{7} \right \rfloor$ many multiples of $7$ and $q$ groups of set $\mathbb{S}$ then at least one set $\mathbb{S}$ will contain $\left \lceil \frac{\left \lfloor \frac{9,999,999,999}{7} \right \rfloor}{q} \right \rceil$

Thus if we can find out how many $q$ there are such that $\left \lceil \frac{\left \lfloor \frac{9,999,999,999}{7} \right \rfloor}{q} \right \rceil \ge 10000$ then we have answered the question.

Consider using encoding to find out $q$ .

Let $a_i$ denote the amount of $i$ in a $10$ digit number such that $a_0+a_1+...+a_9 = 10$

So say for example, the number $1,222,333,444$ has $a_1 = 1$ , $a_2=a_3=a_4=3$ and the rest $a_0=a_5=a_6=...=a_9 = 0$ Now notice how $a_0+a_1+a_2+...+a_9 = 10$

Now we have created a bijection between $a_i$ and a certain set $\mathbb{S}$ which means if we can find out how many different solutions there are to $a_0+a_1+...+a_9 = 10$ then we have found out how many groups of $\mathbb{S}$ there are (which is equal to $q$ )

Now using a similar trick Ahmad used earlier:

Consider $o+o+o+o+o+o+o+o+o+o = 10$ $o$ 's.

That string above would represent the string $(a_0,a_1,...,a_9)$ such that $(a_0,a_1,...,a_9) = (1,1...1)$

Now if we move the $+$ sign somewhere say like this:

$++o+o+o+o+o+o+o+ooo$

That string above would represent the string $(a_0,a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9)$ $= (0,0,1,1,1,1,1,1,1,3)$

This means that by rearranging the $9$ $+$ signs we get a different set of solutions to $a_0+a_1+a_2+...+a_9 = 10$

So how many ways can we rearrange the $9$ $+$ signs?

Well there's $19$ different 'slots' to place $+$ and $o$ and we need to pick $9$ slots to place a $+$ which means the $o$ slots fall naturally into place.

Therefore there are $\binom{19}{9}$ ways of rearranging the $+$ signs.

And since we created a bijection between the different rearrangement of the strings and $q$

$\therefore q = \binom{19}{9}$

Subbing $q$ back in yields:

$\left \lceil \frac{\left \lfloor \frac{9,999,999,999}{7} \right \rfloor}{\binom{19}{9}} \right \rceil = 15465 > 10000$

So yes there do exist at least $10,000$ $10$ digit numbers divisible by $7$ , all of which can be obtained from one another by a reordering of the digits

TrueTears · « **Reply #236 on:** November 30, 2009, 07:55:51 pm »

Actually another way is just to use the balls in urn formula:

$a_0+a_1+a_2+...+a_9 = 10$

Since we have $10$ balls and we want to put them into $10$ urns labelled $a_0,a_1...a_9$

$\implies \binom{10+10-1}{10} = \binom{10+10-1}{10-1} = \binom{19}{9}$

But I still like the 'intuitive' way better

zzdfa · « **Reply #237 on:** November 30, 2009, 08:14:04 pm »

Quote from: TrueTears on November 30, 2009, 07:49:40 pm

Let the set which contains numbers that can be formed by reordering their digits be called $\mathbb{S}$ .

Just letting you know, you can call them equivalence classes, sounds pr0er: http://en.wikipedia.org/wiki/Equivalence_class

i.e. 'We call 2 numbers equivalent if they can be obtained by one another by reordering digits'
'we are counting the number of equivalence classes'

kamil9876 · « **Reply #238 on:** November 30, 2009, 09:08:08 pm »

yep and more importantly it's a very precise way of describing it.

Over9000 · « **Reply #239 on:** November 30, 2009, 11:41:12 pm »

I've unanimously decided to take over this thread for my own personal benefit and facilitate my own self-discovery.
You got a problem with it? Then turn off your station!
Whata bout it?
Whata bout it?

Anyway, my first question is....

The reciprocal of 4 positive integers add up to $\frac{19}{20}$ . Three of these integrers are in ratios 1:2:3. What is the sum of the four integers.

Search the forums now!

We have moved!

Author Topic: TT's Maths Thread (Read 150023 times) Tweet Share

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

Ahmad

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

Ahmad

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

zzdfa

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

Over9000

Re: TT's Maths Thread

Recent Posts

User:
Password: