A003471 -id:A003471 - cp's OEIS frontend

A335872 Number T(n,k) of permutations of [n] having k points that are fixed or reflected; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 0, 2, 0, 4, 0, 2, 4, 0, 16, 0, 4, 16, 36, 32, 32, 0, 4, 80, 192, 216, 128, 96, 0, 8, 672, 1472, 1440, 984, 320, 144, 0, 8, 4752, 10752, 11776, 7680, 3936, 1024, 384, 0, 16, 48768, 103568, 104448, 65920, 28544, 9312, 1792, 512, 0, 16

Offset: 0

Alois P. Heinz, Jun 28 2020

A permutation p of [n] has fixed point j if p(j) = j, it has reflected point j if p(n+1-j) = j. A point can be fixed and reflected at the same time.

			      1;
      0,      1;
      0,      0,      2;
      0,      4,      0,     2;
      4,      0,     16,     0,     4;
     16,     36,     32,    32,     0,    4;
     80,    192,    216,   128,    96,    0,    8;
    672,   1472,   1440,   984,   320,  144,    0,   8;
   4752,  10752,  11776,  7680,  3936, 1024,  384,   0, 16;
  48768, 103568, 104448, 65920, 28544, 9312, 1792, 512,  0, 16;
  ...

Alois P. Heinz, Rows n = 0..22, flattened
T. Simpson, Permutations with unique fixed and reflected points, Preprint. (Annotated scanned copy)
Wikipedia, Permutation

Column k=0 gives A003471.
Main diagonal gives A016116.
Row sums give A000142.
Cf. A008290, A335873.

b:= proc(s, i, t) option remember; (n-> `if`(n=0, x^t, add(
      b(s minus {j}, i+1, t+`if`(j in {i, n}, 1, 0)), j=s)))(nops(s))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b({$1..n}, 1, 0)):
seq(T(n), n=0..10);

b[s_, i_, t_] := b[s, i, t] = With[{n = Length[s]}, If[n == 0, x^t, Sum[b[s ~Complement~ {j}, i+1, t + If[j == i || j == n, 1, 0]], {j, s}]]];
T[n_] := CoefficientList[b[Range[n], 1, 0], x];
T /@ Range[0, 10] // Flatten (* Jean-François Alcover, Feb 13 2021, after Alois P. Heinz *)

Sum_{k=1..n} k * T(n,k) = A335873(n).

T(n,n-2) = floor((n-1)^2/2) * 2^floor(n/2).

A225740 Number of arrangements of n nonattacking Queens on an n X n board, with no Queens on both main diagonals.

Original entry on oeis.org

0, 0, 0, 2, 0, 4, 0, 12, 8, 12, 64, 760, 2080, 11524, 77672, 454376, 2972720, 19274208, 160500016, 1150812148, 9797154696, 79646705916, 771589104392

Offset: 1

Vaclav Kotesovec, Aug 04 2013

			From _Martin Ehrenstein_, Jan 10 2022: (Start)
Solutions for n=9 filtered from the Coserea link in A000170:
  3 5 8 2 9 7 1 4 6
  3 6 9 2 8 1 4 7 5
  4 6 9 3 1 8 2 5 7
  5 3 6 9 2 8 1 4 7
  5 7 4 1 8 2 9 6 3
  6 4 1 7 9 2 8 5 3
  7 4 1 8 2 9 6 3 5
  7 5 2 8 1 3 9 6 4
(End)

V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p.447
Vaclav Kotesovec, example, board 8x8, no queens on line a1-h8 and no queens on line a8-h1

Cf. A000170, A003471.

a(9)-a(19) corrected and extended with a(20)-a(23) by Martin Ehrenstein, Jan 10 2022

a(9)-a(19) confirmed by Vaclav Kotesovec, Jan 11 2022

A292080 Number of nonequivalent ways to place n non-attacking rooks on an n X n board with no rook on 2 main diagonals up to rotations and reflections of the board.

Original entry on oeis.org

1, 0, 0, 0, 2, 2, 14, 84, 630, 6096, 55336, 672160, 7409300, 104999520, 1366363752, 22068387264, 331233939624, 6005919062528, 102144359744192, 2054811316442112, 39053339674065360, 863259240785840640, 18132529836143846560, 436899062862222484480

Offset: 0

Andrew Howroyd, Sep 12 2017

nonn

For odd n, there are no symmetrical configurations of non-attacking rooks without a rook in the main diagonal, so a(2n+1) = A003471(2n+1) / 8. For even n, configurations with rotational and diagonal symmetry are possible.

			Case n=4: The 2 nonequivalent solutions are:
   _ x _ _     _ x _ _
   x _ _ _     _ _ _ x
   _ _ _ x     x _ _ _
   _ _ x _     _ _ x _
Case n=5: The 2 nonequivalent solutions are:
   _ x _ _ _   _ x _ _ _
   x _ _ _ _   _ _ _ _ x
   _ _ _ x _   x _ _ _ _
   _ _ _ _ x   _ _ x _ _
   _ _ x _ _   _ _ _ x _

