A180191 -id:A180191 - cp's OEIS frontend

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

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

A180190 Triangle read by rows: T(n,k) is the number of permutations p of [n] for which k is the smallest among the positive differences p(i+1) - p(i); k=0 for the reversal of the identity permutation (0<=k<=n-1).

Original entry on oeis.org

1, 1, 1, 1, 3, 2, 1, 13, 6, 4, 1, 67, 30, 14, 8, 1, 411, 178, 80, 34, 16, 1, 2921, 1236, 530, 234, 86, 32, 1, 23633, 9828, 4122, 1744, 702, 226, 64, 1, 214551, 88028, 36320, 14990, 6094, 2154, 614, 128, 1, 2160343, 876852, 357332, 145242, 58468, 21842, 6750, 1714, 256

Offset: 1

Emeric Deutsch, Sep 07 2010

Terms obtained by counting with a time-consuming Maple program.
Sum of entries in row n = n! = A000142(n).
T(n,1) = A180191(n).

			T(4,2) = 6 because we have 1324, 4132, 2413, 4213, 2431, and 3241.
Triangle starts:
  1;
  1,  1;
  1,  3,  2;
  1, 13,  6,  4;
  1, 67, 30, 14,  8;
  ...

Alois P. Heinz, Rows n = 1..18, flattened

Cf. A000142, A018927, A180191.

with(combinat): minasc := proc (p) local j, b: for j to nops(p)-1 do if 0 < p[j+1]-p[j] then b[j] := p[j+1]-p[j] else b[j] := infinity end if end do: if min(seq(b[j], j = 1 .. nops(p)-1)) = infinity then 0 else min(seq(b[j], j = 1 .. nops(p)-1)) end if end proc; for n to 10 do P := permute(n): f[n] := sort(add(t^minasc(P[j]), j = 1 .. factorial(n))) end do: for n to 10 do seq(coeff(f[n], t, i), i = 0 .. n-1) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(s, l, m) option remember; `if`(s={}, x^`if`(m=infinity, 0, m),
      add(b(s minus {j}, j, `if`(j (p-> seq(coeff(p, x, i), i=0..n-1))(b({$1..n}, infinity$2)):
seq(T(n), n=1..10);  # Alois P. Heinz, Feb 21 2019

b[s_List, l_, m_] := b[s, l, m] = If[s == {}, x^If[m == Infinity, 0, m], Sum[b[s ~Complement~ {j}, j, If[j < l, m, Min[m, j - l]]], {j, s}]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n - 1}]][b[ Range[n], Infinity, Infinity]];
T /@ Range[10] // Flatten (* Jean-François Alcover, Dec 08 2019, after Alois P. Heinz *)

Sum_{k=0..n-1} k * T(n,k) = A018927(n). - Alois P. Heinz, Feb 21 2019

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

A193465 Row sums of triangle A061312.

Original entry on oeis.org

0, 2, 9, 52, 335, 2466, 20447, 189064, 1930959, 21603430, 262869959, 3457226268, 48880169351, 739429561066, 11918051268255, 203914545928336, 3691384616598047, 70491995143458894, 1416242276574905879, 29862732908481855460, 659413025994777460119

Offset: 0

Johannes W. Meijer, Jul 27 2011

a(n) = p(n+1) where p(x) is the unique degree-n polynomial such that p(k) = A001563(k) for k = 0, 1, ..., n. - Michael Somos, Jun 06 2012

			2*x + 9*x^2 + 52*x^3 + 335*x^4 + 2466*x^5 + 20447*x^6 + 189064*x^7 + ...

G. C. Greubel, Table of n, a(n) for n = 0..445

Cf. A000166, A001563, A002467, A047920, A061312, A180191, A074909.

A193465 := proc(n): add(A061312(n,k), k=0..n) end: A061312:=proc(n,k): add(((-1)^j)*binomial(k+1,j)*(n+1-j)!, j=0..k+1) end: seq(A193465(n), n=0..20);

a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ (1 + x - (1 + x^2) / Exp[ x ]) / (1 - x)^3, {x, 0, n}]] (* Michael Somos, Jun 06 2012 *)

