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

TrueTears · « **Reply #435 on:** December 16, 2009, 11:31:38 pm »

Haha that is awesome kamil, I hardly think of tree diagrams damn.

TrueTears · « **Reply #436 on:** December 17, 2009, 03:38:27 am »

Quote

4. For each $n \ge 1$ , we call a sequence of $\mbox{n}$ (s and n)s 'legal' if the parentheses match up. For example, if $n =4$ , the sequence (()()()) is legal, but ()())(() is not. Let $l_n$ denote the number of legal arrangements for the $2n$ parentheses. Find a recurrence formula for $l_n$ .

Consider the specific case when $n = 10$ .

Now imagine we have $20$ slots _ _ _ _ _ $\cdots$ _

Each slot is distinct and lets name them $1,2,3, \cdots 20$ .

A partition can be done like this: Let $A_k$ be the set containing all possible ways of having a left bracket ' $($ ' with a correspondent right bracket ' $)$ ' on the slot $k$ .

For example, $($ $)$ _ _ _ _ $\cdots$ _ would be $A_2$

However $($ _ _ $)$ _ _ _ $\cdots$ _ would be $A_4$ .

Noticing that $k \in \{\mbox{even numbers}\}$

Thus $l_{10} = |A_2| + |A_4| + |A_6| + \cdots + |A_{20}|$

Now let's take a look at say $|A_6|$

$($ _ _ _ _ $)$ _ _ _ $\cdots$ _
1 2 3 4 5 6 7 8 9 20

Now clearly $|A_6| = (l_2)(l_{\frac{20-7+1}{2}}) = (l_2)(l_7)$ since the slots in between must also contain legal brackets.

Now what about $|A_2|$ ?

Using the same principle we should get $|A_2| = (l_0)(l_9)$

So clearly $l_{10} = (l_0)(l_9) + (l_1)(l_8) + (l_2)(l_7) + \cdots + (l_9)(l_0)$

This looks very similar to the Catalan Recurrence.

Now we can generalise.

Imagine now there are $\mbox{n}$ pairs which means now there are $2n$ slots.

$l_{n} = |A_2| + |A_4| + |A_6| + \cdots + |A_{2n}|$

$|A_{2}| = (l_0)(l_{\frac{2n-2}{2}}) = (l_0)(l_{n-1})$

$|A_4| = (l_1)(l_{\frac{2n-4}{2}}) = (l_1)(l_{n-2})$

$\therefore l_n = (l_0)(l_{n-1}) + (l_1)(l_{n-2}) + (l_2)(l_{n-3}) + \cdots + (l_{n-1})(l_{0})$

Now we have the recurrence formula for the question.

What happens if we evaluate $l_1, l_2$ etc?

Let us define $l_0 = 1$

$l_1 = 1$

$l_2 = 2$

$l_3 = (l_0)(l_2) + (l_1)(l_1) + (l_2)(l_0) = 2 + 1 + 2 =5$

$l_4 = (l_0)(l_3) + (l_1)(l_2) + (l_2)(l_1) + (l_3)(l_0) = 5 + 2 + 2+ 5 = 14$

If we continue the sequence we get $1,1,2,5,14,42,132, \cdots$ which is the Catalan sequence!

$\therefore l_n = \frac{1}{n+1}\binom{2n}{n}$ for $n \ge 0$

/0 · « **Reply #437 on:** December 17, 2009, 04:54:36 am »

Very nice TT!

Quote from: TrueTears on December 16, 2009, 02:56:29 am

3. Fix positive $a,b,c$ . Define a sequence of real numbers by $x_0 = a, x_1 = b \ \mbox{and} \ x_{n+1}=cx_nx_{n-1}$ . Find a formula for $x_n$ .

I've thought about a really messy possibility

$\begin{array}{rcl}x_0 &=& a \\\\ x_1 &=& b \\\\ x_2 &=& cab \\\\ x_3 &=& c^2ab^2 \\\\ x_4 &=& c^4a^2b^3 \\\\ x_5 &=& c^7a^3b^5 \\\\ x_6 &=& c^{12}a^5b^8 \end{array}$

If the closed form is like $x_n = c^{c_n}a^{a_n}b^{b_n}$ , we have

$a_{n} = a_{n-1}+a_{n-2}$

$b_{n}=b_{n-1}+b_{n-2}$

So $a_n$ and $b_n$ can be found with binet's formula

For $c_n$ we have

$c_n = 1+c_{n-1}+c_{n-2}$

If we write the following equations:

$\begin{array}{rcl} c_n &=& 1+\rlap{/}{c_{n-1}}+\rlap{/}{c_{n-2}} \\\\ \rlap{/}{c_{n-1}} &=&1 +\rlap{/}{c_{n-2}}+\rlap{/}{c_{n-3}} \\\\ \rlap{/}{2\rlap{/}{c_{n-2}}} &=& 2+\rlap{/}{2\rlap{/}{c_{n-3}}}+\rlap{/}{2\rlap{/}{c_{n-4}}} \\\\ \rlap{/}{3\rlap{/}c_{n-3}}} &=& 3+\rlap{/}{3\rlap{/}{c_{n-4}}}+\rlap{/}{3\rlap{/}{c_{n-5}}} \\\\ \rlap{/}{5\rlap{/}{c_{n-4}}}&=&5+\rlap{/}{5\rlap{/}{c_{n-5}}}+\rlap{/}{5\rlap{/}{c_{n-6}}}\\ &. \\ &. \\\\ \rlap{/}{F}(n\rlap{/}{-}2)\rlap{/}{c_{3}}&=& \rlap{/}{F}(n\rlap{/}{-}2)+\rlap{/}{F}(n\rlap{/}{-}2)\rlap{/}{c}_2+F(n-2)c_1 \\\\ \rlap{/}{F}(n\rlap{/}{-}1)\rlap{/}{c_{2}}&=& F(n-1)(1+c_1+c_0)\end{array}$

