A180191 -id:A180191 - cp's OEIS frontend

A306234 Number T(n,k) of occurrences of k in a (signed) displacement set of a permutation of [n] divided by |k|!; triangle T(n,k), n>=1, 1-n<=k<=n-1, read by rows.

1, 1, 1, 1, 1, 3, 4, 3, 1, 1, 5, 13, 15, 13, 5, 1, 1, 7, 28, 67, 76, 67, 28, 7, 1, 1, 9, 49, 179, 411, 455, 411, 179, 49, 9, 1, 1, 11, 76, 375, 1306, 2921, 3186, 2921, 1306, 375, 76, 11, 1, 1, 13, 109, 679, 3181, 10757, 23633, 25487, 23633, 10757, 3181, 679, 109, 13, 1

Offset: 1

Alois P. Heinz, Feb 17 2019

			Triangle T(n,k) begins:
  :                                 1                              ;
  :                           1,    1,    1                        ;
  :                     1,    3,    4,    3,    1                  ;
  :               1,    5,   13,   15,   13,    5,   1             ;
  :          1,   7,   28,   67,   76,   67,   28,   7,  1         ;
  :      1,  9,  49,  179,  411,  455,  411,  179,  49,  9,  1     ;
  :  1, 11, 76, 375, 1306, 2921, 3186, 2921, 1306, 375, 76, 11, 1  ;

Alois P. Heinz, Rows n = 1..142, flattened
Wikipedia, Permutation

Columns k=0-10 give (offsets may differ): A002467, A180191, A324352, A324353, A324354, A324355, A324356, A324357, A324358, A324359, A324360.
Row sums give A306525.
T(n+1,n) gives A000012.
T(n+2,n) gives A005408.
T(n+2,n-1) gives A056107.
T(2n,n) gives A324361.
Cf. A000142, A306455, A306461, A324224, A324362.

b:= proc(s, d) option remember; (n-> `if`(n=0, add(x^j, j=d),
      add(b(s minus {i}, d union {n-i}), i=s)))(nops(s))
    end:
T:= n-> (p-> seq(coeff(p, x, i)/abs(i)!, i=1-n..n-1))(b({$1..n}, {})):
seq(T(n), n=1..8);
# second Maple program:
T:= (n, k)-> -add((-1)^j*binomial(n-abs(k), j)*(n-j)!, j=1..n)/abs(k)!:
seq(seq(T(n, k), k=1-n..n-1), n=1..9);

T[n_, k_] := (-1/Abs[k]!) Sum[(-1)^j Binomial[n-Abs[k], j] (n-j)!, {j, 1, n}];
Table[T[n, k], {n, 1, 9}, {k, 1-n, n-1}] // Flatten (* Jean-François Alcover, Feb 15 2021 *)

T(n,k) = T(n,-k).
T(n,k) = -1/|k|! * Sum_{j=1..n} (-1)^j * binomial(n-|k|,j) * (n-j)!.
T(n,k) = (n-|k|)! [x^(n-|k|)] (1-exp(-x))/(1-x)^(|k|+1).
T(n+1,n) = 1.
T(n,k) = A306461(n,k) / |k|!.
Sum_{k=1-n..n-1} |k|! * T(n,k) = A306455(n).

A324362 Total number of occurrences of k in the (signed) displacement sets of all permutations of [n+k] divided by k!; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 0, 1, 3, 4, 0, 1, 5, 13, 15, 0, 1, 7, 28, 67, 76, 0, 1, 9, 49, 179, 411, 455, 0, 1, 11, 76, 375, 1306, 2921, 3186, 0, 1, 13, 109, 679, 3181, 10757, 23633, 25487, 0, 1, 15, 148, 1115, 6576, 29843, 98932, 214551, 229384, 0, 1, 17, 193, 1707, 12151, 69299, 307833, 1006007, 2160343, 2293839

Offset: 0

Alois P. Heinz, Feb 23 2019

			Square array A(n,k) begins:
    0,    0,     0,     0,     0,      0,      0, ...
    1,    1,     1,     1,     1,      1,      1, ...
    1,    3,     5,     7,     9,     11,     13, ...
    4,   13,    28,    49,    76,    109,    148, ...
   15,   67,   179,   375,   679,   1115,   1707, ...
   76,  411,  1306,  3181,  6576,  12151,  20686, ...
  455, 2921, 10757, 29843, 69299, 142205, 266321, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened
