A002467 -id:A002467 - cp's OEIS frontend

A276975 Number of permutations of [n] such that the minimal distance between elements of the same cycle equals one, a(1)=1 by convention.

1, 1, 4, 19, 103, 651, 4702, 38413, 350559, 3539511, 39196758, 472612883, 6165080443, 86526834271, 1300282224846, 20832761552453, 354515666646827, 6386139146435035, 121406489336263622, 2429193186525638435, 51030147426536745655, 1122952442325988152627

Offset: 1

Alois P. Heinz, Sep 23 2016

nonn

			a(2) = 1: (1,2).
a(3) = 4: (1,2,3), (1,3,2), (1)(2,3), (1,2)(3).

Alois P. Heinz, Table of n, a(n) for n = 1..50
Per Alexandersson et al., d-regular partitions and permutations, MathOverflow, 2014

Column k=1 of A276974.

Cf. A002467, A180191, A277032.

b:= proc(n, i, l) option remember; `if`(n=0, mul(j!, j=l),
      (m-> add(`if`(i=j, 0, b(n-1, j, `if`(j>m, [l[], 0],
        subsop(j=l[j]+1, l)))), j=1..m+1))(nops(l)))
    end:
a:= n-> `if`(n=1, 1, n!-b(n, 0, [])):
seq(a(n), n=1..15);

b[n_, i_, l_] := b[n, i, l] = If[n == 0, Product[j!, {j, l}], Function[m, Sum[If[i == j, 0, b[n - 1, j, If[j > m, Append[l, 0], ReplacePart[l, j -> l[[j]] + 1]]]], {j, 1, m + 1}]][Length[l]]];
a[n_] := If[n == 1, 1, n! - b[n, 0, {}]];
Array[a, 15] (* Jean-François Alcover, Oct 28 2020, after Maple code *)

A028305 Triangle of numbers of permutations eliminating just k cards out of n in game of Mousetrap.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 2, 2, 0, 2, 9, 6, 3, 0, 6, 44, 31, 19, 11, 0, 15, 265, 180, 105, 54, 32, 0, 84, 1854, 1255, 771, 411, 281, 138, 0, 330, 14833, 9949, 6052, 3583, 2057, 1366, 668, 0, 1812, 133496, 89162, 55340, 32135, 19026, 12685, 6753, 4305, 0, 9978, 1334961, 886837, 547922, 331930, 193538, 117323, 79291, 45536, 25959, 0, 65503

Offset: 0

N. J. A. Sloane

Triangle T(n,k), 0 <= k <= n

			Triangle begins:
     1,
     0,    1,
     1,    0,   1,
     2,    2,   0,   2,
     9,    6,   3,   0,   6,
    44,   31,  19,  11,   0,  15,
   265,  180, 105,  54,  32,   0, 84,
  1854, 1255, 771, 411, 281, 138,  0, 330,
  ...

R. K. Guy, Unsolved Problems Number Theory, E37.
R. K. Guy and R. J. Nowakowski, "Mousetrap," in D. Miklos, V. T. Sos and T. Szonyi, eds., Combinatorics, Paul Erdős is Eighty. Bolyai Society Math. Studies, Vol. 1, pp. 193-206, 1993.
S. Washburn, T. Marlowe and C. T. Ryan, Discrete Mathematics, Addison-Wesley, 1999, page 326.

Georg Fischer, Table of n, a(n) for n = 0..107 (terms 36..65 from Martin Renner)
Arthur Cayley, On the game of Mousetrap, in: Quarterly Journal of Pure and Applied Mathematics 15 (1878), p. 8-10.
R. K. Guy and R. J. Nowakowski, Mousetrap, Preprint, Feb 10 1993 [Annotated scanned copy]
Adolph Steen, Some formulas respecting the game of Mousetrap, Quarterly Journal of Pure and Applied Mathematics 15 (1878), p. 230-241.

Cf. A000166, A007709, A007710.

