Transcript for the Math Jam "Combinations" on Jul 18.

Math Jam hosted by markan (Sean Markan ).

markan (19:29:40)
Welcome to today's Combinations Math Jam!
Before we get started I would like to take a brief moment to explain
our virtual classroom to those who have not previously participated in
a Math Jam or one of our online classes.

markan (19:29:58)
As many of you know, this classroom is moderated, meaning that
participants can type into the classroom, but only the moderators can
choose a comment to share with everybody in the classroom. So,
everything you type will not appear in the classroom. This helps keep
the session organized and on track. Also, only moderators can enter
into private chats with other people in the classroom.

markan (19:30:08)
This means you should not hesitate to ask questions any time you have
them. We'll try to answer them either in the classroom or through a
private message to you.
By way of introduction, I'm Sean Markan, a new instructor at Art of
Problem Solving.

markan (19:30:18)
My assistant tonight is Beth Schaffer. Her username is Dandelion, and
she's here to help you if you have any questions. She attended the
Research Science Institute program in 2006 and was a Presidential
Scholar this year. This fall, she'll be a student at MIT.

markan (19:30:27)
I think Larry Evans, another new Art of Problem Solving staff member, may be
helping out as well.

markan (19:30:43)
Ok, here goes.

markan (19:30:54)
n this math jam we'll look at combinations. Combinations are related
to permutations, so we'll define them both, but mostly we're going to
focus on combinations.

markan (19:31:07)
Both permutations and combinations are used for counting the number of
ways of making some kind of choice.
For example, let's say there are 5 students and we want to give a gold
medal to one, a silver medal to another, and a bronze medal to a
third. How many different ways of distributing the medals are there?

kyin (19:31:20)
60

Quickster94 (19:31:23)
60

emant777 (19:31:25)
5x4x3

markan (19:31:37)
and why?

kyin (19:31:53)
5 students for gold 4 students for silver and 3 for bronze

Stargirl240 (19:31:53)
Because there are 5 choices for the gold medal, 4 for the silver, and 3 for the bronze

markan (19:32:02)
yes