Wikipedia, Permutation

Columns k=0-10 give: A002467, A180191(n+1), A324352, A324353, A324354, A324355, A324356, A324357, A324358, A324359, A324360.
Rows n=0-3 give: A000004, A000012, A005408, A056107(k+1).
Main diagonal gives A324361.
Cf. A306234.

A:= (n, k)-> -add((-1)^j*binomial(n, j)*(n+k-j)!, j=1..n)/k!:
seq(seq(A(n, d-n), n=0..d), d=0..12);

m = 10;
col[k_] := col[k] = CoefficientList[(1-Exp[-x])/(1-x)^(k+1)+O[x]^(m+1), x]* Range[0, m]!;
A[n_, k_] := col[k][[n+1]];
Table[A[n, d-n], {d, 0, m}, {n, 0, d}] // Flatten (* Jean-François Alcover, May 03 2021 *)

E.g.f. of column k: (1-exp(-x))/(1-x)^(k+1).
A(n,k) = -1/k! * Sum_{j=1..n} (-1)^j * binomial(n,j) * (n+k-j)!.
A(n,k) = A306234(n+k,k).

A207819 Number of permutations of [n] with a fixed point and/or a succession.

Original entry on oeis.org

0, 1, 1, 6, 20, 106, 618, 4358, 34836, 313592, 3135988, 34498646, 414007634, 5382362086, 75356174332, 1130382058576, 18086649408624, 307480839465174, 5534775895914982, 105162728081809146, 2103289132221173216, 44169707042511725964, 971745847021319655464, 22350404337704558809666, 536415027665581568375190, 13410494347081333360291850

Offset: 0

Jon Perry, Jan 10 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 the only permutations that do not count are 2143, 2413, 3142 and 4321, so a(4) = 4!-4 = 20.

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

Cf. A000166, A002467, A180191, A201452, A207821, A209322.

