ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 28 Dec 2015 22:08:34 +0100Counting cycles of induced permutationshttps://ask.sagemath.org/question/31888/counting-cycles-of-induced-permutations/In order to do some sophisticated counting in graph theory, I need to count the cycles of some particular permutations.
In my situation, $n$ is an integer greater than 1, and $K_n$ is the set of all two-element sets {a,b} with $a, b$ being integers not greater than $n$. Now any element $\pi$ of the symmetric group $S_n$ induces a permutation $\overline{\pi}$ of $K_n$ in a natural way, i.e. $\overline{\pi}$ maps any set {a,b} of $K_n$ onto {$\pi(a)$, $\pi(b)$}. What I want to figure out with the help of SAGE is the number of cycles that the permutation $\overline{\pi}$ has.
If you can help me, please do not forget to mention those little extra things that need to be done and that might appear obvious to you (e.g. importing packages and so forth), since I am a relative novice to SAGE.
Thank you very much.
MalteMon, 28 Dec 2015 17:56:15 +0100https://ask.sagemath.org/question/31888/counting-cycles-of-induced-permutations/Answer by vdelecroix for <p>In order to do some sophisticated counting in graph theory, I need to count the cycles of some particular permutations.</p>
<p>In my situation, $n$ is an integer greater than 1, and $K_n$ is the set of all two-element sets {a,b} with $a, b$ being integers not greater than $n$. Now any element $\pi$ of the symmetric group $S_n$ induces a permutation $\overline{\pi}$ of $K_n$ in a natural way, i.e. $\overline{\pi}$ maps any set {a,b} of $K_n$ onto {$\pi(a)$, $\pi(b)$}. What I want to figure out with the help of SAGE is the number of cycles that the permutation $\overline{\pi}$ has.</p>
<p>If you can help me, please do not forget to mention those little extra things that need to be done and that might appear obvious to you (e.g. importing packages and so forth), since I am a relative novice to SAGE.</p>
<p>Thank you very much.</p>
<p>Malte</p>
https://ask.sagemath.org/question/31888/counting-cycles-of-induced-permutations/?answer=31893#post-id-31893 Hello,
This is more a mathematical question rather than a Sage question. Given a permutation $\pi$ with a given cycle decomposition, let say $p = [p_0, p_1, ..., p_{m-1}]$ (I mean that the cycles of $\pi$ have lengths $p_0$, $p_1$, etc). Then the cycle decomposition of the action of $\pi$ on sets can be explicitely computed in terms of $p$. In particular, for the question of the number of cycles you get $$\sum_{i=0}^{m-1} \sum_{j=0}^{i-1} \gcd(p_i, p_j) + \sum_{i=0}^{m-1} \left\lfloor \frac{p_i}{2} \right\rfloor$$.
The above sum can be easily computed with Sage.
VincentMon, 28 Dec 2015 21:20:55 +0100https://ask.sagemath.org/question/31888/counting-cycles-of-induced-permutations/?answer=31893#post-id-31893Comment by Malte for <p>Hello,</p>
<p>This is more a mathematical question rather than a Sage question. Given a permutation $\pi$ with a given cycle decomposition, let say $p = [p_0, p_1, ..., p_{m-1}]$ (I mean that the cycles of $\pi$ have lengths $p_0$, $p_1$, etc). Then the cycle decomposition of the action of $\pi$ on sets can be explicitely computed in terms of $p$. In particular, for the question of the number of cycles you get $$\sum_{i=0}^{m-1} \sum_{j=0}^{i-1} \gcd(p_i, p_j) + \sum_{i=0}^{m-1} \left\lfloor \frac{p_i}{2} \right\rfloor$$.</p>
<p>The above sum can be easily computed with Sage.</p>
<p>Vincent</p>
https://ask.sagemath.org/question/31888/counting-cycles-of-induced-permutations/?comment=31895#post-id-31895Merci, Vincent, for that quick and profound answer. I am surprised to learn that answering my question by doing maths is easier than by doing Sage. Your answer completely satisfies my needs, as far as I understand things by now. The reason I was thinking of this as a Sage problem was that I couldn't find a way to make Sage tell me anything about the cycle decomposition of a permutation operating on anything other than integers (here, it's **sets** of integers instead), and I thought maybe I needed a hint in that direction. Do you happen to know of a general theorem cited in a mathbook that discusses your mathematical solution?
Anyway: Thank you very much for your kind answer.
Vive la France,
MalteMon, 28 Dec 2015 22:08:34 +0100https://ask.sagemath.org/question/31888/counting-cycles-of-induced-permutations/?comment=31895#post-id-31895