A028305:=proc(n)
  local P, j, M, K, A, i, K_neu, k, m;
  P:=combinat[permute](n):
  for j from 0 to n do
    M[j]:=0:
  od:
  for j from 1 to nops(P) do
    K:=P[j]:
    A:=[]:
    for i while nops(K)>0 do
      K_neu:=[]:
      for k from 1 to n do
        m:=nops(K);
        if k mod m = 0 then
          if K[m]=k then
            K_neu:=[seq(K[j],j=1..m-1)];
            A:=[op(A),k];
          else next;
          fi;
        else
          if K[k mod m]=k then
            K_neu:=[seq(K[j],j=(k mod m)+1..m),seq(K[j],j=1..(k mod m)-1)];
            A:=[op(A),k];
          else next;
          fi;
        fi;
        if nops(K_neu)<>0 then break; fi;
      od;
      if nops(K_neu)<>0 then
        K:=K_neu;
      else break;
      fi;
    od:
    M[nops(A)]:=M[nops(A)]+1;
  od:
  seq(M[j],j=0..n);
end:
# Martin Renner, Sep 03 2015

T(n,0) = A000166(n), T(n,1) = A007710(n), T(n,n-1) = A000004(n) = 0, T(n,n) = A007709(n).

a(36)-a(65) from Martin Renner, Sep 02 2015

A209325 Number of permutations of [n] with a succession but no fixed points.

Original entry on oeis.org

0, 0, 0, 2, 5, 30, 163, 1172, 9349, 84208, 842149, 9266416, 111220875, 1446134218, 20248984181, 303774206310, 4860923772369, 82643503648838, 1487703851220935, 28268359232622252, 565401755237435337, 11874072125853230504, 261241878854832755345, 6008813069875360106928, 144216837237680799509479, 3605539586383814138649074

Offset: 0

Jon Perry, Jan 19 2013

nonn

A succession of a permutation p is a position i such that p(i+1)-p(i) = 1.

			For n=4 we have 2341, 3412, 3421, 4123 and 4312.

Max Alekseyev, Table of n, a(n) for n = 0..30

Cf. A000166, A002467, A180191, A207819, A207821, A209322, A209326.

a(n) = A000166(n) - A209322(n).

a(11)-a(14) from Alois P. Heinz, Jan 20 2013
a(15)-a(20) from Max Alekseyev, Oct 17 2017
a(21)-a(22) from Alois P. Heinz, Jul 05 2021
Terms a(23) onward from Max Alekseyev, Apr 03 2025

A209326 Number of permutations of [n] with a fixed point but no succession.

Original entry on oeis.org

0, 1, 0, 3, 7, 39, 207, 1437, 11203, 99041, 975645, 10601377, 125905445, 1622349059, 22539777113, 335845307359, 5341990288103, 90340567900583, 1618553943500599, 30623660893656205, 610152486797080443, 12769086757046132625, 280037186109883699885, 6422309829486480886809, 153727262708736577446741, 3833789797689152809143363

Offset: 0

Jon Perry, Jan 19 2013

nonn

A succession of a permutation p is a position i such that p(i+1)-p(i) = 1.

			For n=4 we have 1324, 1432, 2431, 3214, 3241, 4132 and 4213.

Max Alekseyev, Table of n, a(n) for n = 0..30

Cf. A000166, A000255, A002467, A180191, A207819, A207821, A209322, A209325.

a(n) = A000255(n-1) - A209322(n). - Max Alekseyev, Apr 03 2025

a(11)-a(14) from Alois P. Heinz, Jan 20 2013
a(15)-a(21) from Alois P. Heinz, Jul 04 2021
Terms a(22) onward from Max Alekseyev, Apr 03 2025

A007710 From the game of Mousetrap.

Original entry on oeis.org

1, 0, 2, 6, 31, 180, 1255, 9949, 89162, 886837, 9722814, 116236256, 1507191024, 21042127239

Offset: 1

N. J. A. Sloane

nonn

R. K. Guy and R. J. Nowakowski, "Mousetrap," in D. Miklos, V. T. Sos and T. Szonyi, eds., Combinatorics, Paul Erdős is Eighty. Bolyai Society Math. Studies, Vol. 1, pp. 193-206, 1993.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Arthur Cayley, On the game of Mousetrap, Quarterly Journal of Pure and Applied Mathematics 15 (1878), p. 8-10.
R. K. Guy and R. J. Nowakowski, Mousetrap, Preprint, Feb 10 1993 [Annotated scanned copy]
Adolph Steen, Some formulas respecting the game of Mousetrap, Quarterly Journal of Pure and Applied Mathematics 15 (1878), p. 230-241.

Cf. A028305.

a(n) = A028305((1/2)*(n+1)*(n+2)-n+1). - Martin Renner, Sep 03 2015

a(10) from Martin Renner, Sep 02 2015

a(11)-a(14) from Sean A. Irvine, Jan 17 2018

