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

Ahmad · « **Reply #345 on:** December 07, 2009, 10:44:04 pm »

Here's one definition of trivial, but I forget who it's attributed to: a result is trivial when its proof is immediately and automatically conjured in one's mind. That means something that's obvious, such as that a torus and sphere are topologically different, might not be trivial (for most people). There's also the joke that trivial is synonymous with 'proved', so Fermat's last theorem is trivial.

TrueTears · « **Reply #346 on:** December 08, 2009, 12:27:44 am »

Just wondering if this is the right way to do this problem:

In how many ways can we place $r$ red balls and $w$ white balls in $\mbox{n}$ boxes so that each box contains at least one ball of each colour?

Obviously $\{r,w\} \ge \mbox{n}$

Consider a specific case:

$r = 4$ , $w = 6$ and $n = 3$

Let $r_1,r_2,r_3$ be the number of red balls in box $[1],[2],[3]$ respectively. We assume each box to be distinguishable.

We need to apply the restriction so that each box must contain at least one red ball and at least 1 white ball.

Let's consider just the "at least one red ball" part.

Obviously $r_1+r_2+r_3 = 4$

Let $o$ represent a ball. We can represent one scenario like this:

o_o_o_o where _ represents a place to place a + sign.

Eg, o+o_o+o will represent o+oo+o which means 1 ball in $[1]$ , 2 in $[2]$ , 1 in $[3]$ .

Now notice we can't have this scenario +o_o_o+o. This means there will be 0 ball in $[1]$ , 3 in $[2]$ and 1 in $[4]$ but each box must contain at least 1 red ball.

So there are 3 empty _ to place 2 + signs. $\implies \binom{3}{2}$ choices.

Doing the same for the white balls yields $\binom{5}{2}$ choices.

So in total for this specific case we have $\binom{3}{2}\binom{5}{2}$ ways.

Now we can generalise.

We have $r$ red balls, $w$ white balls and $\mbox{n}$ boxes.

Let $r_1,r_2,r_3...r_n$ be the number of red balls in box $[1],[2],[3]...[n]$

Obviously $r_1+r_2+r_3+...+r_n = r$

Now there would be $r-1$ slots to place a + sign $\implies \binom{r-1}{n-1}$ for red balls

For white balls there would be $\binom{w-1}{n-1}$ slots to place the + sign.

Total $\binom{r-1}{n-1}\binom{w-1}{n-1}$ ways.

TrueTears · « **Reply #347 on:** December 08, 2009, 04:10:57 am »

$\binom{r}{0} - \binom{r}{1} + \binom{r}{2} + ... + (-1)^r\binom{r}{r} = 0$

I know this identity can be proved just by expanding $(1-1)^r = 0$

But I was wondering if anyone can show me how to prove it using induction and the use of the summation identity.

kamil9876 · « **Reply #348 on:** December 08, 2009, 01:36:44 pm »

I like this way the best:
http://vcenotes.com/forum/index.php/topic,19896.msg207276.html#msg207276

It's also obvious for odd n.

You can do it by induction by using pascal's identity. ie suppose it is true for n, now we want to prove true for n+1:

$\sum_{j=0}^{j=n+1} (-1)^j\binom{n+1}{j}$

now all we need to do is sub in $\binom{n+1}{j}=\binom{n}{j-1}+\binom{n}{j}$ (for all j>0 of course). So now because we have n's at the top, we can invoke the inductive hypothesis (ie true for n) and split the sums up etc. carefully doing it all.

Ahmad · « **Reply #349 on:** December 08, 2009, 01:44:58 pm »

The identity says that if you have a set of r elements, then the number of subsets containing an odd number of elements is the same as the number of subsets containing an even number of elements. Can you find a combinatorial proof of this?

kamil9876 · « **Reply #350 on:** December 08, 2009, 02:17:35 pm »

Is this the one you're talking about?

Quote from: kamil9876 on December 08, 2009, 01:36:44 pm

I like this way the best:
http://vcenotes.com/forum/index.php/topic,19896.msg207276.html#msg207276

Ahmad · « **Reply #351 on:** December 08, 2009, 02:28:32 pm »

Sure is

