Michael Cader Nelson - cp's OEIS frontend

User: Michael Cader Nelson

Michael Cader Nelson has authored 2 sequences.

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

Michael Cader Nelson, Jun 24 2020

nonn

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.

			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.

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

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

Cf. A000142, A000166, A003471, A007016.

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

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

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

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

A276357 Primes of the form (p*2^x-1)/3, where p is also prime and x is a positive integer.

Original entry on oeis.org

3, 5, 7, 11, 13, 17, 19, 29, 31, 37, 41, 47, 53, 59, 61, 67, 71, 89, 97, 101, 109, 127, 131, 137, 149, 151, 157, 167, 179, 181, 197, 211, 229, 239, 241, 257, 269, 277, 281, 307, 311, 347, 349, 379, 389, 397, 409, 421, 431, 439, 449, 461, 467, 479, 509, 547, 571, 577, 587

Offset: 1

Michael Cader Nelson, Aug 31 2016

nonn

Relationship to Collatz (3x+1) problem: when one of these primes appears in a hailstone sequence, the next odd number in the sequence must be prime. - Michael Cader Nelson, Jul 03 2020

			3 is in the sequence because 3 = (5*2^1-1)/3 and both 3 and 5 are prime numbers; while 23 is not in the sequence because the only positive integer values (p,x) to give 23 are (35,1) and 35 is not prime.

Cf. A087273, A087963. A177330 (lists all exponents x).

mx = 590; Select[ Sort@ Flatten@ Table[(Prime[p]*2^x - 1)/3, {x, Log2[mx/3]}, {p, PrimePi[3 mx/2^x]}], PrimeQ] (* Robert G. Wilson v, Nov 01 2016 *)

lista(nn) = {forprime(p=2, nn, z = 3*p+1; x = valuation(z, 2); for (ex = 1, x, if (isprime(z/2^ex), print1(p, ", "); break;);););} \\ Michel Marcus, Sep 01 2016

The value of p is (3*a(n)+1)/2^x as well as the respective term in A087273 evaluated for a(n), while the value of x is the related exponent in A087963 unless 3*a(n)+1 is a power of 2 (e.g., n = 1).

Corrected and extended by Michel Marcus, Sep 01 2016

cp's OEIS Frontend

User: Michael Cader Nelson

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

R

Extensions