Permutation Involution

Author

Eric W. Weisstein
November 30, 2008

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Combinatorics/PermutationInvolution.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/PermutationInvolution.html.

©2008 Wolfram Research, Inc. except for portions noted otherwise

Initialization

<<Combinatorica`

Code

SelfConjugatePermutationQ[p_?PermutationQ]:=(p==InversePermutation[p])

Enumeration

Table[
Select[Permutations[Range[n]],SelfConjugatePermutationQ],
{n,4}]//ColumnForm

Table[
Select[Permutations[Range[n]],InvolutionQ],
{n,4}]//ColumnForm

Counts

Length/@Table[Select[Permutations[Range[n]],SelfConjugatePermutationQ],{n,8}]

1+Sum[Product[b[n-2i,2],{i,0,k}]/(k+1)!,{k,0,(n-1)/2}]

(i^(-n)) (2^(n/2)) (HypergeometricU[-(n/2), (1/2), -(1/2)])

Table[(I^(-n)) (2^(n/2)) HypergeometricU[-(n/2),(1/2),-(1/2)],{n,10}]

1+(∑_(k=0)^((n-1)/2))(1/((k+1)!))(∏_(i=0)^k)(Binomial[n-2 i, 2])+1

Table[1+Sum[Product[Binomial[n-2i,2],{i,0,k}]/(k+1)!,{k,0,Floor[(n-1)/2]}],{n,10}]

Product[Binomial[n-2i,2],{i,0,k}]

Table[(2^(-1+k)) (-1+n) n Pochhammer[1-(n/2),k] Pochhammer[(3/2)-(n/2),k],{k,5},{n,5}]

(2^(-1+k)) (-1+n) n Pochhammer[1-(n/2),k] Pochhammer[(3/2)-(n/2),k]/.{k->1,n->4}

FullSimplify[(2^(-1+k)) (-1+n) n Pochhammer[1-(n/2),k] Pochhammer[(3/2)-(n/2),k],(k|n)∈Integers&&n>0]

Table[(((2^(-1-k)) Gamma[2+2 k-n])/(Gamma[-n])),{n,10}]

V6

1+Sum[Product[Binomial[n-2i,2],{i,0,k}]/(k+1)!,{k,0,(n-1)/2}] /. Sin[n π]->0

FullSimplify[%]

Product[Binomial[n-2i,2],{i,0,k}]

Table[(2^(1+k)) Pochhammer[(1/2)-(n/2),1+k] Pochhammer[-(n/2),1+k],{n,5},{k,5}]

Sum[(2^(1+k)) Pochhammer[(1/2)-(n/2),1+k] Pochhammer[-(n/2),1+k],{k,0,(n-1)/2}]

Table[(∑_(k=0)^((1/2) (-1+n)))(2^(1+k)) Pochhammer[(1/2)-(n/2),1+k] Pochhammer[-(n/2),1+k],{n,5}]

V7

Product[Binomial[n-2i,2],{i,0,k}]

Table[(2^(-1+k)) (-1+n) n Pochhammer[1-(n/2),k] Pochhammer[(3/2)-(n/2),k],{n,5},{k,5}]

Sum[(2^(-1+k)) (-1+n) n Pochhammer[1-(n/2),k] Pochhammer[(3/2)-(n/2),k],{k,0,(n-1)/2}]

Table[Sum[(2^(-1+k)) (-1+n) n Pochhammer[1-(n/2),k] Pochhammer[(3/2)-(n/2),k],{k,0,(n-1)/2}],{n,5}]

1+Sum[Product[Binomial[n-2i,2],{i,0,k}]/(k+1)!,{k,0,(n-1)/2}]

V8

Product[Binomial[n-2i,2],{i,0,k}]

1+Sum[Product[Binomial[n-2i,2],{i,0,k}]/(k+1)!,{k,0,(n-1)/2}]

n! (∑_(k=0)^(n/2))(1/((2^k) k! (n-2 k)!))

Table[n!Sum[1/(2^k k!(n-2k)!),{k,0,n/2}],{n,10}]

n!Sum[1/(2^k k!(n-2k)!),{k,0,n/2}]

Table[n!Sum[1/(2^k k!(n-2k)!),{k,0,n}],{n,10}]

n!Sum[1/(2^k k!(n-2k)!),{k,0,n}]

Table[(I^(-n)) (2^(n/2)) HypergeometricU[-(n/2),(1/2),-(1/2)],{n,10}]

Table[{(E^(-(1/2) I n π)),(-I)^n},{n,5}]

Table[(2^(n/2)) (-I)^n  HypergeometricU[-(n/2),(1/2),-(1/2)],{n,10}]

i3[n_?EvenQ]:=Module[{k=n/2},FullSimplify[i[2k],{k∈Integers}]]
i3[n_?OddQ]:=Module[{k=(n-1)/2},FullSimplify[i[2k+1],{k∈Integers}]]

FullSimplify[i[2k],{k∈Integers}]

FullSimplify[i[2k+1],{k∈Integers}]

V8

n!Sum[1/(2^k k!(n-2k)!),{k,0,n/2}]

FullSimplify[%]

Recurrence

a[0]:=1
a[1]:=1
a[n_]:=a[n]=a[n-1]+(n-1)a[n-2]

Table[a[n],{n,10}]

V5.2

<<DiscreteMath`RSolve`

RSolve[{a[n]==a[n-1]+(n-1)a[n-2],a[0]==1,a[1]==1},a[n],n]

V6

RSolve[{a[n]==a[n-1]+(n-1)a[n-2],a[0]==1,a[1]==1},a[n],n]

V7

RSolve[{a[n]==a[n-1]+(n-1)a[n-2],a[0]==1,a[1]==1},a[n],n]

{{a[n]->DifferenceRoot[Function[{\[FormalY],\[FormalN]},{(-1-\[FormalN]) \[FormalY][\[FormalN]]-\[FormalY][1+\[FormalN]]+\[FormalY][2+\[FormalN]]==0,\[FormalY][0]==1,\[FormalY][1]==1}]][n]}}

Table[%[[1,1,2]],{n,10}]

Table[(I^(-n)) (2^(n/2)) HypergeometricU[-(n/2),(1/2),-(1/2)],{n,10}]

V8

RSolve[{a[n]==a[n-1]+(n-1)a[n-2],a[0]==1,a[1]==1},a[n],n]

RecurrenceTable[{a[n]==a[n-1]+(n-1) a[n-2],a[0]==1,a[1]==1},a[n],{n,1,10}]

Generating Functions

Generating Function

Sum[(I^(-n)) (2^(n/2)) HypergeometricU[-(n/2),(1/2),-(1/2)]x^n,{n,∞}]//FullSimplify

Sum[(((-2))^k) HypergeometricU[-k,(1/2),-(1/2)](x^(2k)),{k,0,5}]+Sum[(((-2))^k) HypergeometricU[-k,(3/2),-(1/2)](x^(2k+1)),{k,0,5}]

Sum[(((-2))^k) HypergeometricU[-k,(1/2),-(1/2)](x^(2k)),{k,0,∞}]+Sum[(((-2))^k) HypergeometricU[-k,(3/2),-(1/2)](x^(2k+1)),{k,0,∞}]

GeneratingFunction[(I^(-n)) (2^(n/2)) HypergeometricU[-(n/2),(1/2),-(1/2)],n,z]

FindGeneratingFunction[{1,2,4,10,26,76,232,764,2620,9496,35696,140152},x]

ExponentialGeneratingFunction

Sum[(I^(-n)) (2^(n/2)) HypergeometricU[-(n/2),(1/2),-(1/2)]((x^n)/(n!)),{n,0,∞}]

exp(x+x^2/2)

CoefficientList[Series[Exp[x+x^2/2],{x,0,10}],x]Range[0,10]!

Sum[(((-2))^k) HypergeometricU[-k,(1/2),-(1/2)]((x^(2k))/((2k)!)),{k,0,∞}]+Sum[(((-2))^k) HypergeometricU[-k,(3/2),-(1/2)]((x^(2k+1))/((2k+1)!)),{k,0,∞}]

DirichletGeneratingFunction

Sum[(((I^(-n)) (2^(n/2)) HypergeometricU[-(n/2),(1/2),-(1/2)])/(n^s)),{n,∞}]

Lambert Series

Sum[(((I^(-n)) (2^(n/2)) HypergeometricU[-(n/2),(1/2),-(1/2)](x^n))/(1-(x^n))),{n,∞}]