Andrew Howroyd, Table of n, a(n) for n = 0..100
Andrew Howroyd, Nonequivalent and Symmetric Solutions

Cf. A000166, A000903, A003471, A037224, A053871, A064280.

sf[n_] := n! * SeriesCoefficient[Exp[-x ] / (1 - x), {x, 0, n}];
F[n_] := (Clear[v]; v[_] = 0; For[m = 4, m <= n, m++, v[m] = (m - 1)*v[m - 1] + 2*If[OddQ[m], (m - 1)*v[m - 2], (m - 2)*If[m == 4, 1, v[m - 4]]]]; v[n]);
d[n_] := Sum[(-1)^(n-k)*Binomial[n, k]*(2k)!/(2^k*k!), {k, 0, n}];
R[n_] := If[OddQ[n], 0, (n - 1)!*2/(n/2 - 1)!];
a[0] = 1; a[n_] := (F[n] + If[OddQ[n], 0, m = n/2; 2^m * sf[m] + 2*R[m] + 2*d[m]])/8;
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Dec 28 2017, after Andrew Howroyd *)

\\ here sf is A000166, F is A003471, D is A053871, R(n) is A037224(2n).
sf(n) = {n! * polcoeff( exp(-x + x * O(x^n)) / (1 - x), n)}
F(n) = {my(v = vector(n)); for(n=4,length(v),v[n]=(n-1)*v[n-1]+2*if(n%2==1,(n-1)*v[n-2],(n-2)*if(n==4,1,v[n-4]))); v[n]}
D(n) = {sum(k=0, n, (-1)^(n-k) * binomial(n,k) * (2*k)!/(2^k*k!))}
R(n) = {if(n%2==1, 0, (n-1)!*2/(n/2-1)!)}
a(n) = {(F(n) + if(n%2==1, 0, my(m=n/2); 2^m * sf(m) + 2*R(m) + 2*D(m)))/8}

a(2n+1) = A003471(2n+1) / 8, a(2n) = (A003471(2n) + 2^n * A000166(n) + 2*A037224(2*n) + 2*A053871(n)) / 8.

A322751 Number of directed graphs of 2*n vertices each having an in-degree and out-degree of 1 such that the graph specifies a pairwise connected gift exchange.

Original entry on oeis.org

1, 0, 4, 80, 4704, 436992, 58897920, 10880501760, 2640513576960, 814928486400000, 311763576754667520, 144816978675459686400, 80294888451877031116800, 52385405443881146567884800, 39727727942688305214337843200, 34656123210118214086941474816000

Offset: 0

Russell Y. Webb, Dec 25 2018

nonn

The sequence is the number of unique arrangements of directed graphs connecting 2*n vertices, where vertices occur in pairs, and meeting the following requirements:
1. Each vertex has an out-degree and in-degree of 1.
2. No edge connects vertices that are paired.
3. Starting with any pair, following the edges of paired vertices connects all vertices.
The requirements were chosen to yield a nice gift exchange between a set of couples. Acknowledgement to the additional members of the initial, inspirational gift exchange group: Cat, Brad, Kim, Ada, Graham, Nolan, and Leah.
The fraction of graphs meeting the requirements is approximately 0.12. Starting with n=2, the fractions are (0.166666667, 0.111111111, 0.116666667, 0.12042328, 0.122959756, 0.124807468). Is there a way to compute the percentage of graphs satisfying the condition in the limit as n approaches infinity?

			For n = 1, there is one pair; a(1) = 0 since requirements 1 and 2 can't be satisfied.
For n = 2, there are two pairs; a(2) = 4 graphs given by these edge destinations:
    ((2, 3), (1, 0))
    ((2, 3), (0, 1))
    ((3, 2), (1, 0))
    ((3, 2), (0, 1)).

Andrew Howroyd, Table of n, a(n) for n = 0..100

A322750 does not allow reciprocal connections.
A010050 is the number of graphs (2n)!.
Cf. A000316, A003471.

\\ Here B(n) gives A003471 as vector.
B(n)={my(v=vector(n+1)); v[1]=1; for(n=4, n, my(m = 2-n%2); v[n+1] = v[n]*(n-1) + 2*(n-m)*v[n-2*m+1]); v}
seq(n)={my(v=B(2*n)); Vec(serlaplace(1+log(sum(k=0, n, v[1+2*k]*x^k/k!, O(x*x^n)))))} \\ Andrew Howroyd, Jan 13 2024

from itertools import permutations as perm
def num_connected_by_pairs(assigned, here=0, seen=None):
    seen = (seen, set())[seen is None]
    for proposed in [(here - 1, here), (here, here + 1)][(here % 2) == 0]:
        if proposed not in seen:
            seen.add(proposed)
            num_connected_by_pairs(assigned, assigned[proposed], seen)
    return len(seen)
def valid(assigned, pairs):
    self_give = [assigned[i] == i for i in range(len(assigned))]
    same_pair = [assigned[i] == i + 1 or assigned[i+1] == i for i in range(0, 2*pairs, 2)]
    if pairs == 0 or True in self_give + same_pair:
        return False
    num_connected = [num_connected_by_pairs(assigned, here) for here in range(2, 2*pairs, 2)]
    return min(num_connected) == 2*pairs
