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,5

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.

References

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

Links

Table of n, a(n) for n=0..22.

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).

Example

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.

Maple

b:= proc(s, i, t) option remember; (n-> `if`(n=0, 1, add(
      (h-> `if`(abs(h)<n, b(s minus {j}, i+1, h), 0))(t+
      `if`(j=i, 1, 0)-`if`(j=n, 1, 0)), j=s)))(nops(s))
    end:
a:= n-> 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]<n, b[s ~Complement~ {j}, i + 1, h], 0]][t + If[j == i, 1, 0] - If[j == n, 1, 0]], {j, s}]]][Length[s]];
a[n_] := b[Range[n], 1, 0];
a /@ Range[0, 15] (* Jean-François Alcover, Nov 30 2020, after Alois P. Heinz *)

Prog

(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])}

Crossrefs

Cf. A000142, A000166, A003471, A007016.

Sequence in context: A242582 A242583 A335676 * A159450 A243040 A243041

Adjacent sequences: A334827 A334828 A334829 * A334831 A334832 A334833

Keyword

nonn

Author

Michael Cader Nelson, Jun 24 2020

Extensions

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

Status

approved