GAIさんへのお返事です。
> 要素が例えば４つの場合に
> 全順列が４！＝２４通りある中で、次の１０個
> （１，２，３，４）
> （１，２，４，３）
> （１，３，２，４）
> （１，４，３，２）
> （２，１，３，４）
> （２，１，４，３）
> （３，２，１，４）
> （３，４，１，２）
> （４，２，３，１）
> （４，３，２，１）
> をP1としてとったとき、例の関係を満たすようにするP2が全く同じものになりました。
N=4の場合、条件を満たすものを置換および巡回置換で表現すると
┌ 1 2 3 4 ┐
└ 1 2 3 4 ┘
=( 1 )( 2 )( 3 )( 4 )
┌ 1 2 3 4 ┐
└ 1 2 4 3 ┘
=( 1 )( 2 )( 3 4 )
┌ 1 2 3 4 ┐
└ 1 3 2 4 ┘
=( 1 )( 2 3 )( 4 )
┌ 1 2 3 4 ┐
└ 1 4 3 2 ┘
=( 1 )( 2 4 )( 3 )
┌ 1 2 3 4 ┐
└ 2 1 3 4 ┘
=( 1 2 )( 3 )( 4 )
┌ 1 2 3 4 ┐
└ 2 1 4 3 ┘
=( 1 2 )( 3 4 )
┌ 1 2 3 4 ┐
└ 3 2 1 4 ┘
=( 1 3 )( 2 )( 4 )
┌ 1 2 3 4 ┐
└ 3 4 1 2 ┘
=( 1 3 )( 2 4 )
┌ 1 2 3 4 ┐
└ 4 2 3 1 ┘
=( 1 4 )( 2 )( 3 )
┌ 1 2 3 4 ┐
└ 4 3 2 1 ┘
=( 1 4 )( 2 3 )
恒等置換と長さ２の巡回置換のみが該当するので
恒等置換 １つ
長さ２ (x x)、(x x)(x x)の形は、COMB(4,2)=６、COMB(4,2)*COMB(2,2)/FACT(2)=３
したがって、１＋６＋３＝１０
!参考サイト http://www.research.att.com/~njas/sequences/A000085
!1 + COMB(N,2)/1! + COMB(N,2)*COMB(N-2,2)/2! + COMB(N,2)*COMB(N-2,2)*COMB(N-4,2)/3! + …
LET N=4
LET T=1
FOR i=1 TO INT(N/2)
LET S=1
FOR k=0 TO i-1
LET S=S*COMB(N-2*k,2)
NEXT k
LET T=T+S/FACT(i)
NEXT i
PRINT T
END