print([len([x for x in perm(range(2*pairs)) if valid(x, pairs)]) for pairs in range(0, 6)])

E.g.f.: 1 + log(B(x)) where B(x) is the e.g.f. of A000316. - Andrew Howroyd, Jan 13 2024

a(0) changed to 1 and a(8) onwards from Andrew Howroyd, Jan 13 2024

A378907 Number of permutations of [n] with at least one hit on both main diagonals.

Original entry on oeis.org

0, 1, 0, 2, 10, 48, 270, 2004, 15406, 144656, 1399070, 15924940, 185817038, 2485431096, 33966603790, 522088434644, 8178526719550, 142034596036896, 2508925152633918, 48582127821078684, 955299461042098222, 20406401587894276040, 442067447198146300718

Offset: 0

Vikram Saraph, Dec 10 2024

For a permutation P, a hit on the leading diagonal is a fixed point P(i) = i and a hit on the opposite diagonal is a reverse P(i) = n+1 - i; and here P must have one or more of each.

Equivalently, a(n) is the number of ways to place n marks on an n X n grid so that there is at least one mark in every row and column and also in both of the main diagonals.

			For n = 3, the a(3) = 2 solutions are:
  X . .   . . X
  . X .   . X .
  . . X   X . .
For n = 4, one of a(4) = 10 solutions is:
  X . . .
  . . X .
  . X . .
  . . . X
All a(4) = 10 permutations of 1..4 counted are: 1324, 1342, 1423, 2314, 2431, 3124, 3241, 4132, 4213, 4231.

Cf. A000142, A000166, A002467, A003471.

\\ here B(n) gives first terms of A003471 as vector.
B(n)={my(a=vector(n+1)); a[1]=1; for(n=4, n, my(m=2-n%2); a[1+n] = (n-1)*a[n] + 2*(n-m)*a[1+n-2*m]); a}
seq(n)={Vec(serlaplace((1 - 2*exp(-x + O(x*x^n)))/(1-x)) + Ser(B(n)), -n-1)} \\ Andrew Howroyd, Dec 11 2024

def generate_A378907(n):
    f, A000166, A378907 = 6, 2, [0, 1, 0, 2]
    A003471 = [1, 0, 0, 0]
    for i in range(4, n):
        f *= i
        A000166 = i*A000166 + (1 if i%2==0 else -1)
        d, e = (2,4) if i%2==0 else (1,2)
        A003471.append((i-1)*A003471[-1] + 2*(i-d)*A003471[-e])
        A003471 = A003471[1:]
        s = f - 2*A000166 + A003471[-1]
        A378907.append(s)
    return A378907
A378907 = generate_A378907(23)  # Jwalin Bhatt, Dec 27 2024

a(n) = A000142(n) - 2*A000166(n) + A003471(n).

A259859 a(0)=0; thereafter A003470(n-1) + A003470(n) - 1.

Original entry on oeis.org

0, 1, 3, 10, 38, 177, 999, 6676, 51564, 451585, 4418555, 47746686, 564528978, 7247396065, 100378220943, 1491699317032, 23673159231704, 399553959924801, 7146023007880179, 134997604341408370, 2686037319660797310, 56143557248353416721, 1229914413684635491703

Offset: 0

N. J. A. Sloane, Jul 07 2015, based on a suggestion from John Riordan, Nov 14 1974

nonn

John Riordan and N. J. A. Sloane, Correspondence, 1974

Cf. A003470.

b:= proc(n) b(n):= `if`(n<2, 1, n*b(n-1)-b(n-2)+1+(-1)^n) end:
a:= n-> `if`(n=0, 0, b(n-1)+b(n)-1):
seq(a(n), n=0..22);  # Alois P. Heinz, Jun 17 2021

b[n_] := b[n] = If[n<2, 1, n*b[n-1] - b[n-2] + 1 + (-1)^n];
a[n_] := If[n == 0, 0, b[n-1] + b[n] - 1];
Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Dec 26 2022, after Alois P. Heinz *)

D-finite with recurrence: (-n+2)*a(n) +(n-1)^2*a(n-1) +2*(-n+2)*a(n-2) +(-n^2+4*n-2)*a(n-3) +(n-1)*a(n-4)=0. - R. J. Mathar, Jul 15 2015

Offset corrected by N. J. A. Sloane, Jun 16 2021

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

Original entry on oeis.org

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

cp's OEIS Frontend

A335872 Number T(n,k) of permutations of [n] having k points that are fixed or reflected; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A225740 Number of arrangements of n nonattacking Queens on an n X n board, with no Queens on both main diagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A292080 Number of nonequivalent ways to place n non-attacking rooks on an n X n board with no rook on 2 main diagonals up to rotations and reflections of the board.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A322751 Number of directed graphs of 2*n vertices each having an in-degree and out-degree of 1 such that the graph specifies a pairwise connected gift exchange.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions

A378907 Number of permutations of [n] with at least one hit on both main diagonals.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Python

Formula

A259859 a(0)=0; thereafter A003470(n-1) + A003470(n) - 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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