A306455 -id:A306455 - 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).

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

A125182 Triangle read by rows: T(n,k) is the number of permutations p of {1,2,...,n} such that the set {p(i)-i, i=1,2,...,n} has exactly k elements (1<=k<=n).

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 4, 12, 7, 1, 4, 38, 54, 23, 1, 8, 77, 248, 303, 83, 1, 6, 160, 824, 2008, 1636, 405, 1, 11, 285, 2320, 9449, 15789, 10352, 2113, 1, 10, 476, 5564, 37237, 102726, 133293, 70916, 12657, 1, 14, 799, 13172, 122708, 536900, 1158368, 1177168, 537373, 82297

Offset: 1

Emeric Deutsch, Nov 24 2006

Row sums are the factorial numbers (A000142). T(n,1)=1 (the identity permutation). T(n,2) = A065608(n) = (sum of divisors of n)-(number of divisors of n). T(n,n) = A099152(n). In the first Maple program define n (<=10) to obtain row n.

T(n,k) is also the number of permutations p of {1,2,...,n} such that the set {p(i) + i, i=1,2,...,n} has exactly k elements (1<=k<=n). Example: T(4,2)=4 because we have 1432, 3412, 2143 and 3214. - Emeric Deutsch, Nov 28 2008

			T(4,2) = 4 because we have 4123, 3412, 2143 and 2341.
Triangle starts:
  1;
  1, 1;
  1, 2,  3;
  1, 4, 12,  7;
  1, 4, 38, 54, 23;
  ...

Alois P. Heinz, Rows n = 1..12, flattened
M. Alekseyev, E. Deutsch, and J. H. Steelman, Problem 11281, Amer. Math. Monthly, 116, No. 5, 2009, p. 465. - _Emeric Deutsch_, Apr 23 2009

Cf. A000142, A065608, A099152, A125183, A306455.

n:=7: with(combinat): P:=permute(n): for j from 1 to n! do c[j]:=0 od: for j from 1 to n! do if nops({seq(P[j][i]-i,i=1..n)}) = 1 then c[1]:=c[1]+1 elif nops({seq(P[j][i]-i,i=1..n)}) = 2 then c[2]:=c[2]+1 elif nops({seq(P[j][i]-i,i=1..n)}) = 3 then c[3]:=c[3]+1 elif nops({seq(P[j][i]-i,i=1..n)}) = 4 then c[4]:=c[4]+1 elif nops({seq(P[j][i]-i,i=1..n)}) = 5 then c[5]:=c[5]+1 elif nops({seq(P[j][i]-i,i=1..n)}) = 6 then c[6]:=c[6]+1 elif nops({seq(P[j][i]-i,i=1..n)}) = 7 then c[7]:=c[7]+1 elif nops({seq(P[j][i]-i,i=1..n)}) = 8 then c[8]:=c[8]+1 elif nops({seq(P[j][i]-i,i=1..n)}) = 9 then c[9]:=c[9]+1 elif nops({seq(P[j][i]-i,i=1..n)}) = 10 then c[10]:=c[10]+1 else fi od: seq(c[i],i=1..n);
# second Maple program:
b:= proc(p, s) option remember; `if`(p={}, x^nops(s),
      add(b(p minus {t}, s union {t+nops(p)}), t=p))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b({$1..n}, {})):
seq(T(n), n=1..9);  # Alois P. Heinz, May 04 2014; revised, Sep 08 2018

b[i_, p_List, s_List] := b[i, p, s] = If[p == {}, x^Length[s], Sum[b[i+1, p ~Complement~ {t}, s ~Union~ {t+i}], {t, p}]]; T[n_] := Function[{p}, Table[ Coefficient[p, x, i], {i, 1, n}]][b[1, Range[n], {}]]; Table[T[n], {n, 1, 9}] // Flatten (* Jean-François Alcover, Feb 19 2015, after Alois P. Heinz *)

Sum_{k=1..n} k * T(n,k) = A306455(n). - Alois P. Heinz, Feb 16 2019

A259834 Number of permutations of [n] with no fixed points where the maximal displacement of an element equals n-1.

Original entry on oeis.org

0, 0, 1, 2, 5, 20, 97, 574, 3973, 31520, 281825, 2803418, 30704101, 367114252, 4757800705, 66432995030, 994204132517, 15875195019224, 269397248811073, 4841453414347570, 91856764780324165, 1834779993945449348, 38485629141294791201, 845788826477292504302

Offset: 0

Alois P. Heinz, Jul 06 2015

a(n) counts permutations p of [n] such that p(i) <> i and (p(1) = n or p(n) = 1).

			a(2) = 1: 21.
a(3) = 2: 231, 312.
a(4) = 5: 2341, 3421, 4123, 4312, 4321.

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

A diagonal of A259784.

Cf. A000142, A000166, A000255, A292897, A292898, A306455.

a:= proc(n) option remember; `if`(n<3, [0, 0, 1][n+1],
     ((2*n^2-11*n+13)*a(n-1) +(2*n-5)*(n-3)*a(n-2))/(2*n-7))
    end:
seq(a(n), n=0..30);

Join[{0, 0}, Table[DifferenceRoot[Function[{y, m}, {y[1 + m] == (n - m)*y[m] + (n - m) y[m - 1], y[0] == 0, y[1] == 1, y[2] == 1}]][n], {n, 2, 30}]] (* Benedict W. J. Irwin, Nov 03 2016 *)
Table[If[n<2, 0, Subfactorial[n-2]+2*Subfactorial[n-1]], {n,0,23}] (* Peter Luschny, Oct 04 2017 *)

def A259834_list(len):
    L, u, x, y = [0], 1, 0, 0
    for n in range(len):
        y, x, u = x, x*n + u, -u
        L.append(y + 2*x)
    L[1] = 0
    return L
print(A259834_list(23)) # Peter Luschny, Oct 04 2017

a(n) = ((2*n^2-11*n+13)*a(n-1) + (2*n-5)*(n-3)*a(n-2))/(2*n-7) for n > 2.
a(n) = (n-2)! * [x^(n-2)] exp(-x)*(x+1)/(x-1)^2 for n > 1.
a(n) ~ 2 * (n-1)! / exp(1). - Vaclav Kotesovec, Jul 07 2015
a(n) = y(n,n), n > 1, where y(m+1,n) = (n-m)*y(m,n) + (n-m)*y(m-1,n), with y(0,n)=0, y(1,n)=y(2,n)=1 for all n. - Benedict W. J. Irwin, Nov 03 2016
From Peter Luschny, Oct 05 2017: (Start)
a(n) = (Gamma(n-1, -1) + 2*Gamma(n, -1)) / e for n >= 2.
a(n) = A000166(n-2) + 2*A000166(n-1) for n >= 2.
a(n) = (2*n-1)*A000166(n-2) - 2*(-1)^n for n >= 2.
a(n) = A000255(n-2) + A000166(n-1) for n >= 2.
a(n+2) = (-1)^n*(-hypergeom([1,1-n], [], 1) + hypergeom([2,2-n], [], 1)) = A292898(2, n) for n >= 0.
a(n) ~ 2*sqrt(2*Pi)*exp(-n-1)*n^(n-1/2). (End)
a(n+2) = A306455(n) + n! for n >= 0. - Alois P. Heinz, Feb 16 2019

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

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

A125182 Triangle read by rows: T(n,k) is the number of permutations p of {1,2,...,n} such that the set {p(i)-i, i=1,2,...,n} has exactly k elements (1<=k<=n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A259834 Number of permutations of [n] with no fixed points where the maximal displacement of an element equals n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula