Algebraic Combinatorics

What is Combinatorics

Count how many Answer is a number

Enumerate between the
g set

establishing an
explicit bijection

Count

Example Permutations

How many permutations of numbers 1 ton

are there

Defn A is a
way to write numbers
permutation
in some order

For example n 3 1
2.3
We have
permutations 1.2.33 I 1 3,2
2
1,3 12 3 l

13.1 2 13 2
D
of permutations 6 3 3 2 1
In general case the answer is n

n n 1 In
n 27 1

Remark We can talk about

any set win
in elements
and permutations of this jet

Example n choose k How

many ways are
there
to choose k elements from h
elements

n 4 6 2 I 1 2
3.44
41 r
41.31 31.44 42.3 42,44
g g
6
In general we first count how
many ordered
b elements ace there 7 ane
different
h Ch D i
h Rtl

For any k element subset there are k ordered

to elements
n Cn 11 n ka n
n choose to
k n k
TE
 1 nIe binomial coefficient

xxygn
I
Enumeration

identities for binomial

Example coefficients

nh
Ih obvious from the formula

How to establish an explicit bijection

h element subsets
of h elements
Y

in H element
subsets
of s elements
y

f A 7
A complement
of A
For example n 5 k 2

A _41.24 fCA _Ac 93,4 s y

This proves Ink nhu

nth I 111 from explicit

Emma
Look for an enumeration
proof
A subset of 41.2 n
114 either contains
htt or it does not

To a k element subset
give containing h

we need to choose 1k 1 elements from

41 l n
Fy
To give a h element subset not
containing a
we need to choose k elements
from
41,21 n
Y
1h nm 112
 Next example partitions of
i a
positive
integer

Refn Let n be a
positive integer
we
By a partition of h mean
presentation
of
the sum several positive integers
n as
of
order summands does
of not matter

For example h y

4 3 1 2 2 2 11 11 I 111 1
1
of partitions
of 4 is 5

No
explicit formula
for partition of h's
Lemma Let n and k be positive
integers
The number of partitionstn he more
than
t amas
of
partitions
of n where each
part Ek
 One box
Pfi can use a
diagramy to

represent
a partition graphically

n n thr i
t
ne ni 7h In
zne
we
put n boxes in the
first row

Nz boxes above the

first row
aligned on
the left
n 4 4 ITI
n

3h
Tty1
2 2
THI box diagrams
21 1 H With n

Ffg
boxes

it t

f
of rows is equal to
of parts
of column is equal to maximum
of all
parts
To the lemma we use tr
prove
of a
box diagram

A
i

12 2 2
11

AL It
2 2 C 2 2 12

This proves the lemma

Algebra
algebraic operations
fundamental example i
group
Deth A group G is set with

a binary operation a
map
a
G X G G also called multiplicate
or
product
is denoted
usually by a
symbol
or without
any symbol
G x G G
g h t
gh or
gh
The
product satisfies the
following
axioms
µ Associativity k
gh gfhk
2 Unit element
Identity element
Neural element
There exists an element e C G
e Such that
g g e
g for any
g EG
3 Inverse element
tg EG
for any gins
I there exists I E
G
g Such that
 gg's gg ee

Pupi Unit element is unique

Pf Assume e and ez are both unit elements

yeig
get y tonnages
e V
g ga g gc

g
G.TL ez.eier eei ez
I
Take e e er
g
t
e

e ez
I

Examples

Example l G D Set
of integers
together with addtion
of numbers
A b Atb 4 Atb 1C at Cbtc
12 e O Ot a a 10 a

13 Inverse A E a at f a
c a
a
p

2 t is a
group
similarly Q1 t a set
of atonal numbers
K t IR set
of real
number
E t G set of complex numbers

Example 2 G HOY set

of
non no
rational number
a b A xb multiplication
of numbers

The unit element is 1

Of alloy X

112 1121904 X

E GYM x

There are because

groups special the

products are commutative Abeba

 This not the case
always
C Permutation
Example3 group
set
Perm n
of permutations
of
h elements 41 2.3
ng
Perm in n

In order to
give a
group structure on pens
we view each permutation as a
map
to
4 r
try itself 51,2
ay
The the first
image
of 1 is element in
a
permutation the image
of 2 it the
second
element
For example h 3 a
permutation 1 3 z
l 1 3

Given
f I 1.2
by 4112
ny
two
41.2 n 51.2 my
map Yi
 the
we can form Umposition

fog 41 L
try 51.2 by

fog Ii
f gli
permutations are all the
exactly maps

41,1 n h to that are one to

itself one
e4 k
bijectiej.fi fjimpei j
is also
f surjective for any y 7 i
Such that feil p

The multiplication two

of permutations is
defined by composition of two
maps
11 Associativity fog h
ftp.b
Htt
fifth3
 teh iffy

fog h
fiqh
2 Unit element
e il the
identity map
41.2 try to
itself
eli i

e
of fi
elfin fois eye f
f e il flea fi foe _f
Invate
3
fi 41,2 ay 11,2
ng
f bijective

Define
f i
4 I L h
41,2 my
f i is the uni
Metemstg sauna
taj i
 heck f f f f
j from the definition f fi y
if fej i

f f tis T
f of i i
f f e

compute
f off of Tfof 1

of
e
of f
It
f it
injective
f of fig i

f f e

Computations It is convinient to write

a permutation in 2 lines

iii is in
it t
f
12 n
g jiji in

To compute we
gof permute the

columns
of g such that the
top
line is i il in

f 1.3.24

g 12 1.3.41

f list 9
4,7
list
get ft
To compute
fog f

fog

g ft fog
Perm 4 is not commutative anden
composition