Where $F(i)$ is the (i)th Fibonacci number, and we add all the equations up, then we should get

$c_n = \sum_{i=1}^{n-2}F(i) +F(n-2)c_1+F(n-1)(1+c_1+c_0)=\sum_{i=1}^{n-1}F(i)$ ( $c_1=c_0=0$ )

Now all there is to do is find the closed form for the fibonacci sum....
Not very elegant rofl

humph · « **Reply #438 on:** December 17, 2009, 05:22:59 am »

Quote from: /0 on December 17, 2009, 04:54:36 am

Where $F(i)$ is the (i)th Fibonacci number, and we add all the equations up, then we should get

$c_n = \sum_{i=1}^{n-2}F(i) +F(n-1)(1+c_1+c_0)=\sum_{i=1}^{n-1}F(i)$

Now all there is to do is find the closed form for the fibonacci sum....
Not very elegant rofl

By this, the answer comes out quite nicely, and you can write it in a closed form.

Ahmad · « **Reply #439 on:** December 17, 2009, 12:42:42 pm »

Quote from: /0 on December 17, 2009, 04:54:36 am

$c_n = 1+c_{n-1}+c_{n-2}$

Once you get to here a simplifying trick is to set $d_n = 1 + c_n$ , then the recursion becomes $d_n = d_{n-1} + d_{n-2}$ with $d_1 = d_0 = 1$ , which means $d_n$ is a shifted Fibonacci sequence, $d_n = F_{n+1}$ so that $c_n = F_{n+1} - 1$ .

Well done though

/0 · « **Reply #440 on:** December 17, 2009, 01:03:45 pm »

Quote from: Ahmad on December 17, 2009, 12:42:42 pm

Quote from: /0 on December 17, 2009, 04:54:36 am
$c_n = 1+c_{n-1}+c_{n-2}$

Once you get to here a simplifying trick is to set $d_n = 1 + c_n$ , then the recursion becomes $d_n = d_{n-1} + d_{n-2}$ with $d_1 = d_0 = 1$ , which means $d_n$ is a shifted Fibonacci sequence, $d_n = F_{n+1}$ so that $c_n = F_{n+1} - 1$ .

Well done though

Ah, that's clever ;p

TrueTears · « **Reply #441 on:** December 17, 2009, 02:35:37 pm »

haha awesome solution /0