{a(n) = if( n<0, 0, n! * polcoeff( (1 + x - (1 + x^2) / exp(x + x * O(x^n))) / (1 - x)^3, n))} /* Michael Somos, Jun 06 2012 */

a(n) = Sum_{k=0..n} A061312(n,k).
a(n) = (n+1)*A180191(n+1).
a(n) = A002467(n+2) - (n+1)! (the game of mousetrap with n cards).
a(n) = (n+1)*(n+1)! - A000166(n+2) (rencontres numbers).
a(n) = ((n-n^3)*a(n-3) + (2*n+n^2-n^3)*a(n-2) - (1-n-2*n^2)*a(n-1))/n with a(0) = 0, a(1) = 2 and a(2) = 9.
E.g.f: (1 + x - (1 + x^2) / exp(x)) / (1 - x)^3. - Michael Somos, Jun 06 2012
a(n) = Sum_{k=0..n} C(n+1,k)*A000166(k+1) = Sum_{k=0..n} A074909(n,k)*A000166(k+1). - Anton Zakharov, Sep 26 2016
a(n) = Sum_{k=1..n+1} A047920(n+1,k). - Alois P. Heinz, Sep 01 2021

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

Original entry on oeis.org

1, 1, 5, 20, 109, 668, 4801, 38894, 353811, 3561512, 39374609, 474132730, 6179650125, 86676293916, 1301952953989, 20852719565694, 354771488612075, 6389625786835184, 121456993304945749, 2429966790591643402, 51042656559451380013, 1123165278137918510772

Offset: 1

Alois P. Heinz, Sep 25 2016

nonn

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

Per Alexandersson et al., d-regular partitions and permutations, MathOverflow, 2014

Column k=1 of A277031.

Cf. A002467, A180191, A276975.