markan (19:32:04)
Let's suppose we award the medals in that order. We have five choices
when deciding who to give the gold medal to. Then we'll have four
choices for the silver (it can't be the same student as the gold), and
three for the bronze.
All together we have $5 \cdot 4 \cdot 3 = 60$ options.

markan (19:32:15)


markan (19:32:24)
Notice that we only actually used two facts from the problem: there
were 5 students and 3 to select for different awards.
The answer would be the same if we had 5 boxes and wanted to know the
number of ways of writing 1, 2, and 3 in different boxes.

markan (19:32:31)
The common element in these problems is that we have 5 objects and
must choose 3 for different purposes.
Instead of saying ""for different purposes,"" we could also say that we
need to pick a sequence of 3 of the 5 objects. This is called a
permutation of 3 elements from a set of 5. The most important thing
to remember here is that picking the same 3 objects in different
orders counts as different permutations.

markan (19:32:46)
In general, we can ask for the number of permutations of r objects
from a set of n. Mathematicians have a symbol for this:

markan (19:32:53)


markan (19:32:57)
You can also write

markan (19:33:02)


markan (19:33:09)
Above we discovered that

markan (19:33:13)


markan (19:33:18)
Let's do one more. What is

markan (19:33:22)


ndem23 (19:33:38)
7*6*5*4

ytrewq (19:33:39)
7*6*5*4

shaggy75 (19:33:41)
7*6*5*4

catboy (19:33:42)
7x6x5x4

Ursa (19:33:47)
7x6x5x4=840

ma_va (19:33:47)
7*6*5*4

12markkram34 (19:33:47)
840

nuttynut (19:33:53)
840

Cecilerie (19:33:54)
840

markan (19:34:11)
hat does this mean?
It is the number of ways of choosing 4 objects out of 7 when order
matters.
We can calculate it as before: we have 7 choices for the first object,
6 for the second, 5 for the third, and so on.
Altogether,

markan (19:34:16)


markan (19:34:31)
What does the middle expression above remind you of?

emant777 (19:34:39)
n!

mathguy55 (19:34:39)
factorial

Cecilerie (19:34:39)
Factorials

markan (19:34:48)
It looks a lot like the expression for a factorial. Let's rewrite it:

markan (19:34:53)


markan (19:35:02)
Now both the numerator and denominator are factorials. We have

markan (19:35:10)


markan (19:35:15)


markan (19:35:24)
can someone do this?

12markkram34 (19:35:29)
The formula is N!/(N-R)!.

Currylover (19:35:32)
n!/(n-r)!

ytrewq (19:35:35)
n!/(r-1)!

mathguy55 (19:35:38)
n!/(n-r)!

markan (19:35:50)


markan (19:36:00)
those dots don't go on forever of course

markan (19:36:05)
We have r terms, so that's n-0 through n-(r-1).
; $P^n_r = n(n-1)(n-2) \dots (n-r+1)$

markan (19:36:12)
Now if we rewrite this as a fraction, we get

markan (19:36:15)


markan (19:36:20)


markan (19:36:40)
hat's the formula for permutations.

markan (19:36:45)
any questions?

markan (19:37:13)
Now we're ready to move on to combinations, which are very similar.

markan (19:37:42)
those of you who are asking when the class will end, it'll be around 90 minutes, give or take

markan (19:37:49)
Permutations tell us how many ways there are to choose some elements
from a set when the order in which we choose them matters.

markan (19:37:55)
Combinations tell us how many ways there are to choose some elements
from a set when the order does _not_ matter.

markan (19:38:00)
For example, the number of ways to choose 3 elements from a set of 5
is 10. If we call the elements A, B, C, D, and E, we can list the 10
ways:

markan (19:38:20)
what are they?

keiko_911 (19:38:29)
ABC

keiko_911 (19:38:42)
ABD

mathguy55 (19:38:45)
abd,abe

tcliao (19:38:47)
BCD

kyin (19:38:49)
ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE

markan (19:38:57)
ABC ABD
ABE ACD
ACE ADE
BCD BCE
BDE CDE

markan (19:39:12)
Mathematicians write the number of combinations of 3 elements out of 5
as

markan (19:39:15)


markan (19:39:20)
or alternatively

markan (19:39:26)


markan (19:39:33)
This is pronounced ""5 choose 3.""

markan (19:39:41)
So

markan (19:39:44)


markan (19:39:46)
whereas

markan (19:39:52)


markan (19:40:05)
There are a lot more ways to pick 3 elements out of a set when we
distinguish between different orderings of the elements.

markan (19:40:13)
In fact, in this case, they differ by an integer factor: 6.

markan (19:40:18)
Can anybody figure out why this is? Why is it P(5,3) 6 times more
than C(5,3)?

Quickster94_2 (19:40:20)
3!

kyin (19:40:36)
because when you order 3 terms there are 6 ways to order them

Quickster94_2 (19:40:38)
there are 3!, 6 ways to arrange the 3 items chosen

Stargirl240 (19:40:39)
Because 3!=6

markan (19:40:57)
hoosing a permutation is equivalent to choosing a combination, and
_then_ deciding the order of the elements. In this case, we have 10
ways to choose 3 of the 5 elements (without deciding the order), and
then 6 ways to arrange the objects. So there are 6 times more
permutations than combinations.

markan (19:41:02)
*choosing

markan (19:41:34)
Now, can someone generalize this relationship to figure out the
general connection between $P^n_k$ and ${n \choose k}$ ?

markan (19:41:47)


Currylover (19:42:03)
n!/(n-k)k!

emant777 (19:42:03)
P = C (n!) ?

Quickster94_2 (19:42:05)
they differ by a factor of k!

minicon (19:42:05)
k!

markan (19:42:31)


markan (19:42:36)
The number of ways to pick $k$ elements when order matters is just the
number of ways of picking $k$ elements _without_ an order, times the
number of ways of choosing an order.

markan (19:42:41)
In general, how many ways are there to put $k$ objects in order?
k!

markan (19:42:51)
Therefore,

markan (19:42:54)


markan (19:42:59)
We can use this equation to get a formula for C(n,k), based on the one for P(n,k):

markan (19:43:02)


markan (19:43:12)
So for example,

markan (19:43:15)


markan (19:43:22)
Any questions?

markan (19:44:06)
there was a question about n and k

markan (19:44:11)
n and k are just any two numbers we want them to be

markan (19:44:39)
so that expression above for n choose k is the number of ways of choosing k elements from a set of n, when order doesn't matter

markan (19:44:44)
n and k can be anything

12markkram34 (19:44:36)
N is total number of choices and K is number of choices you are going to choose

markan (19:44:57)
Alright, for practice, let's compute a few combinations. I'll put
them up and pass along the first couple correct answers for each. No
calculators allowed!
What is:

markan (19:45:12)
oh, but first :

Currylover (19:44:55)
The formula doesn't work if k is greater than n, right?

Quickster94_2 (19:44:59)
but k has to be less then or equal to n

markan (19:45:43)
yes, k can't be more than n, because then you end up trying to take the factorial of a negative number

markan (19:45:55)
however

markan (19:46:05)
well, let's just do the practice :)

markan (19:46:16)
What is:

markan (19:46:19)


mihail911 (19:46:23)
45

markan (19:46:31)
This is

markan (19:46:39)


markan (19:46:44)
How about

markan (19:46:49)


emant777 (19:46:58)
30

mz94 (19:47:03)
180

mathguy55 (19:47:03)
210

kyin (19:47:07)
1260

markan (19:47:18)
some disagreement i see!

tcliao (19:47:13)
5040

ngade (19:47:25)
45

markan (19:47:38)
one of those 6 is right :)

markan (19:47:54)
we want 10! / 6! / 4!

markan (19:47:57)


markan (19:48:20)
how about 17 choose 3

mathguy55 (19:48:28)
680

kyin (19:48:38)
680

Stargirl240 (19:48:38)
680

mz94 (19:48:38)
680

markan (19:48:48)
yep

markan (19:48:53)
ok, how about 17 choose 14?

Stargirl240 (19:49:01)
680

Currylover (19:49:01)
680

Lawrence Wu (19:49:02)
same

kyin (19:49:03)
680

markan (19:49:13)
Hmmm....that's interesting, C(17,14) = C(17,3)

markan (19:49:19)
Can anyone see why?

kyin (19:49:29)
because both are 17!/3!17!

alexluh (19:49:31)
17-14=3, 17-3=14

