11
$\begingroup$

How many elements of order $2$ are there in $S_n$?

Using combinatorics I arrived at this:

For $n$ even ($n=2k$) there are ${n\choose2}+{n\choose 2}{n-2\choose 2}\dfrac{1}{2!}+{n\choose 2} {n-2\choose 2}{n-4\choose 2}\dfrac{1}{3!}+\cdots+{n\choose 2}{n-2\choose 2}{n-4\choose 2}\cdots{2\choose 2}\dfrac{1}{k!}$.

For $n$ odd ($n=2k+1$) there are ${n\choose 2}+{n\choose 2}{n-2\choose 2}\dfrac{1}{2!}+{n\choose 2}{n-2\choose 2}{n-4\choose 2}\dfrac{1}{3!}+\cdots+{n\choose 2}{n-2\choose 2}{n-4\choose 2}\cdots{3\choose 2}\dfrac{1}{k!}$

But how do I find the sums?

Seems like I have to use induction. But not quite upto there.

Thanks for the help!!

$\endgroup$
  • 2
    $\begingroup$ I do not think there is a closed form for this sum. $\endgroup$ – Chris Godsil Aug 11 '14 at 13:39
  • 2
    $\begingroup$ See this for some references etc oeis.org/A001189 $\endgroup$ – Mark Bennet Aug 11 '14 at 14:02
4
$\begingroup$

An element of order $2$ is a product of $k$, say, disjoint 2-cycles.

  • For $k=1$, there are $\frac{n(n-1)}{2^1\cdot 1!}$ elements of order two.

  • For $k=2$, there are $\frac{n(n-1)(n-2)(n-3)}{2^2\cdot 2!}$ elements of order two.

  • For $k=3$, there are $\frac{n(n-1)(n-2)(n-3)(n-4)(n-5)}{2^3\cdot 3!}$ elements of order two.

In the denominator of each fraction, you have a $2^k k!$, because each 2-cycle could be chosen in the form $(a, b)$ or in the form $(b, a)$ (so you need to divide by $2^k$), while the different permutations of the 2-cycles don't change the element (so you need to divide through by $k!$). Hence, you get in general:

  • There are $\frac{n \choose 2k}{2^k\cdot k!}$ elements of order two which are the product of $k$ disjoint 2-cycles.

Then sum these to get your number! $$\text{number of elements of order two}=e_2(n)=\sum_{k=1}^{\lfloor n/2\rfloor}\frac{n \choose 2k}{2^k\cdot k!}$$ Note that the following recurrence relation holds. $$e_2(n)=e_2(n-1)+(1+e_2(n-2))(n-1)$$

$\endgroup$
  • $\begingroup$ My question is how do i find the sum of what i asked?? $\endgroup$ – tattwamasi amrutam Aug 11 '14 at 13:49
  • $\begingroup$ This is exactly what I wrote $\endgroup$ – tattwamasi amrutam Aug 11 '14 at 14:10
  • $\begingroup$ @tattwamasi Well, it isn't exactly what you wrote. As the comments to your post point out, it is unlikely that there is a closed-form of this sum (this is especially implied by the oeis link, where no closed-form is given). So I thought it would be helpful, at lease to others, to write down the sum as neatly as possible. So I gave you (what I considered to be) a neater way of writing the terms of the sum, as well as a recurrence relation. $\endgroup$ – user1729 Aug 11 '14 at 14:26
1
$\begingroup$

it is probably not any help, but i think your sum may be written $f(\sqrt{2})$ where $$ f(x) = \sqrt{2}^{-n} \sum_{k=1}^{\lfloor \frac{n}2 \rfloor} \frac1{k!}\frac{d^{2k}}{dx^{2k}}x^n $$

$\endgroup$
1
$\begingroup$

If you accept a confluent hypergeometric function as a closed form, then a Computer Algebra System like Mathematica will give you
for even $n = 2w$:
$\left(-\frac{1}{2}\right)^{-w} U\left(-w,\frac{1}{2},-\frac{1}{2}\right)-1$
and for odd $n = 2w-1$:
$\left(-\frac{1}{2}\right)^{1-w} U\left(1-w,\frac{3}{2},-\frac{1}{2}\right)-1$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.