TrueTears · « **Reply #352 on:** December 08, 2009, 05:37:51 pm »

Quote

$\binom{r}{0} - \binom{r}{1} + \binom{r}{2} + ... + (-1)^r\binom{r}{r} = 0$

Base Case:

When $r = 2$

$\binom{2}{0} - \binom{2}{1} + \binom{2}{2} = 0$

Inductive Hypothesis:

Assume it is true for $r = k$

$\binom{k}{0} - \binom{k}{1} + \binom{k}{2} + ... + (-1)^{k}\binom{k}{k} = 0$

Proof:

Must show it is true for $r = k+1$

$\binom{k+1}{0} - \binom{k+1}{1} + \binom{k+1}{2} + ... + (-1)^{k+1}\binom{k+1}{k+1} = 0$

But $\binom{k}{0} - \binom{k}{1} + \binom{k}{2} + ... + (-1)^{k}\binom{k}{k} = 0$ is true using our inductive hypothesis.

Using the summation identity:

$\binom{n}{q} = \binom{n+1}{q+1}- \binom{n}{q+1}$

$\binom{k}{0} = \binom{k+1}{0+1}- \binom{k}{0+1}$

$\implies \binom{k+1}{0+1}- \binom{k}{0+1} - \left(\binom{k+1}{1+1}- \binom{k}{1+1}\right) + \left(\binom{k+1}{2+1}- \binom{k}{2+1}\right) + ... + \left[(-1)^{k}\left(\binom{k+1}{k+1}- \binom{k}{k+1}\right)\right] = 0$

$\implies \binom{k+1}{0+1}- \binom{k}{0+1} - \binom{k+1}{1+1}+ \binom{k}{1+1} + \binom{k+1}{2+1}- \binom{k}{2+1}+ ... + (-1)^{k}\left(\binom{k+1}{k+1}- \binom{k}{k+1}\right) = 0$

$\implies \binom{k+1}{1}- \binom{k}{1} - \binom{k+1}{2}+ \binom{k}{2} + \binom{k+1}{3}- \binom{k}{3}+ ... + (-1)^{k}\binom{k+1}{k+1}+(-1)^{k+1} \binom{k}{k+1} = 0$

$\implies \left(- \binom{k}{1}+ \binom{k}{2}- \binom{k}{3}+ ... +(-1)^k\binom{k}{k}\right) + \left(\binom{k+1}{1}- \binom{k+1}{2}+ \binom{k+1}{3}+...+ (-1)^{k}\binom{k+1}{k+1}\right)$

$\implies -1+\binom{k+1}{1}- \binom{k+1}{2}+ \binom{k+1}{3}+...+ (-1)^{k}\binom{k+1}{k+1} = 0$

$\implies 1-\binom{k+1}{1}+ \binom{k+1}{2}- \binom{k+1}{3}+...+ (-1)^{k+1}\binom{k+1}{k+1} = 0$

$\therefore \binom{k+1}{0}-\binom{k+1}{1}+ \binom{k+1}{2}- \binom{k+1}{3}+...+ (-1)^{k+1}\binom{k+1}{k+1} = 0$

$\mbox{Q.E.D}$

TrueTears · « **Reply #353 on:** December 08, 2009, 11:34:36 pm »

Wow just finished reading a chapter on Complement PIE and I gotta say it's probs one of the funnest chapter I've read so far in combinatorics.

A few questions for thought

1. A random number generator randomly generates the integers $1,2,...,9$ with equal probability. Find the probability that after $\mbox{n}$ numbers are generated, the product is a multiple of $10$ .

2. Let $a_1,a_2,...a_n$ be an ordered sequence of n distinct objects. A derangement of this sequence is a permutation that leaves no object in its original place. For example, if the original sequence is $1,2,3,4$ then $2,4,3,1$ is not a derangement, but $2,1,4,3$ is. Let $D_n$ denote the number of derangements of an $\mbox{n}$ -element sequence. Show that $D_n = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - ... + (-1)^n\frac{1}{n!}\right)$