mihail911 (19:49:31)
14+3=`17...

Currylover (19:49:40)
choosing 3 out of 17 is like not choosing 14 out of 17

shaggy75 (19:49:42)
same denominator

markan (19:49:49)
good

markan (19:49:52)
two ways to see it:

markan (19:50:00)
one way is that in the formula, you end up with the same denominator either way

markan (19:50:02)
another way is that

markan (19:50:13)
The number of ways of picking 14 elements out of a group of 17 is the
same as the number of ways of picking 3 _not_ to include in the 14.

markan (19:50:15)
In general, C(n,k) = C(n,n-k).

markan (19:50:23)
ok, just a couple more

markan (19:50:33)


alexluh (19:50:38)
1

mihail911 (19:50:38)
1

kyin (19:50:38)
1

Stargirl240 (19:50:39)
1

ytrewq (19:50:39)
1

mathguy55 (19:50:39)
1

markan (19:50:49)


emant777 (19:50:52)
1

mihail911 (19:50:54)
1

Stargirl240 (19:50:54)
1

mathguy55 (19:50:55)
1

tennis4life (19:50:55)
1

acerlendss (19:50:56)
1

Currylover (19:50:57)
1

asdfxz (19:50:58)
0.0

Lawrence Wu (19:50:58)
infinite

alexluh (19:50:59)
0

markan (19:51:10)
this is 1 too

markan (19:51:17)
remember, n choose k is the same as n choose n-k

markan (19:51:23)
so 1000 choose 1000 is the same as 1000 choose 0

markan (19:51:36)
alternatively, you can think that the number of ways to pick nothing is exactly one: you pick nothing

mathguy55 (19:51:13)
only one way to pick none of them

emant777 (19:51:21)
1 way to not choose.

Currylover (19:51:28)
there's 1 way to choose none out of 1000

alexluh (19:51:30)
oh, ther is one way to coose nothing, right?

12markkram34 (19:51:32)
Because there is 1 way to choose 0 things, do nothing!

markan (19:51:49)
last but not least:

markan (19:51:52)


kyin (19:51:57)
0

Stargirl240 (19:51:57)
0

mz94 (19:51:58)
0

keiko_911 (19:51:58)
0

mihail911 (19:51:59)
not possible

Currylover (19:52:00)
0

ytrewq (19:52:00)
iimposible

Quickster94_2 (19:52:02)
undefined

mathguy55 (19:52:03)
undefined

tennis4life (19:52:03)
0

Lawrence Wu (19:52:04)
impossible

12markkram34 (19:52:04)
Undefined

markan (19:52:16)
usually it actually is considered to be defined

markan (19:52:18)
it's just 0

markan (19:52:29)
because there's no way to pick 1001 elements if you only have 1000

markan (19:52:34)
and likewise, 1000 choose -1 is also 0

markan (19:52:47)
alright, time for probems!

markan (19:52:58)


12markkram34 (19:52:57)
I have a question... How did ppl get the C(17,3) answer so fast?

Quickster94_2 (19:53:05)
45

Stargirl240 (19:53:06)
45

markan (19:53:27)
those of you who don't already know the answer, any ideas how to do this?

mz94 (19:53:41)
9+8+7+6+5+4+3+2+1=45

markan (19:53:51)
mz94 has one good idea

markan (19:54:04)
9 ways for the first guy to shake hands with the others

markan (19:54:09)
then 8 for the second guy to shake hands with the remaining ones

markan (19:54:12)
and so on down the line

markan (19:54:23)
but it turns out that we can use combinations to go faster

markan (19:54:31)
We want the number of ways to choose two people to have a handshake,
because that will be the number of handshakes that need to occur.

markan (19:54:39)
So we're choosing 2 out of 10, which is C(10,2), which is 45, as we
figured out above.

algebra3000 (19:54:41)
i still can't see my text when i enter it in.

shaggy75 (19:54:47)
how do people figure out those practice combinations so fast?

markan (19:55:26)
algebra3000: the classroom is moderated, so you enter text, and then the instructor passes it along if he/she chooses

markan (19:55:34)
i'm not sure how people go so fast :)

markan (19:55:56)
anybody want to explain?

mathguy55 (19:55:38)
i've seem problems like them before

ngade (19:56:11)
i am using pen and paper

emant777 (19:56:14)
you can cancel factorials

markan (19:56:26)
ok, next problem

markan (19:56:32)


kyin (19:56:46)
56

mz94 (19:56:48)
c(8,3)=40

alexluh (19:56:52)
56

RollandWu (19:56:53)
56

markan (19:57:11)
each triangle can be made by just picking 3 vertices of the cube to use\

markan (19:57:17)
since there are 8 vertices, it's 8 choose 3, or 56

markan (19:57:28)
alright, now we'll start getting into tougher problems

markan (19:57:33)
This one is based on a Mathcounts problem:

markan (19:57:40)


markan (19:57:45)
How can we use combinations here?

mz94 (19:58:04)
c(6,2)+c(6,2)?

markan (19:58:27)
good start

shaggy75 (19:58:20)
C(6,2)*2

Ursa (19:58:24)
C(6,4) boys, and C(6,4) girls?

markan (19:58:38)
lots of good ideas, but nobody's nailed it yet

markan (19:58:46)
Imagine finding one way to assign students to committees.
What do we have to choose?

shaggy75 (19:58:57)
students

markan (19:59:06)
more specifically?

Elizabeth Cole (19:59:13)
2 boys, 2 girls

mathguy55 (19:59:18)
2 boys and 2 girls

mz94 (19:59:21)
boys & girls?

markan (19:59:41)
that's half of it

markan (19:59:43)
read the problem carefully :)

12markkram34 (19:59:47)
2 boys and girls for each committe

markan (20:00:01)
yes, so really we need 4 girls and 4 boys

markan (20:00:08)
We have to choose:
(A) 2 boys for committee A
(B) 2 girls for committee A
(C) 2 boys for committee B
(D) 2 girls for committee B

markan (20:00:19)
Each of these things can be figured out using combinations.

markan (20:00:27)
What's (A)?

RollandWu (20:00:32)
15

Lawrence Wu (20:00:33)
15

12markkram34 (20:00:37)
So is it C(6,2) x C(4,2) x 2?

acerlendss (20:00:39)
C(6,2)

Currylover (20:00:40)
C(6,2)

Cecilerie (20:00:41)
6 choose 2

markan (20:00:51)
We have to choose 2 of the 6 boys. This is C(6,2), or 15.

markan (20:00:56)
Likewise, there are 15 ways to choose 2 girls for A.
Now how many choices are there for boys on committee B?

rachelinia (20:01:08)
15, same thing

markan (20:01:20)
remember, nobody can serve on two committees

Currylover (20:01:09)
C(4,2) which is 6

mathguy55 (20:01:13)
4 choose 2 = 6

alexluh (20:01:19)
4 choose 2=6

markan (20:01:42)
after we assign two boys for committee A, we only have 4 left over to assign to committee B

markan (20:01:46)
so we have to pick 2 of those 4

markan (20:01:48)
which we can do in 6 ways

markan (20:01:57)
Same for the girls.

markan (20:02:03)
So altogether, the answer is what?

ndem23 (20:02:15)
21

Lawrence Wu (20:02:15)
810

mihail911 (20:02:16)
42

mz94 (20:02:18)
60

mathguy55 (20:02:20)
42

catboy (20:02:20)
42

tcliao (20:02:22)
42

kyin (20:02:24)
225+36=261

shaggy75 (20:02:26)
12

alexluh (20:02:27)
42

markan (20:02:42)
lots of ideas.....

markan (20:02:47)
but not quite there

markan (20:02:53)
let's review for a second

markan (20:03:24)
we wanted to choose 2 boys for A, which we could do in 15 ways

markan (20:03:37)
multiply that by 15 because we then choose 2 girls for A

markan (20:03:54)
then we have 6 ways to pick 2 girls for A

markan (20:04:02)
and 6 ways to pick 2 girls for B

markan (20:04:07)
altogether, we multiply all these up

Currylover (20:02:55)
15 x 15 x 6 x 6 = 8100

markan (20:04:21)
15 * 15 * 6 * 6 = 8100

markan (20:04:23)
is the answer

markan (20:04:34)
many of you are inclined to add things

markan (20:04:48)
but when we make one choice and then another, we want to multiply

Elizabeth Cole (20:04:34)
wow

acerlendss (20:04:36)
Why multiply?

12markkram34 (20:04:44)
That is ingenious

alexluh (20:04:49)
[img id=em-3]why, multiply

markan (20:05:17)
for example, if i have 3 choices for lunch and 3 for dinner, then there are 9 possible combinations of meals i could have

markan (20:05:20)
not 6

markan (20:05:41)
any questions before the next problem?

markan (20:06:13)
http://www.artofproblemsolving.com/Forum/latexrender/pictures/3/b/f/3bff02b6ca6f1ffaf4071a6de25e8f0fd904d4aa.png

markan (20:06:21)


markan (20:06:36)


markan (20:06:38)
ideas?

markan (20:06:56)
the class will probably end somewhere in the 5:30-6 range, for those of you who are asking

12markkram34 (20:06:55)
Start drawing?

shaggy75 (20:06:59)
calcute area of grid

emant777 (20:07:02)
each time we have to choose between two.

Moo (20:07:10)
you always have to go 10 right and 10 up to get from a to b

CCrystal (20:07:12)
could you send the image again? i am late

markan (20:07:36)
http://www.artofproblemsolving.com/Forum/latexrender/pictures/3/b/f/3bff02b6ca6f1ffaf4071a6de25e8f0fd904d4aa.png

RollandWu (20:07:20)
count them using pascal's triangle

mihail911 (20:07:22)
there's two ways along the sides

markan (20:07:54)
lots of good ideas

markan (20:08:00)
Moo had a good starting observation

markan (20:08:21)
which is that to get there in 20 steps, we have to be walking up or right all the time

alexluh (20:08:07)
how many different combinations at each point you reach

mihail911 (20:08:13)
i agree...u have to do 10 up and 10 right

sbanerjee (20:08:15)
you can also go up, then right

firelight (20:08:17)
well. we must go up 10 times and right 10 times. so we permute uuuuuuuuuurrrrrrrrr which is 20 choose 10.

markan (20:08:56)
somebody mentioned pascal's triangle, which we'll get to in a bit

markan (20:09:17)
but what i think they were getting at is that we could label each point with the number of ways to get there, assuming we only ever go up or right

markan (20:09:33)
so we label A with one, since we start there

markan (20:09:41)
and then we label the points to the right and top of it with one

markan (20:09:55)
but then the point 1 block north and 1 block east of A gets 2, because we have two routes to get there

markan (20:10:03)
in other words, we sum the ways to get to the points below and left of it

markan (20:10:22)
this could be continued until we filled in the whole grid, and then we'd be done

mihail911 (20:10:21)
i learned that method, but is there a faster way?

markan (20:10:35)
good question, yes there is

markan (20:10:48)
and by the way, i know many of you already know this method, so just sit tight for a minute :)

markan (20:11:04)
Notice that to have a path length of 20 we'll have to move in steps of
1, always up or right (north or east). So let's break our path down
into 1-step chunks, and write N for steps north and E for steps east.
Now any possible path will consist of a string of 20 letters, 10 being
N and 10 being E. And any string of 10 N's and 10 E's will correspond
to a different path.

markan (20:11:20)
So to count the number of paths, we just need to count the number of
strings with 10 E's and 10 N's.

markan (20:11:33)
how can we count those strings?

mihail911 (20:11:41)
combinations?

markan (20:11:49)
yep

kyin (20:11:52)
20!/10!10!

mihail911 (20:12:02)
n=total number of E's and N's

shaggy75 (20:12:06)
20 choose ten

markan (20:12:13)
why?

markan (20:12:19)
(i mean, why 20 choose 10?)

Currylover (20:12:32)
choose 10 for N and 10 for E

markan (20:12:40)
good

markan (20:12:43)
We need to choose 10 positions for E in a string of 20, so this is 20
choose 10.

markan (20:12:51)
what does that come out to?

12markkram34 (20:12:47)
Because 20 possible choices, but 10 have to be N or E. And if it's not n, then it's e

markan (20:13:01)
(if anybody wants to show off) :)

markan (20:13:25)
guess not

markan (20:13:27)
it comes out to:

markan (20:13:30)


12markkram34 (20:13:32)
184756, using calc

markan (20:13:49)
ok, any questions on this before we go to the third dimension?

Cecilerie (20:13:44)
*boggle*

markan (20:14:12)
Let's do a slight extension: suppose the grid were actually
three-dimensional, and we had to go 10 blocks out of the screen as
well as going 10 blocks north and 10 blocks east. How many paths of
length 30 would there be?
Ideas?

Lawrence Wu (20:13:55)
would this be a target round question?

markan (20:14:31)
yes, it could be a target round question

kyin (20:14:31)
30!/10!10!10!

alexluh (20:14:32)
30!/10!/10!

mihail911 (20:14:36)
30 choose 10

emant777 (20:14:39)
30 choose 10 ?

markan (20:15:16)
many of you are jumping to conclusions :)

markan (20:15:26)
can somebody explain their thinking a bit?

12markkram34 (20:15:41)
30 choose 20? Because you must choose N, E, or Up at each point.

markan (20:16:01)
hm....not sure i see the connection there

Currylover (20:15:56)
even if you choose 10 out of the 30, you have 20 more that you need to split in half

mihail911 (20:16:00)
well....the path is 30 long and there's 10 N, E, or up

kyin (20:16:03)
Choose 10 out of 30 for each direction and then multiply?

markan (20:16:24)
currylover has a good idea

Quickster94_2 (20:16:21)
(30,10) chooses one direction, and then (20,10) chooses the other 2

markan (20:16:38)
let's think of it this way

markan (20:16:51)
we can still use strings of letters that give ""directions""

markan (20:16:56)
They would be strings consisting of three possible letters, N for
north, E for east, and X for out of the screen. Strings would have 30
letters, 10 of each.

markan (20:17:12)
How many such strings are there?

emant777 (20:17:18)
30!/10!/10!/10! ?

markan (20:17:30)
emant777, how did you get that?

emant777 (20:17:39)
because the letters repeat

Currylover (20:17:49)
C(30,10) X C(20,10)?

markan (20:18:02)
so it looks like there are two approaches being used here

markan (20:18:07)
let me talk about each of them

markan (20:18:10)
first is emant's expression

markan (20:18:23)
if we start off with 30 letters, there are 30! ways to arrange them

markan (20:18:31)
but we have to worry about the fact that certain arrangements will look the same

markan (20:18:39)
because we can't distinguish between one E and another E

markan (20:18:55)
therefore, 30! will overcount a lot

markan (20:19:21)
for any permutation of the 30 letters, we can get another 10! that look the same, just by moving the E's around

markan (20:19:29)
so if we want to count the ones that look different, we should divide by 10!

markan (20:19:34)
and the same thing goes for N and for X

markan (20:19:42)
so all together, we'll have to divide by (10!)^3

markan (20:20:00)
we get

mihail911 (20:19:00)
30!/10!10!10!

markan (20:20:22)
and one other approach to counting the strings:

mihail911 (20:20:13)
ohh....now the other one makes sense too!...genius!

markan (20:20:27)
Well, first we can choose where to put the N's, which is 30 choose 10.
Then we could choose where to put the E's in the leftover spaces,
which is 20 choose 10.

markan (20:20:35)
So the answer is
; ${30 \choose 10}{20 \choose 10}$

markan (20:20:48)
notice, this latter expression is:

markan (20:20:59)
30! / 20! / 10! * 20! / 10! / 10!

markan (20:21:04)
which works out to 30! / 10! / 10! / 10!

markan (20:21:07)
so the two approaches give the same answer

markan (20:21:28)
actually, i didn't work out the numerical answer :)

algebra3000_2 (20:21:17)
but what is the answer?

markan (20:21:34)
anybody want to do it and tell us?

markan (20:21:44)
meanwhile, here's our next problem:

markan (20:21:47)
How many different 5-card poker hands are three-of-a-kinds?
(In other words, how many ways can we choose 5 cards from a standard
deck so that three have the same rank (ace, king, jack, five, etc.),
and the other two have different ranks?)
There are many ways to solve this. What's one?

markan (20:22:05)
What decisions do we have to make when creating a hand that is a
three-of-a-kind?

shaggy75 (20:22:08)
5 choose 3

shaggy75 (20:22:13)
combinations

kyin (20:22:18)
if the two other cards are same or different

markan (20:22:29)
we're going to require that the other two be different

markan (20:22:55)
same ranks means that all three are queens, or all three are jacks, or all three are 5's, etc.

catboy (20:22:40)
there are only 4 of the same card in each deck

mathguy55 (20:23:06)
there are 52 cards in a deck and 13 cards in each suit.

mihail911 (20:23:26)
wouldn't it be 52!/(3!)^13

mz94 (20:23:29)
there are 4 ncr 3 types of 3 of a kinds

acerlendss (20:23:43)
3721624570390534359552000 is the answer to the previous question (I think)

markan (20:23:57)
thanks :)

Currylover (20:23:50)
C(5,2) X 4 X 13

markan (20:24:10)
lots of people are giving me expressions, but can someone give us a strategy for counting the hands?

Quickster94_2 (20:24:14)
there are 13 cards, so thirteen possibilities for the 3 of a kind, and then C(49,2)-12 for the possibilities that have them equal, that gives 15,132

sbanerjee (20:24:47)
I got 5550996791340 as the answer to the last one...

markan (20:24:55)
let's start with quickster's approach here

markan (20:25:06)
sounds like he wants to pick what the rank of the three of a kind is going to be

markan (20:25:13)
so there are 13 options for that

catboy (20:25:32)
and any three of four cards will do

markan (20:25:58)
ok, so that gives us 4 choose 3, or 4, options for the suits of the triplet

markan (20:26:06)
so altogether, we've got 13 * 4 possibilities for the triplet

markan (20:26:13)
now what?

Elizabeth Cole (20:26:33)
two other cards have to be different...

kyin (20:26:26)
find the choices for the other 2 cards

emant777 (20:26:36)
how do you choose the triplet again?

catboy (20:26:37)
the other two cards must be different

algebra3000_2 (20:26:38)
we find the possibilities for the other two cards

Currylover (20:26:39)
52 X C(5,2)

markan (20:27:03)
so for the other two cards:

markan (20:27:11)
we've got 12 suits left after we do the triplet

markan (20:27:16)
and we're going to have to choose 2 of them

markan (20:27:23)
so that's 12 choose 2

mz94 (20:27:39)
do we count full houses?

markan (20:27:51)
no full houses

markan (20:28:16)
oops, sorry, i guess the question was a little unclear

markan (20:28:19)
let's say no full houses

markan (20:28:57)
so we've got 52 options for the triplet, 12 choose 2 for the other two, and finally we just have to pick the ranks of the other two

markan (20:29:58)
oops, sorry, i just realized what happened

markan (20:30:47)
ok

markan (20:30:57)
i think we're good so far

markan (20:31:12)
so we just need to pick the last two suits

markan (20:31:17)
and we've got 16 options for that

markan (20:31:37)
so overall, we had 52 options for the triplet

markan (20:31:49)
times 12 choose 2 = 66 options for the other ranks

markan (20:31:54)
times 16 options for the other suits

markan (20:31:59)
which is what?

alexluh (20:32:03)
52*66*16

algebra3000_2 (20:32:19)
1056?

mz94 (20:32:20)
1056

mathguy55 (20:32:20)
55968

Lawrence Wu (20:32:21)
41184

algebra3000_2 (20:32:26)
wait

kyin (20:32:29)
1056*52

Quickster94_2 (20:32:33)
ARRRGGGHH I've messed this problem up so much!!!

mathguy55 (20:32:40)
54912

Lawrence Wu (20:32:45)
41184

Lawrence Wu (20:32:48)
41184\

markan (20:33:07)
ahhh!

markan (20:33:09)
so many different answers :)

markan (20:33:14)
but i think it's 54912

alexluh (20:33:18)
52*66*16=54912

Elizabeth Cole (20:33:24)
54,912?

markan (20:33:37)
so are we on the same page now?

markan (20:33:52)
these poker problems are always tricky

algebra3000_2 (20:33:46)
so mathguy's correct?[img id=em-3]

alexluh (20:33:51)
yes, we are in the same boat

catboy (20:34:05)
my boat sunk

markan (20:34:20)
ok, let's move on to the next problem

markan (20:34:30)
i'm sure it'll be good to go over these again in your free time :)

markan (20:34:40)
the next problem involves a trick, but not nearly as much computation!

markan (20:34:45)
Suppose we have 10 different boxes. How many ways are there to
distribute 20 identical donuts among them?
Any ideas?

tennis4life (20:34:56)
can you post the transcript please?

markan (20:35:13)
yes, there will be a transcript

sbanerjee (20:35:10)
can boxes be empty?

mihail911 (20:35:17)
pigeonhole principle doesn't apply to this kind of problem right?

kyin (20:35:18)
find how many groups of 10 numbers add upt o 20

mathguy55 (20:35:19)
so the probability of getting a 3 of a kind if you are delt five cards is 54912/ C(52,5)?

Lawrence Wu (20:35:24)
we have 10 right off the bat

markan (20:35:38)
sbanerjee: yes, they can be empty

markan (20:35:46)
mihail: no, pigeonhole doesn't really apply

markan (20:35:58)
kyin: good idea

markan (20:36:06)
mathguy: yes, that's right

markan (20:36:31)
Let's try a small case.
; Suppose it's it's 6 boxes and 1 donut.

Currylover (20:36:29)
are the boxes identical or completely different?

Lawrence Wu (20:36:37)
6

markan (20:36:49)
currylover: completely different

shaggy75 (20:36:44)
6

catboy (20:36:44)
6

ytrewq (20:36:47)
6 ways

shaggy75 (20:36:49)
6 ways

markan (20:36:56)
excellent!

markan (20:37:01)
ok, how about 5 boxes and 2 donuts?

shaggy75 (20:37:07)
10

shaggy75 (20:37:09)
10 ways

Currylover (20:37:17)
10?

catboy (20:37:17)
10

ytrewq (20:37:19)
15

markan (20:37:34)
a bit of disagreement here :)

markan (20:37:39)
certainly we have 10 options if we put them in different boxes

markan (20:37:44)
because that's 5 choose 2

markan (20:37:49)
but we could put them in the same box, which gives us another 5

markan (20:37:52)
so the answer is 15

markan (20:38:07)


tennis4life (20:38:18)
16

shaggy75 (20:38:20)
16?

shaggy75 (20:38:22)
12?

markan (20:38:35)
not quite :)

sbanerjee (20:38:39)
12+4 is 16...

alexluh (20:39:28)
4 chooose 3 is 4

markan (20:39:49)
yeah, so that's the number of ways if we put them all in different boxes

markan (20:39:56)
so it'll be 4 + something

markan (20:40:13)
what if we put 2 in one box, and 1 in another box?

markan (20:40:16)
how many ways could we do that?

markan (20:40:38)
i guess that's where you guys got the 12, right?

Lawrence Wu (20:40:19)
12

markan (20:40:50)
because you have 4 choices which box to put 2 in, and then 3 choices which box to put the other one in

markan (20:40:55)
so we've got 16 so far

markan (20:40:58)
but what have we left out?

Quickster94_2 (20:40:52)
plus, another 4 for all in same box

Lawrence Wu (20:40:47)
20

Currylover (20:40:53)
20?!?!

markan (20:41:10)
yeah

markan (20:41:18)
4 + 12 + 4 = 20

markan (20:41:33)
ok, does anyone notice anything about these numbers?

jama1 (20:41:40)
is there a quicker way to approach this problem?

markan (20:41:50)
jama: yes, there is

markan (20:41:55)
we're going to discover it :)

markan (20:42:07)
ah, i meant the numbers 6, 15, and 20

markan (20:42:15)
1 donut in 6 boxes = 6 ways

markan (20:42:20)
2 donuts in 5 boxes = 15 ways

markan (20:42:22)
3 donuts in 4 boxes = 20 ways

alexluh (20:42:06)
pascals triangle

mz94 (20:42:18)
combos

Currylover (20:42:23)
pascal's triangle?

markan (20:42:33)
good!

markan (20:42:38)
what combinations are these?

markan (20:43:00)
in other words, 20 is what choose what?

Currylover (20:43:10)
C(6,1) C(6,2) C(6,3)?

Quickster94_2 (20:43:19)
6 choose 3

mihail911 (20:43:29)
6 chose 4

Currylover (20:43:35)
C(6,1)=1

mihail911 (20:43:39)
or 6 choose 2

markan (20:43:47)
We've got C(6,1) = 6, C(6,2) = 15, and C(6,3) = 20.

markan (20:43:57)
Anyone want to guess what the pattern is in general?

markan (20:44:07)
in other words, if we have B boxes and D donuts....

markan (20:44:15)
how many arrangements?

sbanerjee (20:44:24)
it would be C(B,D)

shan_ying80@yahoo.com_2 (20:44:27)
B choose D?

markan (20:44:42)
close

algebra3000_2 (20:44:35)
C(6, D)

algebra3000_2 (20:45:02)
C(6, D)???

Quickster94_2 (20:44:29)
for n donuts and k boxes, it is C(n+k-1,k-1)

Lawrence Wu (20:45:06)
B+D-1 choose D?

markan (20:45:20)
yes, that's right

markan (20:45:22)
now let's see why

markan (20:45:34)
For this problem, we'll use a trick that is conceptually similar to
the trick we used for the grid problem. For that, we wrote each
possible option as a string of characters. This time we'll find a way
to write each possible arrangement as a string of items.
Any ideas what items to use?

markan (20:46:18)
to clarify:

markan (20:46:21)
if there are B boxes and D donuts, the number of arrangements is
C(B+D-1,D).

Lawrence Wu (20:46:07)
the donuts?

kuitang (20:46:30)
letters for boxes, numbers for donuts

markan (20:46:45)
good ideas

markan (20:46:57)
Here's a clever trick.
Imagine putting all 20 donuts in a row, left to right.
Then, take 9 separators, and place each one somewhere in the row. It
could be between two donuts, between two separators, all the way on
the right, etc. Any position is fine.

markan (20:47:14)
(we're going back to the 20 donuts rather than the small numbers)

markan (20:47:19)
Now imagine that we fill our ten boxes as follows: put all the donuts
before the first separator in the first box, all the donuts between
the first and second separators in the second box, and so on up to the
tenth box.

markan (20:47:31)
This process gives us a way to distribute donuts based on an
arrangement of donuts and separators. Every possible way of
distributing donuts corresponds to some arrangement of separators, and
every arrangement of separators gives a different distribution of
donuts.

markan (20:47:39)
This means that to count the number of possible distributions of
donuts, we just need to count how many ways there are to arrange 9
separators and 20 donuts in a row.

markan (20:47:44)
How can we do this with combinations?

kuitang (20:47:58)
c(29,9)

markan (20:48:08)
yep

markan (20:48:10)
we've got 29 objects

markan (20:48:15)
We have to choose 9 of them to be separators, and the order doesn't
matter because all the separators are the same.

markan (20:48:22)
So the number of possibilities is 29 choose 9.

markan (20:48:29)
Therefore, the number of ways of arranging 20 identical donuts in 10
different boxes is

markan (20:48:32)


markan (20:48:46)
btw, yes, we'll end around 9 EST

markan (20:48:58)
any questions?

markan (20:49:02)
we have one last topic after this

Lawrence Wu (20:48:59)
nooooooooooooooooooooooooooooooooooooo

Lawrence Wu (20:49:13)
yesssssssssssssssssssssssssssssssssssssssssssssssss

minicon (20:49:26)
will there be a transcript?

markan (20:49:35)
yes, there will be a transcrip

markan (20:49:40)
Ok, one last topic.

markan (20:49:47)
Most of you have probably seen Pascal's triangle. If you haven't:
http://www.learner.org/channel/workshops/math/images/pascal.gif

markan (20:49:54)
Each number is the sum of the two above it.

markan (20:49:59)
Our goal is going to be to find a formula for the k'th entry in the
n'th row of Pascal's triangle.

markan (20:50:04)
To simplify things, we're going to use the convention that the top row
is numbered 0, and the first entry in each row is numbered 0. Let

levans (20:50:04)
or the wiki here on the AoPS site

markan (20:50:49)


markan (20:50:54)
e the j'th entry in the i'th row.

markan (20:50:59)
http://www.learner.org/channel/workshops/math/images/pascal.gif

markan (20:51:01)
So to make sure we're all on the same page, what is

markan (20:51:06)


shan_ying80@yahoo.com_2 (20:51:17)
1

ytrewq (20:51:20)
1

markan (20:51:30)
yep

markan (20:51:37)
0th row, 0th entry is the tip of the triangle, 1

markan (20:51:47)
what is

markan (20:51:52)


markan (20:52:06)
remember the convention i'm using:

markan (20:52:13)
To simplify things, we're going to use the convention that the top row
is numbered 0, and the first entry in each row is numbered 0. Let

markan (20:52:18)


kyin (20:52:25)
6

markan (20:52:43)
good

emant777 (20:52:49)
5th row, 3rd from left = 6

markan (20:53:05)


markan (20:53:07)
what's that?

jama1 (20:53:13)
0?

algebra3000_2 (20:53:16)
0

sbanerjee (20:53:25)
there is no 9th entry?

ytrewq (20:53:30)
imposible

markan (20:53:44)
Trick question. Any entry falling left or right of the table is
considered 0.
In general, if i is at least 1, we have the recursion

markan (20:53:51)


markan (20:54:03)
Alright, suppose we want to understand where one of the entries in the
triangle comes from. Let's say we want to know why

markan (20:54:10)


markan (20:54:24)
any thoughts?

shaggy75 (20:54:33)
4+_2=6?

Quickster94_2 (20:54:34)
c(4,2)

shaggy75 (20:54:38)
4+2=6?

sbanerjee (20:54:41)
maybe a coincidence, but the two subscripts add up to 6

markan (20:54:58)
it's a good observation that they sum up to 6, but sadly a coincidence :)

Currylover (20:54:47)
C(4,2)=6

markan (20:55:12)
a couple of you also noticed that 4 choose 2 is 6

markan (20:55:19)
which is not a coincidence :)

markan (20:55:32)
let's try to see why this works

markan (20:55:39)
there are actually a lot of ways of explaining this

markan (20:55:44)
i'm going to go with just one, which is kind of unusual

markan (20:55:53)
let's just try rewriting T_42 using our recursion

markan (20:56:00)


markan (20:56:04)


markan (20:56:06)


markan (20:56:09)


markan (20:56:13)


markan (20:56:15)


markan (20:56:24)
i'll let you process that for a second :)

markan (20:57:00)
So you see that our sum eventually reduces to a bunch of 1's, all
coming from

Quickster94_2 (20:56:12)
what exactly is a recursion?

markan (20:57:18)


markan (20:57:29)
And this would happen for any entry, not just 6.

markan (20:57:33)
In fact, if you look at where each of our 1's is coming from, you can
find a sequence of terms that gave rise to it.

mz94 (20:55:49)
pascals triangle is made of combanotorics, isnt it?

emant777 (20:57:38)
how does 22 go to 10 ?

jama1 (20:57:44)
i think im getting the hang of this[img id=em-3]

levans (20:58:20)
A recursion can be thought of as something that requires a previous calculation.

markan (20:58:24)
emant: good point, i think i meant to write T_11

markan (20:58:38)
which will go to T_00 on the next step, so it's still 1

markan (20:59:04)
in any case, let's look at the sequences that tell us where terms come from

markan (20:59:13)
For example, the third 1 in the final expression came from T_00, which
came from T_11, which came from T_21, which came from T_31, which came
from T_42.

markan (20:59:31)


markan (20:59:48)
If you imagine following this sequence in the triangle, you'll see
that you're going from the top of the triangle down to 6, always
moving southeast or southwest.

markan (21:00:01)
With a little thinking you can convince yourself that the possible
paths from 1 to 6 in Pascal's triangle correspond to the terms in the
final expression for T_42. Since those terms are all 1, to find T_42
we could just compute the number of paths from 1 to 6.

minicon (21:00:05)


markan (21:01:05)
umm....it doesn't, did i write that somewhere?

markan (21:01:44)
anyway, now that we've found this connection between paths and the entries of the triangle, it's easy to find the numbers

markan (21:01:54)
to find a path to 6, for example,

markan (21:02:04)
we have to go 2 squares southwest and two southeast, but any ordering of these moves is possible

markan (21:02:19)
So the number of paths is

markan (21:02:21)


markan (21:02:34)
it's just like the grid problem

markan (21:02:37)
The same argument would work for any position in the triangle. So in
general, we have

markan (21:02:41)


markan (21:02:51)
Ok, that's all we had planned for tonight.

markan (21:02:56)
Thanks for coming!

markan (21:03:01)
If you want to learn more about combinations and other counting
topics, you might be interested in Art of Problem Solving's Counting &
Probability book, or our Counting & Probability class.

markan (21:03:14)
i'll take questions for a couple minutes, and then we'll turn the moderation off

sbanerjee (21:03:15)
is the exclamation mark in there a factorial symbol, or an exclamation mark?

markan (21:03:40)
it's an exclamation mark