Justin Komisarof
Mandie asked a question about her work that turned out to be a question about set theory
(not group theory)
ish?
she noticed that if you have four objects (1, 2, 3, and 4)
and you construct a bijection (1 -> 3, 2 ->4, 3 -> 1, 4 -> 2)
sometimes if you write out the order of the things 1 2 3 4 now map to
3 4 1 2
that's the same as the bijection
but for other bijections (1 -> 2, 2 -> 3, 3-> 1, 4 -> 4)
gj google
then you end up with 3 1 2 4
which is not the same as the bijection
so I realized that this property is basically a way of identifying bijections f(x) such that f(f(x) = x
Kevin Carde
you and Mandie are discovering involutions :D
Justin Komisarof
so then we tried to generalize
Kevin Carde
(bijections such that f(f(x)) = x)
Justin Komisarof
for 2-element sets, all bijections are involutions
for 3-element sets, 4 of 6 possible bijections are involutions
Justin Komisarof
so the Mandie conjecture was that for an N element set
Kevin Carde
ooh but I want to hear her conjecture
Justin Komisarof
2/n bijections are involutions
2/n of the n! bijections
that is
Kevin Carde
so studying these things (permutations, and in particular involutions) is one of my favoritest things
and I hope you and Mandie will keep playing with them :D
but I must off to lunch now
bye for now!
Justin Komisarof
nooo are you going to make us prove the Mandie conjecture???
or disprovei t
Kevin Carde
the power is yours!
talk to you later!
Kevin Carde
hey!
I collapsed into nap after food
I didn't sleep at all last night =\
Justin Komisarof
aw Kevin
ar eyou feeling better?
Kevin Carde
a bit =)
was just a lonnnngg travel day
Justin Komisarof
ok so I think I have a solution
Kevin Carde
oh?
Justin Komisarof
for how many bijections on a set are involutions
it's a counting problem!
Kevin Carde
indeed!
Justin Komisarof
so for n = 1 1/1 bijections are involutions
for n = 2 2/2 bijections are involutions
for n > 2
we take the newest element added to the set
it can either map to itself or not
if it maps to itself
then there are the same number of involutions as there are for N-1
if it maps to some other element
then that other element must map to it
there are n-1 other elements it could map to and then once those two are out of the way there are f(n-2) involutions for each of the n-1 possible choices
so f(x) = f(x-1) + (x-1)f(x-2)
where f(1) = 1 and f(2) = 2
Kevin Carde
this is a great solution =)