# HW3 Q1a

Hello, can somebody explain me (with a couple of examples or something) what does point 1a mean when it says assigns a sign + or – to a point i?

1. To understand this better I googled it and this could be helpful. Let $\pi$ be a permutation and let $F = \{i: \pi(i) = i\}$ be the set of fixed points of $\pi$.
A decorated permutation $(\pi, col)$ is a tuple where $col: F \rightarrow \{-1,1\}$ assigns 1 or -1 to every fixed point. For example, in one line notation:
$3 \, 2\, 1$ and $3 -2 1$ are two decorated permutations that come from the same permutation but have different decorations. But $-3\, 2\, 1$ isn’t since $3$ was not fixed.
I hope this is correct.

• That’s right. Thanks, Santiago.

2. I’m attempting to prove the recurrence relation f_n=n*f_{n-1}+1. It’s easy to see where 2*f_{n-1} comes from, but does anyone have a nice way to organize the rest of the proof of this? Or is there a nicer recurrence relation to work with?

• That’s a nice idea. There should be a nice way to make it work.
A different approach that can work is non-recursive: identify which decorated permutations are counted by each individual term $n!/k!$. (There is not a unique way to do this, but there is at least one nice way to do it.)

3. I think I misread the question the first time through.. I read this as we’re counting only the total number of decorated permutations, but it seems like it’s actually the total number of permutations including all decorated permutations, right?

4. Okay, answered my own question that this is right, and I think I found what each term counts 🙂

5. yes, a permutation without fixed points is still decorated…with nothing