F[{}] = 1; F[S_] := Sum[G[S ~Complement~ {s}, s-1], {s, S ~Complement~ {Length[S]}}];
G[{}, ] = 1; G[S, t_] := G[S, t] = Sum[G[S ~Complement~ {s}, s-1], {s, S ~Complement~ {t, Length[S]}}];
Table[a[n] = n! - F[Range[n]]; Print[n, " ", a[n]]; a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 05 2019, using Robert Israel's code for A209322 *)

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

a(n) = n! - A209322(n). - Robert Israel, Mar 27 2017

Values a(1..10) double-checked by M. F. Hasler, Jan 13 2013
a(11)-a(14) from Alois P. Heinz, Jan 15 2013
a(15)-a(20) from Robert Israel, Mar 27 2017
a(21)-a(23) from Alois P. Heinz, Jul 04 2021
Terms a(24) onward from Max Alekseyev, Apr 03 2025

A207821 Number of permutations of [n] that either have a fixed point or a succession, but not both.

Original entry on oeis.org

0, 1, 0, 5, 12, 69, 370, 2609, 20552, 183249, 1817794, 19867793, 237126320, 3068483277, 42788761294, 639619513669, 10202914060472, 172984071549421, 3106257794721534, 58892020126278457, 1175554242034515780, 24643158882899363129, 541279064964716455230, 12431122899361840993737, 297944099946417376956220, 7439329384072966947792437

Offset: 0

Jon Perry, Jan 10 2013

nonn

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

			a(4) = 12 because we have 1324, 1432, 2341, 2431, 3214, 3241, 3412, 3421, 4123, 4132, 4213 and 4312.

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

Cf. A000166, A002467, A180191, A201452, A207819.

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

a(n) = A209325(n) + A209326(n) = A000166(n) + A000255(n-1) - 2*A209322(n) = 2*A207819(n) - A180191(n) - A002467(n). - Max Alekseyev, Apr 03 2025

Values a(1) to a(10) double-checked by M. F. Hasler, Jan 13 2013
Inserted a(0) and a(11)-a(13) from Alois P. Heinz, Jan 18 2013
a(14)-a(20) from Alois P. Heinz, Jul 05 2021
Terms a(21) onward from Max Alekseyev, Apr 03 2025

A209322 Number of derangements of [n] with no succession.

Original entry on oeis.org

1, 0, 1, 0, 4, 14, 102, 682, 5484, 49288, 492812, 5418154, 64993966, 844658714, 11822116868, 177292309424, 2836140479376, 48206588630826, 867597809813018, 16482372327022854, 329612875955466784, 6921235129197714036, 152254880756288024536, 3501612401180417830334, 84033374067657870984810, 2100715696249652623708150

Offset: 0

Jon Perry, Jan 19 2013

nonn

A derangement is a permutation with no fixed points. A succession of a permutation p is a position i such that p(i+1)-p(i) = 1.

			For n=4 we have 2143, 2413, 3142 and 4321, so a(4) = 4.

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

Cf. A000166, A002467, A180191, A207819, A207821, A209325, A209326, A288208.

F:= proc(S) add(G(S minus {s}, s-1), s = S minus {nops(S)}) end proc:
G:= proc(S,t) option remember;
if S = {} then return 1 fi;
add(procname(S minus {s},s-1), s = S minus {t, nops(S)})
end proc:
1,seq(F({$1..n}), n=1..19); # Robert Israel, Mar 02 2017

F[{}] = 1; F[S_] := Sum[G[S ~Complement~ {s}, s-1], {s, S ~Complement~ {Length[S]}}];
G[{}, ] = 1; G[S, t_] := G[S, t] = Sum[G[S ~Complement~ {s}, s-1], {s, S ~Complement~ {t, Length[S]}}];
Table[a[n] = F[Range[n]]; Print[n, " ", a[n]]; a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 05 2019, after Robert Israel *)

{ a209322(n) = if(n==0, return(1)); my(A=matrix(n, n, i, j, i-j!=1 && i!=j)); parsum(s=1, 2^n-1, my(M=vecextract(A, s, s), d=matsize(M)[1], v=vectorv(d, i, 1), pos=bitand(s, 1)); if(pos, v[1]=0); for(k=1, n-1, v=M*v; if(bitand(s>>k, 1), v[pos++]=0)); (-1)^(n-d)*vecsum(v) ); } \\ Max Alekseyev, Apr 03 2025

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

a(11)-a(14) from Alois P. Heinz, Jan 19 2013
a(15)-a(20) from Robert Israel, Mar 02 2017
a(21)-a(23) from Alois P. Heinz, Jul 04 2021
Terms a(24) onward from Max Alekseyev, Apr 03 2025

A306461 Number T(n,k) of occurrences of k in a (signed) displacement set of a permutation of [n]; triangle T(n,k), n>=1, 1-n<=k<=n-1, read by rows.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 4, 3, 2, 6, 10, 13, 15, 13, 10, 6, 24, 42, 56, 67, 76, 67, 56, 42, 24, 120, 216, 294, 358, 411, 455, 411, 358, 294, 216, 120, 720, 1320, 1824, 2250, 2612, 2921, 3186, 2921, 2612, 2250, 1824, 1320, 720, 5040, 9360, 13080, 16296, 19086, 21514, 23633, 25487, 23633, 21514, 19086, 16296, 13080, 9360, 5040

Offset: 1

Alois P. Heinz, Feb 17 2019

			The 6 permutations p of [3]: 123, 132, 213, 231, 312, 321 have (signed) displacement sets {p(i)-i, i=1..3}: {0}, {-1,0,1}, {-1,0,1}, {-2,1}, {-1,2}, {-2,0,2}, respectively. Numbers -2 and 2 occur twice, -1 and 1 occur thrice, and 0 occurs four times. So row n=3 is [2, 3, 4, 3, 2].
Triangle T(n,k) begins:
  :                             1                           ;
  :                        1,   1,   1                      ;
  :                   2,   3,   4,   3,   2                 ;
  :              6,  10,  13,  15,  13,  10,   6            ;
  :        24,  42,  56,  67,  76,  67,  56,  42,  24       ;
  :  120, 216, 294, 358, 411, 455, 411, 358, 294, 216, 120  ;

Alois P. Heinz, Rows n = 1..142, flattened
Wikipedia, Permutation

Columns k=0-1 give: A002467, A180191.
Row sums give A306455.
T(n+1,n) gives A000142.
T(n+2,n) gives A007680.
Cf. A000142, A061018 (left half of this triangle), A306234, A306506, A324225.

b:= proc(s, d) option remember; (n-> `if`(n=0, add(x^j, j=d),
      add(b(s minus {i}, d union {n-i}), i=s)))(nops(s))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1-n..n-1))(b({$1..n}, {})):