b:= proc(n, i, l) option remember; `if`(n=0, mul(j!, j=l),
      (m-> add(`if`(i=j or n*j=1, 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-1, 1, [0])):
seq(a(n), n=1..15);

b[n_, i_, l_] := b[n, i, l] = If[n == 0, Product[j!, {j, l}], With[{m = Length[l]}, Sum[If[i == j || n*j == 1, 0, b[n-1, j, If[j>m, Append[l, 0], ReplacePart[l, j -> l[[j]]+1]]]], {j, 1, m+1}]]];
a[n_] := If[n == 1, 1, n! - b[n-1, 1, {0}]];
Array[a, 15] (* Jean-François Alcover, Mar 13 2021, after Alois P. Heinz *)

A306511 Number of permutations p of [n] having at least one index i with |p(i)-i| = 1.

Original entry on oeis.org

0, 0, 1, 4, 19, 99, 603, 4248, 34115, 307875, 3085203, 33993870, 408482695, 5316309607, 74499953255, 1118421967520, 17907571955927, 304619809031127, 5486197279305911, 104289196264058030, 2086706157642260387, 43838287730208552691, 964790364323910060691

Offset: 0

Alois P. Heinz, Feb 20 2019

nonn

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

Column k=1 of A306506.

Cf. A000142, A078480, A180191.

a:= proc(n) option remember; `if`(n<5, [0$2, 1, 4, 19][n+1],
      (2*(n^3-8*n^2+20*n-14)*a(n-1)-(n-4)*(n-1)*(n^2-5*n+7)*
       a(n-2)-(n-2)*(n^2-7*n+13)*a(n-3)+(n^4-12*n^3+53*n^2
       -102*n+71)*a(n-4)+(n-4)*(n^2-5*n+7)*a(n-5))/(n^2-7*n+13))
    end:
seq(a(n), n=0..23);

a[n_] := n! - Sum[Sum[(-1)^k (i-k)! Binomial[2i-k, k], {k, 0, i}],
     {i, 0, n}];
a /@ Range[0, 23] (* Jean-François Alcover, May 03 2021, after Vaclav Kotesovec in A078480 *)

a(n) = n! - A078480(n).

A345462 Triangle T(n,k) (n >= 1, 0 <= k <= n-1) read by rows: number of distinct permutations after k steps of the "first transposition" algorithm.

Original entry on oeis.org

1, 2, 1, 6, 3, 1, 24, 13, 4, 1, 120, 67, 23, 5, 1, 720, 411, 146, 36, 6, 1, 5040, 2921, 1067, 272, 52, 7, 1, 40320, 23633, 8800, 2311, 456, 71, 8, 1, 362880, 214551, 81055, 21723, 4419, 709, 93, 9, 1, 3628800, 2160343, 825382, 224650, 46654, 7720, 1042, 118, 10, 1

Offset: 1

Olivier Gérard, Jun 20 2021

The first transposition algorithm is: if the permutation is sorted, then exit; otherwise, exchange the first unsorted letter with the letter currently at its index. Repeat.
At each step at least 1 letter (possibly 2) is sorted.
If one counts the steps necessary to reach the identity, this gives the Stirling numbers of the first kind (reversed).

			Triangle begins:
      1;
      2,     1;
      6,     3,    1;
     24,    13,    4,    1;
    120,    67,   23,    5,   1;
    720,   411,  146,   36,   6,  1;
   5040,  2921, 1067,  272,  52,  7, 1;
  40320, 23633, 8800, 2311, 456, 71, 8, 1;
  ...

D. E. Knuth, The Art of Computer Programming, Vol. 3 / Sorting and Searching, Addison-Wesley, 1973.

Alois P. Heinz, Rows n = 1..150, flattened

Cf. A321352, A345461 (same idea for other sorting algorithms).
Cf. A180191 (second column, k=1).
Cf. A107111 a triangle with some common parts.
Cf. A143689 (diagonal T(n,n-3)).
Cf. A000142, A000166, A000255, A000274, A000313, A010027, A123513.

b:= proc(n, k) option remember; (k+1)!*
      binomial(n, k)*add((-1)^i/i!, i=0..k+1)/n
    end:
T:= proc(n, k) option remember;
     `if`(k=0, n!, T(n, k-1)-b(n, n-k+1))
    end:
seq(seq(T(n, k), k=0..n-1), n=1..10);  # Alois P. Heinz, Aug 11 2021

b[n_, k_] := b[n, k] = (k+1)!*Binomial[n, k]*Sum[(-1)^i/i!, {i, 0, k+1}]/n;
T[n_, k_] := T[n, k] = If[k == 0, n!, T[n, k-1] - b[n, n-k+1]];
Table[Table[T[n, k], {k, 0, n - 1}], {n, 1, 10}] // Flatten (* Jean-François Alcover, Mar 06 2022, after Alois P. Heinz *)

T(n,0) = n!; T(n,n-3) = (3*(n-1)^2 - n + 3)/2.
From Alois P. Heinz, Aug 11 2021: (Start)
T(n,k) = T(n,k-1) - A010027(n,n-k) for k >= 1.
T(n,k) - T(n,k+1) = A123513(n,k).
T(n,0) - T(n,1) = A000255(n-1) for n >= 2.
T(n,1) - T(n,2) = A000166(n) for n >= 3.
T(n,2) - T(n,3) = A000274(n) for n >= 4.
T(n,3) - T(n,4) = A000313(n) for n >= 5. (End)

A193364 Number of permutations that have a fixed point and contain 123.

Original entry on oeis.org

0, 0, 0, 1, 1, 3, 11, 59, 369, 2665, 21823, 199983, 2028701, 22577141, 273551115, 3585133147, 50540288857, 762641865009, 12265883397719, 209475278413895, 3785852926650453, 72191462591370733, 1448516763956727331, 30507960955933725171, 672958104387944656145

Offset: 0

Jon Perry, Dec 20 2012

nonn

A000142(n-2) gives number of permutations with a 123 present.

It appears that a(n) = A180191(n-2) - A018934(n-3) for n>3.

			For n=5 we have 12345, 12354 and 41235, so a(5)=3.
For n=6 we have 123456, 123465, 123546, 123465, 123645, 123654, 412356, 451236, 512346, 541236 and 612354, so a(6)=11.

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

Cf. A000142, A002467, A018934.

a:= proc(n) option remember;
      `if`(n<7, [0$3, 1$2, 3, 11][n+1],
       ((4*n^3-42*n^2+92*n+39) *a(n-1)
        +(32*n^3-2*n^4-163*n^2+223*n+204) *a(n-2)
        -(n-4)*(n-7)*(2*n^2-10*n-15) *a(n-3)) / (2*n^2-14*n-3))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 07 2013

a[n_] := a[n] = If[n<7, {0, 0, 0, 1, 1, 3, 11}[[n+1]], ((4n^3 - 42n^2 + 92n + 39) a[n-1] + (32n^3 - 2n^4 - 163n^2 + 223n + 204) a[n-2] - (n-4)(n-7) (2n^2 - 10n - 15) a[n-3])/(2n^2 - 14n - 3)];
a /@ Range[0, 30] (* Jean-François Alcover, Mar 15 2021, after Alois P. Heinz *)

A209256 Number of permutations of [n] that contain at least two fixed points in a succession.

Original entry on oeis.org

0, 0, 1, 1, 4, 18, 93, 579, 4165, 34031, 311528, 3158978, 35154907, 426029455, 5585287179, 78767551059, 1189090451364, 19133023344034, 326894939779865, 5910529926220115, 112753567098061553, 2263304875358959543, 47687055915645538384, 1052290471481700378570

Offset: 0

Jon Perry, Jan 14 2013

nonn

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

			For n=4 we have 1234, 1243, 4231 and 2134 so a(4) = 4.

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

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

a:= proc(n) option remember; `if`(n<6, [0, 0, 1, 1, 4, 18][n+1],
      ((2*n^3-43-17*n^2+47*n) *a(n-1)
       -(n-2)*(n^3-13*n^2+50*n-59) *a(n-2)
       -(n-3)*(3*n^3-28*n^2+82*n-78) *a(n-3)
       +(-219*n^2-4*n^4+49*n^3-305+425*n) *a(n-4)
       -(n-4)*(3*n^3-25*n^2+66*n-57) *a(n-5)
       -(n-4)*(n-5)*(n-2)^2 *a(n-6)) / (n-3)^2)
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jan 15 2013

a[n_] := a[n] = If[n<6, {0, 0, 1, 1, 4, 18}[[n+1]],
     ((2n^3 - 43 - 17n^2 + 47n) a[n-1]
     -(n-2)(n^3 - 13n^2 + 50n - 59) a[n-2]
     -(n-3)(3n^3 - 28n^2 + 82n - 78) a[n-3]
     +(-219n^2 - 4n^4 + 49n^3 - 305 + 425n) a[n-4]
     -(n-4)(3n^3 - 25n^2 + 66n - 57) a[n-5]
     -(n-4)(n-5)(n-2)^2 a[n-6])/(n-3)^2];
a /@ Range[0, 25] (* Jean-François Alcover, Mar 15 2021, after Alois P. Heinz *)

a(n) ~ (n-1)! * (1 - 3/(2*n) + 2/(3*n^2) + 47/(24*n^3) - 49/(120*n^4) - 6421/(720*n^5) - 17183/(1260*n^6)). - Vaclav Kotesovec, Mar 17 2015

Extended beyond a(10) by Alois P. Heinz, Jan 15 2013

A345464 Second column of A345461 - Number of distinct permutations after one step of the "optimist" sorting algorithm.

Original entry on oeis.org

1, 1, 6, 38, 232, 1607, 12984, 117513, 1182540, 13060248, 157314056, 2051314949

Offset: 2

Olivier Gérard, Jun 20 2021

Cf. A345453, A345461.
Cf. A000166 (equivalent for Eulerian numbers).
Cf. A180191 (equivalent for Stirling numbers of the first kind).

a(11)-a(13) from Pontus von Brömssen, Jun 29 2021

cp's OEIS Frontend

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

A180190 Triangle read by rows: T(n,k) is the number of permutations p of [n] for which k is the smallest among the positive differences p(i+1) - p(i); k=0 for the reversal of the identity permutation (0<=k<=n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions

A193465 Row sums of triangle A061312.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A306511 Number of permutations p of [n] having at least one index i with |p(i)-i| = 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A345462 Triangle T(n,k) (n >= 1, 0 <= k <= n-1) read by rows: number of distinct permutations after k steps of the "first transposition" algorithm.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica