I wonder why number of permutations on $\hat n$ without a fixed point satisfies this recurrence: $r_n = (n-1)r_{n-1}+(n-1)r_{n-2}$

A fixed point is number $i$ such that $\pi (i) = i$

It is mysterious to me. The recurrence has solution $ \lfloor { n! e^{-1} + \frac{1}{2} \rfloor}$

@Pedro @Fernando lel

@mirgee You can make a combinatorial argument.

@PedroTamaroff That's what I would like to do!

@mirgee Well, do it.

Suppose $i_1\ldots i_n$ is a derrangement.

Well, the number permutations should satisfy this recurrence $n! = d_n + nd_{n-1} + {n \choose 2}d_{n-2} + ... + {n \choose n} d_0$, I think

@mirgee I know the following argument.

@mirgee: you might find this answer to be of use.

Pick $k$ such that $i_k=1$.

Consider two cases.

First, $i_1=k$; second $i_1=j\neq k$.

This should give you $d_n=(n-1)d_{n-1}+(n-1)d_{n-2}$.

@robjohn That looks very informative, thanks! Can't wait to read it.

@mirgee I have to go in a bit, but if you have any questions, ping me and I will get to them when I get back.

@PedroTamaroff Its one of my favorite combinatorial arguments :)

Nice :)

@r9m did you see the link I gave to mirgee? I give the three ways I know to compute derangements.

@robjohn liked it and (+1) upvoted it :)

@r9m I taught a class in Discrete Math at UCLA long ago. That was one of the topics.

@robjohn :) .. Our prof only concentrated his efforts on graph theory .. he did little combinatorics ..

But in the final .. he gave most questions from Combinatorics and little from graph theory .. :P

@Alyosha It holds in any integral domain.

@Alyosha $a\mid b,b\mid a\implies a=bu=(ak)u=a(ku)$, integral domain then $ku=1$.

So $u$ is a unit and $a\sim b$.

@PedroTamaroff I managed to do that much, but why does it follow that, if $ku=1$, then $u$ is unit?

It's not a field so inverses don't exist always, but they may exist for some elements, surely (here, $k$ and $u$)?

Well, you also have $b=ak=(bu)k=b(uk)$.

So $uk=1$ too.

At any rate, is the ring commutative?

Then all is easier.

Yes.

Well, then $ku=1\implies uk=1$.

So $k,u$ are invertible.

I'm being stupid, I don't see why they are invertible due to this.

Read the definition of invertible again.

You might have forgotten it.

I had.

Well, not learned it.

Regardless, why does their invertibility here mean they're both equal to $1$?

@Alyosha They are not equal to one. Their product is.

Being associate means $a=ub$ for $u$ a unit.

you have $b=b(uk)$; you have cancellation in domains - use it

For example, $2x+1$ is associate to $x+1/2$ in $\Bbb Q[X]$.

@PedroTamaroff I've got it now, sorry for wasting your time a little, I should have reread the definitions first.

@FernandoMartin I am stuck in the lemma.

diagram chase

The proof and definition of the boundary morphism I could manage to obtain.

Not that.

which lemma?

I have to show the exactness now.

that's diagram chasing as well

Well, I want to show that $\ker d={\rm im}\, \bar v$.

ok

what are you proving, $\subseteq$ or $\supseteq$?

I showed that ${\rm im}\, \bar v\subseteq \ker d$.

Now, suppose that $d(x'')=0$.

ok

This means that if $x''=v(x)$ and $f(x)=u'(y')$, $y'\in {\rm im}\, f'$.

So $f(x)=u'f'(x')=fu(x')$. I should be getting that $x\in \ker f$.

But I get $x-u(x')\in \ker f$.

gimme a sec

So if I show that $fu(x')=0$, I'm done.

right

let me try to write it down

${\rm im}\, u=\ker v$.

Ah, that is it.

Got it.

ok

We can write $x=j+l$, $j\in \ker v$ and $l\in \ker f$.

apparently there's an element free proof

Then $x''=v(x)=v(j)+v(l)=v(l)$.

So $x''=v(l),l\in\ker f$.

@FernandoMartin Probably uses 120935090945 universal properties.

@r9m we did a lot of graph theory as well, but pretty simple stuff.

jesus

@FernandoMartin cheesus.

@FernandoMartin is He in chat?

It's pretty bad @Pedro

doubt it @robjohn

@FernandoMartin you never know...

it works for arbitrary abelian categories though

"Arbitrary abelian categories were a terrible idea, why did you let us do that?"

@FernandoMartin y'know what they call topology where you don't bother with elements of your space and only think about the lattice of open sets, right?

pointless top?

yes

@robjohn Nice :)

so, too, is an element-free proof pointless, @FernandoMartin

pointless > pointful

Lexicographically, @FernandoMartin.

@FernandoMartin sometimes I wonder if I am doing pointless analysis...

@robjohn You are back :) I have a question regarding your answer on the number of derangements, if I may

@mirgee sure... I actually bypassed my trip by doing stuff online.

@robjohn I am sorry, but I don't quite get why we get derangment of n-1 intems in the second case

@mirgee okay... let me look at that case.

@mirgee are you looking at Method 2?

@robjohn No, I meant method 1

@robjohn I get the picture that we select an item, invert the permutation and then permutate all the other items, is it correct?

@mirgee we are counting the number of derangements $P$ so that $P(P(n))=n$, or the other case?

@robjohn The coordinates are Method 1, case 2 :)

@mirgee ah so counting the permutations so that $P(P(n))\ne n$

@robjohn Yes

@robjohn For each selected item, we may invert the permutation and permutate the rest again, right?

@mirgee so first choose which element $k$ we want $P(n)=k$. By hypothesis, $P(k)\ne n$.

@robjohn Well, if yes, I don't see why this encompasses all possible derangements in this case...

@mirgee for each permutation so that $P(n)=k$, we can associate that with the derangement of $n-1$ items that sends $P^{-1}(n)$ to $P(n)$ and is otherwise identical to $P$

@robjohn That's what I can't get my head around... Any simple example? Please please :)

@mirgee consider any Derangement of $n-1$ items. Choose item $k$ and instead of sending it to $P(k)$, send $k$ to $n$ and send $n$ to $P(k)$

that creates a derangement of $n$ items. It actually creates all derangements so that $P(P(n))\ne n$

@robjohn Yes

@mirgee does the second case make sense now?

@robjohn I think so :)

@mirgee great :-)

@robjohn Maybe I just misunderstood the original

@robjohn I guess I will have to think about why we split it into those two cases

@robjohn what makes the second case work

@robjohn Oh, I see already :)

@mirgee it is so that we can "factor" the derangements of $n$ items through item $n$ to get $n-1$ derangements of $n-1$ items and $n-1$ derangements of $n-2$ items

@robjohn And if $P(P(n)) = n$, we don't get a derangement this way

@mirgee then we get $n-1$ derangements of $n-2$ items.

@mirgee If $P(P(n))=n$, then we can pull out $n$ and $P(n)$ and get a derangement of the remaining $n-2$ items

@robjohn Yes, I get that, sorry, don't know what I was trying to say :)

Thanks a lot @robjohn :)

@mirgee any time :-)

I am so glad this community exists! Those generous people here are helping me so much in my studies! Wish I had the ability to help someone, but maybe one day :)

@seaturtles Hello, stranger.

yo

@seaturtles What's the news?

news is haram

@PedroTamaroff nothin

@seaturtles Oh. Sometimes nothin' is good.

Better than something.

yes