seq(T(n), n=1..8);
# second Maple program:
T:= (n, k)-> -add((-1)^j*binomial(n-abs(k), j)*(n-j)!, j=1..n):
seq(seq(T(n, k), k=1-n..n-1), n=1..9);

T[n_, k_] := -Sum[(-1)^j Binomial[n-Abs[k], j] (n-j)!, {j, 1, n}];
Table[Table[T[n, k], {k, 1-n, n-1}], {n, 1, 9}] // Flatten (* Jean-François Alcover, Feb 20 2021, after Alois P. Heinz *)

T(n,k) = T(n,-k).
T(n,k) = - Sum_{j=1..n} (-1)^j * binomial(n-|k|,j) * (n-j)!.
T(n,k) = |k|! * (n-|k|)! [x^(n-|k|)] (1-exp(-x))/(1-x)^(|k|+1).
Sum_{k=1-n..n-1} T(n,k) = A306455(n).
T(n,k) = |k|! * A306234(n,k).

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

Original entry on oeis.org

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

A116853 Difference triangle of factorial numbers read by upward diagonals.

Original entry on oeis.org

1, 1, 2, 3, 4, 6, 11, 14, 18, 24, 53, 64, 78, 96, 120, 309, 362, 426, 504, 600, 720, 2119, 2428, 2790, 3216, 3720, 4320, 5040, 16687, 18806, 21234, 24024, 27240, 30960, 35280, 40320

Offset: 1

Gary W. Adamson, Feb 24 2006

This is a subsequence of Euler's difference table A068106 and of A047920 (in a different ordering), since 0! = 1 was left out here. - Georg Fischer, Mar 23 2019

			Starting with 1, 2, 6, 24, 120 ... we take the first difference row (A001563), second, third, etc. Reorient into a flush left format, getting:
[1]    1;
[2]    1,   2;
[3]    3,   4,   6;
[4]   11,  14,  18,  24;
[5]   53,  64,  78,  96, 120;
[6]  309, 362, 426, 504, 600, 720;
...

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened

Cf. A000142 (factorial numbers).
Cf. A000255 (first column and inverse binomial transform of A000142).
N-th forward differences of A000142: A001563 (1st), A001564 (2nd), A001565 (3rd), A001688 (4th), A001689 (5th).
Cf. A047920 (with 0!, different order), A068106 (with 0!), A180191 (row sums), A246606 (central terms).

a116853 n k = a116853_tabl !! (n-1) !! (k-1)
a116853_row n = a116853_tabl !! (n-1)
a116853_tabl = map reverse $ f (tail a000142_list) [] where
   f (u:us) vs = ws : f us ws where ws = scanl (-) u vs
-- Reinhard Zumkeller, Aug 31 2014

rows = 8;
rr = Range[rows]!;
dd = Table[Differences[rr, n], {n, 0, rows-1}];
T = Array[t, {rows, rows}];
Do[Thread[Evaluate[Diagonal[T, -k+1]] = dd[[k, ;;rows-k+1]]], {k, rows}];
Table[t[n, k], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Dec 21 2019 *)

Take successive difference rows of factorial numbers n! starting with n=1. Reorient into a triangle format.

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

cp's OEIS Frontend

A306234 Number T(n,k) of occurrences of k in a (signed) displacement set of a permutation of [n] divided by |k|!; triangle T(n,k), n>=1, 1-n<=k<=n-1, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A324362 Total number of occurrences of k in the (signed) displacement sets of all permutations of [n+k] divided by k!; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A207819 Number of permutations of [n] with a fixed point and/or a succession.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A207821 Number of permutations of [n] that either have a fixed point or a succession, but not both.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A209322 Number of derangements of [n] with no succession.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A306461 Number T(n,k) of occurrences of k in a (signed) displacement set of a permutation of [n]; triangle T(n,k), n>=1, 1-n<=k<=n-1, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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