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
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
KEYWORD
nonn
AUTHOR
Michael Cader Nelson, Jun 24 2020
EXTENSIONS
a(11)-a(22) from Alois P. Heinz, Jun 25 2020
STATUS
approved