3. Imagine you are going to give $\mbox{n}$ kids ice-cream cones, one cone per kid, and there are $k$ different flavours available. Assuming that no flavours get mixed, show that the number of ways we can give out the cones using all $k$ flavours is $k^n - \binom{k}{1}(k-1)^n + \binom{k}{2}(k-2)^n- \binom{k}{3}(k-3)^n+...+(-1)^k \binom{k}{k}0^n$

kamil9876 · « **Reply #354 on:** December 08, 2009, 11:41:54 pm »

1.) by fundumanetal theorem of arithmetic it is equivalent to: how many different ways so that we don't choose:

5 and an even number.

so find how many ways there are where we have no 5 or no even number.

TrueTears · « **Reply #355 on:** December 09, 2009, 03:20:17 am »

Ah, yeah good strategy kamil.

So if the number is a multiple of 10 then it must have 5 amongst its prime factorization and the rest of the digits chosen must all be even.

We require the complement of this.

Let $A$ represent the set which contains no 5.

Let $B$ represent the set which contains even numbers.

Let $C$ represent the set which contains odd numbers.

The complement is $(A \cap B) \cup C$

$|(A \cap B) \cup C| = |(A \cap B)| + |C| - |\left((A \cap B) \cap C\right)| = 4^n + 5^n - 8^n$

The total number of ways is $9^n$

$\therefore Pr((A \cap B) \cup C) = \frac{4^n + 5^n - 8^n}{9^n}$

$\therefore$ probability required $= 1 - \frac{4^n + 5^n - 8^n}{9^n}$

But the answer is $1 - \frac{8^n+5^n-4^n}{9^n}$ . Where did I go wrong?

I'm confused to what the complement is now =.=

/0 · « **Reply #356 on:** December 09, 2009, 03:53:21 am »

So you want to find the number of ways to NOT pick 5 and and even number... hmm sounds like a good idea

You could do that by choosing $\boxed{1},\boxed{2},\boxed{3},\boxed{4},5,\boxed{6},\boxed{7},\boxed{8},\boxed{9}$ n times.
So there are $8^n$ ways of picking from those n times.

You could do that by choosing $\boxed{1},2,\boxed{3},4,\boxed{5},6,\boxed{7},8,\boxed{9}$ n times.
So there are $5^n$ of picking from those n times.

But there is an overlap between them, namely $\boxed{1},\boxed{3},\boxed{7},\boxed{9}$ .
There are $4^n$ ways of picking from those n times.

So there are $8^n+5^n-4^n$ ways of avoiding the deadly combination.

My reasoning's a bit shaky, but just going with my gut

Ahmad · « **Reply #357 on:** December 09, 2009, 01:21:50 pm »

In my opinion the best way to think about PIE is through indicator functions (sometimes called characteristic functions). In fact, once you've set up the very simple idea of indicator functions PIE is an immediate consequence, and there are lots of other useful consequences too.

So what's the idea of characteristic functions? Well suppose the set S contains all possible integer strings of length n output by the random generator. Then we define the function $H_2 : S \rightarrow \{0,1\}$ which intuitively represents "string does not contains an even number", and takes as input a possible integer string from the random number generator, and outputs the value 1 if "string does not contains an even number", and 0 otherwise. Notice that $\sum_{s \in S} H_2(s)$ counts the number of outcomes which don't contain an even number.

Similarly we can define $H_5 : S \rightarrow \{0,1\}$ which represents "string does not contain a 5". In particular I chose to define $H_2$ and $H_5$ this way because the number of outcomes which satisfies the property associated with each of these indicator function is easily counted.

The intriguing thing about these indicator functions is that they convert logical operations into standard algebra. For example, what if we wanted to find the characteristic function which represents "string contains an even number", well this is just NOT(H_2), which has the indicator function $1 - H_2$ . I'll leave you to verify the following,

$\neg H_2 \leftrightarrow (1 - H_2)$ where $x \leftrightarrow y$ means that x translates into characteristic function y. The funny symbol represents "not".

$H_2 \wedge H_5 \leftrightarrow H_2 \cdot H_5$ represents "and"

$H_2 \vee H_5 \leftrightarrow H_2 + H_5 - H_2\cdot H_5$ represents "or"