So basically:

$a_n = F_{n-1} \ \forall \ n \ge 1$ and define $a_0 = 1$

$b_n = F_{n} \ \forall \ n \ge 0$

$c_n = F_{n+1}-1 \ \forall \ n \ge 0$

TrueTears · « **Reply #442 on:** December 17, 2009, 05:35:01 pm »

Challenge question: (Putnam)

Define a selfish set to be a set that has its own cardinality as an element. Find, with proof, the number of subsets of $\{1,2, \cdots, n\}$ that are minimal selfish sets, that is, selfish sets none of whose proper subsets is selfish.

kamil9876 · « **Reply #443 on:** December 17, 2009, 06:42:16 pm »

i remember doing that one

it's easier than the previous q's u've been doing IMO

TrueTears · « **Reply #444 on:** December 17, 2009, 06:43:47 pm »

Quote from: kamil9876 on December 17, 2009, 06:42:16 pm

i remember doing that one it's easier than the previous q's u've been doing IMO

lolz yeah I'm having a go now, don't post solution yet

or put it in white if you are going to post solution, I wanna have some fun too

dcc · « **Reply #445 on:** December 18, 2009, 12:14:11 am »

I completely screwed up my first attempt at this, but I realised the trick as I was driving home from a jam

Let $C_n$ be the number of minimal selfish subsets of $A_n = \{1,2,\dots,n\}$ . Consider some $k \in \{1,2, \dots,n\}$ . We wish to find all the minimal selfish subsets of $A_n$ of cardinality $k$ .

We first note that our minimal selfish subsets cannot contain any element less then $k$ , as the existence of such an element allows us to easily construct a selfish subset, which shows that our original subset is not minimal.

Membership in our set is restricted to $k$ and elements between $k$ and up to (and including) $\textbf{n}$ . Therefore we have $n - k$ elements to choose from to make our minimal selfish subsets from. In addition, since our set has cardinality $k$ , then for each potential subset we must choose $k - 1$ numbers to create a full set.

Therefore the number of ways of creating a minimal subset of $A_n$ of cardinality $k$ is $\binom{n-k}{k-1}$ . Summing this over all valid lengths, we find that $C_n = \sum_{k=1}^{n-1} \binom{n-k}{k-1}$ , which is of course a generator of the general Fibonacci sequence.

TrueTears · « **Reply #446 on:** December 18, 2009, 03:54:02 am »

lol I've been at this question for ages, I'm so tempted to look at your solution dcc but I feel that I have almost got it hahaa

TrueTears · « **Reply #447 on:** December 18, 2009, 10:44:59 pm »

Ok here is what I have come up with after last night's thought.

Consider listing out the minimal selfish subsets of $\{1,2,3, \cdots, n\}$

Let $M$ represent a minimal selfish subset.

$n=1 \implies \{1\} \to 1 M$

$n=2 \implies \{1\} \to 1 M$

$n=3 \implies \{1\} \ \mbox{and} \ \{2,3\} \to 2 M$

$n=4 \implies \{1\} \ \mbox{and} \ \{2,3\} \ \mbox{and} \ \{2,4\} \to 3 M$

$n=5 \implies \{1\} \ \mbox{and} \ \{2,3\} \ \mbox{and} \ \{2,4\} \ \mbox{and} \ \{2,5\} \ \mbox{and} \ \{3,4,5\} \to 5 M$

A few things can be noticed.

$M$ is a minimal selfish set if and only if $|M|$ is the smallest element of the set.

Why is this? Consider if there was an element smaller than $|M|$ in the set $M$ . Call this element $m$ .

Thus there exists subsets of $M$ which contains the element $m$ which could also be a selfish set.

Therefore, if $|M|$ is the smallest element of the set $M$ then $M$ is a minimal selfish set.

Consider the specific case when $n = 5$ , there are exactly $2+3=5$ minimal selfish sets.

Partition the minimal selfish subsets of when $n =5$ of the set $\{1,2,3,4,5\}$ to those that have $5$ and those that don't.

Those that do not have $5$ are simply the $n=4$ case which are $\{1\} \ \mbox{and} \ \{2,3\} \ \mbox{and} \ \{2,4\}$

