A334830 a(n) is the number of permutations of length n that have the same number of fixed points whether forwards or backwards.

1, 1, 0, 0, 14, 46, 200, 1496, 11718, 111558, 1052272, 12261712, 140348300, 1915312460, 25732919088, 402510985872, 6210501292870, 109537725353798, 1908681625474400, 37475105645783072, 727818914470269924, 15743598127274107044, 337206399213040703920

Offset: 0

Author

Michael Cader Nelson, Jun 24 2020

Keywords

• nonn

Comments

Relevant to the "matching problem" in combinatorics: For a random permutation of the integers 1 through n, what is the expected number of elements in the permutation equal to their respective order in the permutation?

If m(P[n]) is a function that returns the number of matches for a particular permutation P of the integers 1 through n, and -P[n] is P[n] backward, then a(n) answers the question, "For how many permutations P[n] does m(P[n]) = m(-P[n])?"

Equivalently, the probability that m(P[n]) = m(-P[n]) for a random permutation of length n equals a(n)/n!.

Also relevant to the null hypothesis statistical test (NHST) called the matching method, used to evaluate the experimental hypothesis that two nominal or ordinal populations are mutually independent.

A simplified version of this sequence is "the number of distinct permutations...", where reversing the order of elements does not create a distinct permutation. Each element in the simplified sequence after n = 1 is half of a(n). However, this sequence no longer has the property that a(n)/n! is the probability that m(P[n]) = m(-P[n]) for a random permutation of length n.

Examples

			Permutations and their reversals for n = 3: {1, 2, 3}, {3, 2, 1}; {1, 3, 2}, {2, 3, 1}; {2, 1, 3}, {3, 1, 2}; {2, 3, 1}, {1, 3, 2}; {3, 1, 2}, {2, 1, 3}; {3, 2, 1}, {1, 2, 3}. Total number of elements for which the i-th element equals i: 3, 1; 1, 0; 1, 0; 0, 1; 0, 1; 1, 3. a(3) = 0.
		

References

• G. W. Allport and P. Vernon, Studies in expressive movement. New York: Macmillan, 1933.

Links

• C. D. Evans, J. Hughes, and J. Houston, Significance-testing the validity of idiographic methods: A little derangement goes a long way, British Journal of Mathematical and Statistical Psychology, 55(2), 385-390 (2002).
• W. V. Li, F. Liu, and X. Shi, An analysis of the last round matching problem, Journal of mathematical analysis and applications, 323(2), 1373-1382 (2006).
• P. R. de Montmort, Essay d’Analyse sur les Jeux de Hazard, Chez Jacque Quillau, imprimeur-juré-libraire de l'Université, rue Galande, 1713 - 191 pages.
• P. E. Vernon, The evaluation of the matching method, Journal of educational Psychology, 27(1), 1 (1936).

Crossrefs

Cf. A000142, A000166, A003471, A007016.

Programs

Maple

b:= proc(s, i, t) option remember; (n-> `if`(n=0, 1, add(
      (h-> `if`(abs(h) b({$1..n}, 1, 0):
seq(a(n), n=0..15);  # Alois P. Heinz, Jun 26 2020

Mathematica

b[s_, i_, t_] := b[s, i, t] = Function[n, If[n == 0, 1, Sum[Function[h, If[Abs[h]Jean-François Alcover, Nov 30 2020, after Alois P. Heinz *)

R

AT<-function(T){ #Returns a(n)
perm<-function(v){ #Returns all n! P[n]
n <- length(v)
if (n == 1) v
else{
X <- NULL
for (i in 1:n) X <- rbind(X, cbind(v[i], perm(v[-i])))
X}}
PN<-perm(1:T) #All P[n]
FN<-factorial(T)
PNn<-NULL
for (i in T:1){
PNn<-cbind(PNn,PN[,i])} #All -P[n]
PNO<-NULL
for (j in 1:T){
PNO<-cbind(PNO,rep(j,FN))} #Order
PNM<-matrix(0,FN,2)
for (k in 1:FN){
PNM[k,1]<-sum(PNO[k,]==PN[k,]) #m(P)
PNM[k,2]<-sum(PNO[k,]==PNn[k,])}#m(-P)
return(sum(PNM[,1]==PNM[,2]))} #Sum{m(P[n]) = m(-P[n])}

Extensions

a(11)-a(22) from Alois P. Heinz, Jun 25 2020