Now we want to find the number of strings with products a multiple of 10. How do we represent this in terms of $H_2$ and $H_5$ ? Well we want neither $H_2$ nor $H_5$ to occur, i.e. we want strings that contain an even number and a multiple of 5. Representing this in logical terms this is exactly $(\neg H_2) \wedge (\neg H_5)$ which using the above rules we can see has indicator function $(1-H_2)(1-H_5)$ . So to find the number of outcomes that have products that are multiples of 10 we simply sum over this indicator function, which is easily evaluated because we can expand out to get everything in terms of $H_2$ and $H_5$ which as I've previously mentioned have been chosen in particular because they're easily summed over!

$\sum_{s \in S} (1-H_2(s))(1-H_5(s)) = \sum_{s \in S} (1 - H_2(s) - H_5(s) + H_2(s)H_5(s))$

$= \sum_{s \in S} 1 - \sum_{s \in S} H_2(s) - \sum_{s \in S} H_5(s) + \sum_{s \in S} H_2(s)H_5(s)$

$= 9^n - 5^n - 8^n + 4^n$

Of course we simply divide by $9^n$ to get the desired probability. It might seem that this is overkill, but that's because I was showing the gory details, on paper I'd maybe write one or two lines, or just the last line. Also, the case I've presented this for is simple and you can just think it through and work it out like /0 did, but it's rather helpful for more complicated scenarios which it easily adapts to.

Notice that in this language PIE can be stated as follows: suppose $A_1, A_2, \ldots, A_n$ are indicator functions each associated with a property, and you want to count the number of outcomes not satisfying any of these properties, then,

$(\neg A_1) \wedge (\neg A_2) \wedge \cdots \wedge (\neg A_n) \rightarrow (1 - A_1)(1 - A_2)\cdots (1 - A_n) = 1 - (A_1 + A_2 + \cdots A_n) + (A_1 A_2 + \cdots) + \cdots + (-1)^n A_1\cdot A_2 \cdots A_n$

So it's essentially been reduced to algebra.

TrueTears · « **Reply #358 on:** December 09, 2009, 05:23:06 pm »

Ahmad you have inspired me to use indicator functions for the next question lol I think it worked out pretty well.

Quote

2. Let $a_1,a_2,...a_n$ be an ordered sequence of n distinct objects. A derangement of this sequence is a permutation that leaves no object in its original place. For example, if the original sequence is $1,2,3,4$ then $2,4,3,1$ is not a derangement, but $2,1,4,3$ is. Let $D_n$ denote the number of derangements of an $\mbox{n}$ -element sequence. Show that $D_n = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - ... + (-1)^n\frac{1}{n!}\right)$

Consider the specific case of just $4$ distinct objects.

Let $A$ represent the event where $a_1$ is in the same place.

Let $B$ represent the event where $a_2$ is in the same place.

Let $C$ represent the event where $a_3$ is in the same place.

Let $D$ represent the event where $a_4$ is in the same place.

What we require is the complement $\bar A \cap \bar B \cap \bar C \cap \bar D$

Let's define an indicator function namely $I_y(x)$ where $y \in \{A,B,C,D\}$ and $x \in \mathbb{U}$ where $\mathbb{U}$ is an universal set that contains all sets $\{A,B,C,D\}$

$I_y(x) = <br />\begin{cases} <br /> 0, & \mbox{if} \ \mbox{x} \ \notin \ \mbox{y} \\<br /> 1, & \mbox{if} \ \mbox{x} \ \in \ \mbox{y} <br />\end{cases}$

We require:

$I_{\bar A}(x) \wedge I_{\bar B}(x) \wedge I_{\bar C}(x) \wedge I_{\bar D}(x)$

Let's define a function:

$f(x) = (I_{\bar A}(x))(I_{\bar B}(x))(I_{\bar C}(x))(I_{\bar D}(x))$

$\implies f(x) = (1-I_A(x))(1-I_B(x))(1-I_C(x))(1-I_D(x)) = I_{\bar A \cap \bar B \cap \bar C \cap \bar D}(x)$

Let $F$ represent the cardinality of $f(x)$

$\therefore \sum_{x \in \mathbb{U}} f(x) = F$

$\implies F = \sum_{x \in \mathbb{U}} \left((1-I_A(x))(1-I_B(x))(1-I_C(x))(1-I_D(x))\right)$