A028306 Triangle read by rows of numbers of permutations eliminating just card k out of n in game of Mousetrap.

Original entry on oeis.org

1, 0, 0, 1, 0, 1, 2, 1, 1, 2, 9, 5, 5, 3, 9, 44, 31, 25, 20, 16, 44, 265, 203, 167, 142, 117, 96, 265, 1854, 1501, 1267, 1075, 932, 791, 675, 1854, 14833, 12449, 10745, 9311, 8241, 7132, 6205, 5413, 14833, 133496, 114955, 101005, 88993, 78607, 70340, 62141

Offset: 0

N. J. A. Sloane

R. K. Guy, Unsolved Problems Number Theory, E37.
R. K. Guy and R. J. Nowakowski, "Mousetrap," in D. Miklos, V. T. Sos and T. Szonyi, eds., Combinatorics, Paul Erdős is Eighty. Bolyai Society Math. Studies, Vol. 1, pp. 193-206, 1993.

R. K. Guy and R. J. Nowakowski, Mousetrap, Preprint, Feb 10 1993 [Annotated scanned copy]

Diagonals include A000166, A002469. Cf. A028305.

A061018 Triangle: a(n,m) = number of permutations of (1,2,...,n) with one or more fixed points in the m first positions.

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 6, 10, 13, 15, 24, 42, 56, 67, 76, 120, 216, 294, 358, 411, 455, 720, 1320, 1824, 2250, 2612, 2921, 3186, 5040, 9360, 13080, 16296, 19086, 21514, 23633, 25487, 40320, 75600, 106560, 133800, 157824, 179058, 197864, 214551, 229384

Offset: 1

Wouter Meeussen, May 23 2001

Row sums of n are the number of derangements (permutations without fixed point) of n+1, i.e. A000166(n+1).

			For n=3, the permutations are (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1); and (x, 2, 3), (x, 3, 2) have a fixed point x in position 1, (x, x, 3), (x, 3, 2), (3, x, 1) have a fixed point x in positions 1 or 2 and (x, x, x), (2, 1, x), (x, 3, 2), (3, x, 1) have a fixed point x in positions 1, 2 or 3, hence {2, 3, 4}
{1},
{1, 1},
{2, 3, 4},
{6, 10, 13, 15},
{24, 42, 56, 67, 76},
{120, 216, 294, 358, 411, 455},
{720, 1320, 1824, 2250, 2612, 2921, 3186}, ...

Columns: A000142, A007680, A002467, A180191.

A061018 := proc(n,m): (n-1)! + add(A061312(n-2,k), k=0..m-2) end: A061312:= proc(n,m): if m=-1 then 0 elif m=0 then n*n! else procname(n,m-1) - procname(n-1,m-1) fi: end: seq(seq(A061018(n,m), m=1..n), n=1..8); # Johannes W. Meijer, Jul 27 2011
T := (n, k) -> `if`(n=k,n!-GAMMA(n+1,-1)/exp(1),n!*(1-hypergeom([-k],[-n],-1))):
for n from 1 to 9 do seq(simplify(T(n,k)), k=1..n) od; # Peter Luschny, Oct 03 2017

Table[Count[Permutations[Range[n]], p_/;( Times@@Take[(p-Range[n]), k]===0)], {n, 7}, {k, n}]

a(n,m) = (n-1)! + Sum_{k=0..m-2} T(n-2, k) where T(n,-1) = 0, T(0,0) = 0, T(n,0) = A001563(n) = n*n!, T(n,m) = T(n,m-1) - T(n-1,m-1) (see A061312).

T(n, k) = n!*(1 - hypergeom([-k], [-n], -1)) for 1 <= k < n and T(n, n) = n! -Gamma(n+1, -1)/exp(1). - Peter Luschny, Oct 03 2017

Edited and information added by Johannes W. Meijer, Jul 27 2011

A178517 Triangle read by rows: T(n,k) is the number of non-derangement permutations of {1,2,...,n} having genus k (see first comment for definition of genus).

Original entry on oeis.org

1, 1, 0, 4, 0, 0, 11, 4, 0, 0, 36, 40, 0, 0, 0, 117, 290, 48, 0, 0, 0, 393, 1785, 1008, 0, 0, 0, 0, 1339, 9996, 12712, 1440, 0, 0, 0, 0, 4630, 52584, 123858, 48312, 0, 0, 0, 0, 0, 16193, 264720, 1027446, 904840, 80640, 0, 0, 0, 0, 0, 57201, 1290135, 7627158, 12449800, 3807936, 0