Those that do are $\{2,5\} \ \mbox{and} \ \{3,4,5\}$ . Now note that if we have $M+1$ for the $n=3$ case then we have $\{2\} \ \mbox{and} \ \{3,4\}$ . However these are now no longer minimal selfish conditions as $|M|$ is not the smallest element in the set. So if we add $5$ into the subsets $M+1$ we will change them into minimal selfish subsets that contains $5$ .

Summing together the partitions we get $\{1\} \ \mbox{and} \ \{2,3\} \ \mbox{and} \ \{2,4\} \ \mbox{and} \ \{2,5\} \ \mbox{and} \ \{3,4,5\}$

Now let's try generalise this.

Looking at the sequence of $M$ 's we have $1,1,2,3,5, \cdots$ we see it resembles the Fibonacci sequence, so I am going to conjecture that it does follow the Fibonacci sequence and try to prove it.

Consider for all $n \ge 2$ , let there be $q$ minimal selfish subsets for the set $\{1,2,3, \cdots, n\}$ . Let there be $w$ minimal selfish subsets for the set $\{1,2,3, \cdots, n-1\}$

I conjecture that there will be exactly $q+w$ minimal selfish subsets for the set $\{1,2,3, \cdots, n+1\}$ .

Let's split our approach in two ways, those subsets of $\{1,2,3, \cdots, n+1\}$ that contain $n+1$ and those that do not.

Consider the cases where the subsets does not contain $n+1$ .

Let $M$ be a minimal selfish subset of $\{1,2,3, \cdots, n\}$ . Then $M$ must also be a minimal selfish subset of $\{1,2,3, \cdots, n+1\}$ since $\{1,2,3, \cdots, n\} \subset \{1,2,3, \cdots, n+1\}$

$\therefore$ There are $q$ minimal selfish subsets of $\{1,2,3, \cdots, n+1\}$ without the element $n+1$

Now let us consider the case where the subsets of $\{1,2,3, \cdots, n+1\}$ that contain $n+1$ .

Let $A$ be a minimal selfish subset of $\{1,2,3, \cdots, n-1\}$ .

Let us define $P = \{n+1\} \cup \{A+1\}$

Now notice # $P =$ # $(A+1)$ (Although we changed the number of elements in each set, the total number of sets do not change)

$\therefore$ $P$ is a minimal selfish subset since $|P| = |A+1|$ is the smallest element in $P$ .

This produces exactly $w$ minimal subsets of $\{1,2,3, \cdots, n+1\}$ which contain the element $n+1$ .

But why does this work? The proof is as follows:

Consider the minimal selfish set P of the set $\{1,2,3, \cdots, n+1\}$ that contains the element $n+1$ .

Now $1 \notin P$ since $\min P = |P| = 2$

$A = x-1 \ \mbox{where} \ x \in P \ \mbox{and that} \ x \neq n+1$

$A$ is a minimal selfish subsets since # $A =$ # $(P-1)$ .

$\therefore$ $P = \{n+1\} \cup \{A+1\}$

$\therefore q+w = \mbox{total number of minimal selfish subsets of the set} \ \{1,2,3, \cdots, n-1\}$

If we define $f_n, f_{n-1}$ to be the number of the minimal selfish subsets of $\{1,2,3, \cdots, n\}$ and $\{1,2,3, \cdots, n-1\}$ respectively.

Then we have $f_{n+1} = f_n + f_{n-1}$

$\mbox{Q.E.D}$

zzdfa · « **Reply #448 on:** December 18, 2009, 11:13:21 pm »

hey , about 12 lines from the bottom up, let us define p={n+1} U {A+1}

whats A+1?

TrueTears · « **Reply #449 on:** December 18, 2009, 11:16:39 pm »

Sorry I knew that notation was shit, what I mean is: add 1 to every element in A

Also #A means the number of sets that satisfies A.

Search the forums now!

We have moved!

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

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

/0

Re: TT's Maths Thread

humph

Re: TT's Maths Thread

Ahmad

Re: TT's Maths Thread

/0

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

dcc

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

zzdfa

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

Recent Posts

User:
Password: