cp's OEIS Frontend

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

%I A334830 #38 Dec 06 2020 06:27:50
%S A334830 1,1,0,0,14,46,200,1496,11718,111558,1052272,12261712,140348300,
%T A334830 1915312460,25732919088,402510985872,6210501292870,109537725353798,
%U A334830 1908681625474400,37475105645783072,727818914470269924,15743598127274107044,337206399213040703920
%N A334830 a(n) is the number of permutations of length n that have the same number of fixed points whether forwards or backwards.
%C A334830 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?
%C A334830 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])?"
%C A334830 Equivalently, the probability that m(P[n]) = m(-P[n]) for a random permutation of length n equals a(n)/n!.
%C A334830 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.
%C A334830 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.
%D A334830 G. W. Allport and P. Vernon, Studies in expressive movement. New York: Macmillan, 1933.
%H A334830 C. D. Evans, J. Hughes, and J. Houston, <a href="https://doi.org/10.1348/000711002760554525">Significance-testing the validity of idiographic methods: A little derangement goes a long way</a>, British Journal of Mathematical and Statistical Psychology, 55(2), 385-390 (2002).
%H A334830 W. V. Li, F. Liu, and X. Shi, <a href="https://doi.org/10.1016/j.jmaa.2005.11.024">An analysis of the last round matching problem</a>, Journal of mathematical analysis and applications, 323(2), 1373-1382 (2006).
%H A334830 P. R. de Montmort, <a href="https://books.google.fr/books/about/Essay_d_analyse_sur_les_jeux_de_hazard.html?id=x6wgqvsHv6EC">Essay d’Analyse sur les Jeux de Hazard</a>, Chez Jacque Quillau, imprimeur-juré-libraire de l'Université, rue Galande, 1713 - 191 pages.
%H A334830 P. E. Vernon, <a href="https://doi.org/10.1037/h0056572">The evaluation of the matching method</a>, Journal of educational Psychology, 27(1), 1 (1936).
%e A334830 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.
%p A334830 b:= proc(s, i, t) option remember; (n-> `if`(n=0, 1, add(
%p A334830       (h-> `if`(abs(h)<n, b(s minus {j}, i+1, h), 0))(t+
%p A334830       `if`(j=i, 1, 0)-`if`(j=n, 1, 0)), j=s)))(nops(s))
%p A334830     end:
%p A334830 a:= n-> b({$1..n}, 1, 0):
%p A334830 seq(a(n), n=0..15);  # _Alois P. Heinz_, Jun 26 2020
%t A334830 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]];
%t A334830 a[n_] := b[Range[n], 1, 0];
%t A334830 a /@ Range[0, 15] (* _Jean-François Alcover_, Nov 30 2020, after _Alois P. Heinz_ *)
%o A334830 (R)
%o A334830 AT<-function(T){ #Returns a(n)
%o A334830 perm<-function(v){ #Returns all n! P[n]
%o A334830 n <- length(v)
%o A334830 if (n == 1) v
%o A334830 else{
%o A334830 X <- NULL
%o A334830 for (i in 1:n) X <- rbind(X, cbind(v[i], perm(v[-i])))
%o A334830 X}}
%o A334830 PN<-perm(1:T) #All P[n]
%o A334830 FN<-factorial(T)
%o A334830 PNn<-NULL
%o A334830 for (i in T:1){
%o A334830 PNn<-cbind(PNn,PN[,i])} #All -P[n]
%o A334830 PNO<-NULL
%o A334830 for (j in 1:T){
%o A334830 PNO<-cbind(PNO,rep(j,FN))} #Order
%o A334830 PNM<-matrix(0,FN,2)
%o A334830 for (k in 1:FN){
%o A334830 PNM[k,1]<-sum(PNO[k,]==PN[k,]) #m(P)
%o A334830 PNM[k,2]<-sum(PNO[k,]==PNn[k,])}#m(-P)
%o A334830 return(sum(PNM[,1]==PNM[,2]))} #Sum{m(P[n]) = m(-P[n])}
%Y A334830 Cf. A000142, A000166, A003471, A007016.
%K A334830 nonn
%O A334830 0,5
%A A334830 _Michael Cader Nelson_, Jun 24 2020
%E A334830 a(11)-a(22) from _Alois P. Heinz_, Jun 25 2020