Offset: 1

Emeric Deutsch, May 30 2010

The genus g(p) of a permutation p of {1,2,...,n} is defined by g(p)=(1/2)[n+1-z(p)-z(cp')], where p' is the inverse permutation of p, c = 234...n1 = (1,2,...,n), and z(q) is the number of cycles of the permutation q.
The sum of the entries in row n is A002467(n).
The number of entries in row n is floor(n/2).
T(n,0) = A106640(n-1) .

			T(3,0)=4 because all non-derangements of {1,2,3}, namely 123=(1)(2)(3), 132=(1)(23), 213=(12)(3), and 321=(13)(2) have genus 0. This follows easily from the fact that a permutation p of {1,2,...,n} has genus 0 if and only if the cycle decomposition of p gives a noncrossing partition of {1,2,...,n} and each cycle of p is increasing (see Lemma 2.1 of the Dulucq-Simion reference).
Triangle starts:
[ 1]  1,
[ 2]  1, 0,
[ 3]  4, 0, 0,
[ 4]  11, 4, 0, 0,
[ 5]  36, 40, 0, 0, 0,
[ 6]  117, 290, 48, 0, 0, 0,
[ 7]  393, 1785, 1008, 0, 0, 0, 0,
[ 8]  1339, 9996, 12712, 1440, 0, 0, 0, 0,
[ 9]  4630, 52584, 123858, 48312, 0, 0, 0, 0, 0,
[10]  16193, 264720, 1027446, 904840, 80640, 0, 0, 0, 0, 0,
[11]  57201, 1290135, 7627158, 12449800, 3807936, 0, 0, 0, 0, 0, 0,
[12]  203799, 6133930, 52188774, 140356480, 96646176, 7257600, 0, ...,
[13]  731602, 28603718, 335517468, 1373691176, 1749377344, 448306560, 0, ...,
...

S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8 (1998), 169-191.

Cf. A177267 (genus of all permutations).
Cf. A178514 (genus of derangements), A178515 (genus of involutions), A178516 (genus of up-down permutations), A178518 (permutations of [n] having genus 0 and p(1)=k), A185209 (genus of connected permutations).
Cf. A002467, A106640.

n := 7: with(combinat): P := permute(n): inv := proc (p) local j, q: for j to nops(p) do q[p[j]] := j end do: [seq(q[i], i = 1 .. nops(p))] end proc: nrfp := proc (p) local ct, j: ct := 0: for j to nops(p) do if p[j] = j then ct := ct+1 else end if end do: ct end proc: nrcyc := proc (p) local pc: pc := convert(p, disjcyc): nops(pc)+nrfp(p) end proc: b := proc (p) local c: c := [seq(i+1, i = 1 .. nops(p)-1), 1]: [seq(c[p[j]], j = 1 .. nops(p))] end proc: gen := proc (p) options operator, arrow: (1/2)*nops(p)+1/2-(1/2)*nrcyc(p)-(1/2)*nrcyc(b(inv(p))) end proc: NDER := {}: for i to factorial(n) do if nrfp(P[i]) > 0 then NDER := `union`(NDER, {P[i]}) else end if end do: f[n] := sort(add(t^gen(NDER[j]), j = 1 .. nops(NDER))): seq(coeff(f[n], t, j), j = 0 .. floor((1/2)*n)-1); # yields the entries in the specified row n

Terms beyond row 7 from Joerg Arndt, Nov 01 2012.

A201452 Number of permutations of [n] with both a fixed point and a succession.

Original entry on oeis.org

0, 0, 1, 1, 8, 37, 248, 1749, 14284, 130343, 1318194, 14630853, 176881314, 2313878809, 32567413038, 490762544907, 7883735348152, 134496767915753, 2428518101193448, 46270707955530689, 927734890186657436

Offset: 0

Jon Perry, Jan 09 2013

A succession of a permutation p is the appearance of [k,k+1], e.g. in 23541, 23 is a succession.

			a(4) = 8 because we have 1234, 1243, 1342, 1423, 2134, 2314, 3124 and 4231.

Cf. A002467, A180191, A207819, A207821.

A201452(n)=my(p,c);sum(k=1,n!,p=numtoperm(n,k);c=(p[1]==1);for(j=2,n,p[j]==j&c!=1&c++==3&break;p[j]-1==p[j-1]&c!=2&(c+=2)==3&break);c==3) \\ - M. F. Hasler, Jan 13 2013

Values a(1..10) double-checked by M. F. Hasler, Jan 13 2013
a(11)-a(13) from Alois P. Heinz, Jan 18 2013
a(14)-a(20) from Alois P. Heinz, Jul 06 2021

A296050 Number of permutations p of [n] such that min_{j=1..n} |p(j)-j| = 1.

Original entry on oeis.org

0, 0, 1, 2, 8, 40, 236, 1648, 13125, 117794, 1175224, 12903874, 154615096, 2007498192, 28075470833, 420753819282, 6726830163592, 114278495205524, 2055782983578788, 39039148388975552, 780412763620655061, 16381683795665956242, 360258256118419518680, 8283042472303599966974

Offset: 0

Alois P. Heinz, Jan 21 2019

nonn

			a(2) = 1: 21.
a(3) = 2: 231, 312.
a(4) = 8: 2143, 2341, 2413, 3142, 3421, 4123, 4312, 4321.
a(5) = 40: 21453, 21534, 23154, 23451, 23514, 24153, 24513, 24531, 25134, 25413, 25431, 31254, 31452, 31524, 34152, 34251, 35124, 35214, 35412, 35421, 41253, 41523, 41532, 43152, 43251, 43512, 43521, 45132, 45213, 45231, 51234, 51423, 51432, 53124, 53214, 53412, 53421, 54132, 54213, 54231.

Alois P. Heinz, Table of n, a(n) for n = 0..450

Column k=1 of A299789.

Cf. A000142, A000166, A001883, A002467, A016933, A047252, A323671.

b:= proc(s, k) option remember; (n-> `if`(n=0, `if`(k=1, 1, 0), add(
      `if`(n=j, 0, b(s minus {j}, min(k, abs(n-j)))), j=s)))(nops(s))
    end:
a:= n-> b({$1..n}, n):
seq(a(n), n=0..14);
# second Maple program:
a:= n-> (f-> f(1)-f(2))(k-> `if`(n=0, 1, LinearAlgebra[Permanent](
        Matrix(n, (i, j)-> `if`(abs(i-j)>=k, 1, 0))))):
seq(a(n), n=0..14);
# third Maple program:
g:= proc(n) g(n):= `if`(n<2, 1-n, (n-1)*(g(n-1)+g(n-2))) end:
h:= proc(n) h(n):= `if`(n<7, [1, 0$3, 1, 4, 29][n+1], n*h(n-1)+4*h(n-2)
      -3*(n-3)*h(n-3)+(n-4)*h(n-4)+2*(n-5)*h(n-5)-(n-7)*h(n-6)-h(n-7))
    end:
a:= n-> g(n)-h(n):
seq(a(n), n=0..25);

g[n_] := g[n] = If[n < 2, 1-n, (n-1)(g[n-1] + g[n-2])];
h[n_] := h[n] = If[n < 7, {1, 0, 0, 0, 1, 4, 29}[[n+1]],
     n h[n-1] + 4h[n-2] - 3(n-3)h[n-3] + (n-4)h[n-4] +
     2(n-5)h[n-5] - (n-7)h[n-6] - h[n-7]];
a[n_] := g[n] - h[n];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Aug 30 2021, after third Maple program *)

a(n) = A000142(n) - A001883(n) - A002467(n).
a(n) = A000166(n) - A001883(n).
a(n) = Sum_{k=1..n} A323671(n,k).
a(n) is odd <=> n in { A016933 }.
a(n) is even <=> n in { A047252 }.

cp's OEIS Frontend

A276975 Number of permutations of [n] such that the minimal distance between elements of the same cycle equals one, a(1)=1 by convention.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A028305 Triangle of numbers of permutations eliminating just k cards out of n in game of Mousetrap.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

Extensions

A209325 Number of permutations of [n] with a succession but no fixed points.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A209326 Number of permutations of [n] with a fixed point but no succession.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A007710 From the game of Mousetrap.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A028306 Triangle read by rows of numbers of permutations eliminating just card k out of n in game of Mousetrap.

Views

Author

Keywords

References

Links

Crossrefs

A061018 Triangle: a(n,m) = number of permutations of (1,2,...,n) with one or more fixed points in the m first positions.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A178517 Triangle read by rows: T(n,k) is the number of non-derangement permutations of {1,2,...,n} having genus k (see first comment for definition of genus).

Views

Author

Keywords

Comments

Examples

References

Crossrefs