Integration over quantum permutation groups

We find a combinatorial formula for the Haar measure of quantum permutation groups. This leads to a dynamic formula for laws of diagonal coefficients, explaining the Poisson/free Poisson convergence result for characters.