$F = \sum_{x \in \mathbb{U}} 1 - \sum_{x \in \mathbb{U}} \left((I_{A}(x))+(I_{B}(x))+(I_{C}(x))+(I_{D}(x))\right) + \sum_{x \in \mathbb{U}} \left[(I_{A}(x))(I_{B}(x))+(I_{A}(x))(I_{C}(x)) + (I_{A}(x))(I_{D}(x)) + (I_{B}(x))(I_{C}(x)) +(I_{B}(x))(I_{D}(x)) +(I_{C}(x))(I_{D}(x))\right]$

$- \sum_{x \in \mathbb{U}} \left[(I_{A}(x))(I_{B}(x))(I_{C}(x))+(I_{A}(x))(I_{B}(x))(I_{D}(x))+(I_{B}(x))(I_{C}(x))(I_{D}(x)) + (I_{A}(x))(I_{C}(x))(I_{D}(x))\right] + \sum_{x \in \mathbb{U}} \left[(I_{A}(x))(I_{B}(x))(I_{C}(x))(I_{D}(x))\right]$

$F = 4! - 3!(4) + \binom{4}{2}2! - \binom{4}{3} + \binom{4}{4}$

$F = 4!-4! + \frac{4!}{2!2!}(2!) - \frac{4!}{3!1!} + \frac{4!}{4!0!}$

$F = 4!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!}\right)$

Which is exactly what we get if we sub in $n = 4$ .

Now we can generalise:

If there were $\mbox{n}$ distinct objects.

$a_1,a_2,a_3...a_n$

Let $A$ represent the event where $a_1$ is in the same place.

Let $B$ represent the event where $a_2$ is in the same place.

Let $C$ represent the event where $a_3$ is in the same place.

.
.
.

Let $N$ represent the event where $a_n$ is in the same place.

We require:

$I_{\bar A}(x) \wedge I_{\bar B}(x) \wedge I_{\bar C}(x) \wedge ... \wedge I_{\bar N}(x)$

$\implies F = \sum_{x \in \mathbb{U}} \left((1-I_A(x))(1-I_B(x))(1-I_C(x)) ... (1-I_N(x))\right)$

$F = \sum_{x \in \mathbb{U}} 1 - \sum_{x \in \mathbb{U}} \left((I_{A}(x))+(I_{B}(x))+(I_{C}(x))+...+(I_{N}(x))\right) + \sum_{x \in \mathbb{U}} \left[(I_{A}(x))(I_{B}(x))+(I_{A}(x))(I_{C}(x)) + ...+ (I_{A}(x))(I_{N}(x)) \cdots \right]$

$- \sum_{x \in \mathbb{U}} \left[(I_{A}(x))(I_{B}(x))(I_{C}(x))+...+(I_{A}(x))(I_{B}(x))(I_{D}(x))\right] + ... + (-1)^n \sum_{x \in \mathbb{U}} \left[(I_{A}(x))(I_{B}(x))(I_{C}(x))...(I_{D}(x))\right]$

$F = n! - (n-1)!(n) + \binom{n}{2}(n-2)! - \binom{n}{3}(n-3)! + ... + (-1)^n \binom{n}{n}$

$F = n!-n!+\frac{n!}{(n-2)!2!}(n-2)! - \frac{n!}{(n-3)!3!}(n-3)! + ... + (-1)^n\frac{n!}{n!0!}$

$F = n!\left(1-\frac{1}{1!}+\frac{1}{2!} - \frac{1}{3!} + ... + (-1)^n\frac{1}{n!}\right)$

$\mbox{Q.E.D}$

zzdfa · « **Reply #359 on:** December 09, 2009, 05:33:59 pm »

Note that the stuff in the brackets is the truncated expansion of $e^{-1}$ . So $\lim_{n\rightarrow \infty}D_n=\frac{n!}{e}$ . In fact $D_n =\left\lfloor \frac{n!}{e} \right\rfloor$ which i think is pretty neat

Search the forums now!

We have moved!

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

Ahmad

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

Ahmad

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

Ahmad

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

/0

Re: TT's Maths Thread

Ahmad

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

zzdfa

Re: TT's Maths Thread

Recent Posts

User:
Password: