Lecture notes
MT2504 Combinatorics and Probability: Chapter 2
- Institution
- University Of St Andrews
Handwritten revision notes
[Show more]
Seller
Follow
Content preview
Counting combinatorial structuresChapter 2
Theorem u ') .
PIGEONHOLE PRINCIPLE
let m n r EIN se m > nr
, ,
If m objects are divided into n sets
,
at least one set contains at least rtl
objects .
r =L In ) ( ie number of times can
.
you
wholly fit n into m ]
Proof :
Let It be a set with III -
- m
Let Ai ,
. . .
,
An E II sit # =
it ,
Ai e- Doesn't have to be a
partition
then
,
IA I ,
t -
- -
t IA n
I > m > nr
Impossible if til Ail Er
( then El Ail Snr
)
Remarks :
"
pigeonholes
"
tf then hole has 3 Rtl
put into
pigeons
•
n
m
pigeons are one
Proof used
•
a more basic fact :
Ha , .
.
- .
.
an EIR
,
mix ai
s
,
ta la ,
t - -
-
tan )
' 2
Eg
'
Show that
among
6
people (A ,
O C
, , QE F) ,
,
there are either 3 who all know each other
,
or 3 who are
mutual strangers .
Pick one
person arbitrarily (A) .
There are 5 other people ( 8,40 E
,
F) who know
I don't know this person .
,
Divide 5 into
remaining people two sets :
•
One set contains all who know A
•
The other set contains all who don't know A .
P H P three
By -
-
,
one set must contain at least
people
A
Suppose → 3 know :
we ( without
losing generality) 8 and all know A then either :
can C 0
say ,
.
of 8 C and 0 know each other ( O, C and 0 mutual strangers )
-
None .
,
32 each other B and C which each other
-
know in A 8 C know
,
say ,
case
, ,
Suppose 73 don't know A :
we can
say
( without
losing generality ) 8, c and 0 don't know A . then either :
B C D all know each other ( found set each other)
of three people who
-
, , know .
-
72 don't know each other 0 and C which mutual
, say ,
in case A. 0
,
c are
strangers
, I -3
Eg
Show that in
any set of m
people ,
at least two have the same number of friends in the set .
Each has between O and m l friends in the set
person
-
.
sets
Let 8; be the subset people with friends Oo Bm ( these
disjoint)
!
i → m
of .
.
. . -
,
-
,
are
of Bo
observation : one or Bm -
i
is
empty .
↳ If somebody friends with
everybody ,
then everyone
has at least one friend ( Oo empty)
↳ If someone knows
nobody then no one knows
everyone ( i.e . Bm -
i
is empty ) .
,
So m
people ,
m -
I subsets
,
PHP says some toil > 2
Cl u)
Eg
-
How many
people do we need to
guarantee 5 of them have
birthdays in the same month ?
(12×4)+1 =
49
n
p
-
Let Ai be the set of
people with birthdays in month i e El
,
. . .
,④}
we want in some
Ai
↳ rt ,
If 12×4=48 S PHP if
people
nr
then by
m
month
>
49
-
s, in some .
,
( 1. s )
Eg
Is there multiple of 1413 in the 7 77 777 7777 ?
a
sequence , , , ,
. .
.
Let ai
= 77 . .
-7 so a
,
-
- 7
,
ai 77
-
i times
set bi
-
-
ai mod 1413 ( remainder after
dividing by 1413 ) for I a- is 1413 .
CASE 1 :
some bi -
- O
.
Done since if O -
ai mod 1413 then 1413 divides ai .
CASE 2 !
No bi -
-
O .
there are 1413 bi 's and only 1412
possibilities for them :
Possibilities 1412 ( remainder 't itself)
:
1,2 , .
-
-
,
can be 1413
there bi bj (i j) ( P H P)
↳ Hence exists #
by
= - .
Assume j > i :
Ioi La
a ai
)
- -
;
-
; -
i
A
-
-
7 7 7 7
; . . -
7 7 7
aj
=
-
. . .
77 70 O
aj a
-
= . . - . - -
,
-
Ioi
Aj -
i
"
By construction :
1413 divides 10 ( aj -
i )
To finish : 2 does not divide 1413 and 5 also does not divide 1413 .
.
'
.
10 does not divide 1413
,
Hence 1413 divides ai which is in the
j sequence
-
,
so ans =
yes
=
, Definition :
the CARTESIAN PRODUCT
' '
Y
"
→ X cross
II ×
Y of sets IT ,
'T is the set
x
'T -
-
{( x
, y ) :
x c-
II , ye 'T }
of all ordered pairs w/ ace # , ye 'T
[ Cx , y
) # Cy ,
x ) ]
Eg :
{ 1.2.33 xea.b.is
-
-
{ !! :} ! !!:b;) ! ! }
NOTATION ( 2 2) -
S E Ix 'T
r. G) =/ { y :( x. g) ES } Cy ( s )
=
{ x :( x. g) es }
r = row c
-
-
Col
G 3)
Eg -
TI -
-
{ a
,
b. c. d } Y -
-
{ 1.2.33
,
,
s=E@④C kiss , ,
( a. 21 ,
3,④D3 EXIT
( s)
r⑤( s ) 2
⑧
=3
-
-
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller WinterBerry. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for £10.49. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
71184 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy revision notes and other study material for 14 years now