A369596 Number T(n,k) of permutations of [n] whose fixed points sum to k; triangle T(n,k), n>=0, 0<=k<=A000217(n), read by rows.

1, 0, 1, 1, 0, 0, 1, 2, 1, 1, 1, 0, 0, 1, 9, 2, 2, 3, 3, 2, 1, 1, 0, 0, 1, 44, 9, 9, 11, 11, 13, 5, 5, 4, 4, 2, 1, 1, 0, 0, 1, 265, 44, 44, 53, 53, 62, 64, 29, 22, 24, 16, 16, 8, 6, 5, 4, 2, 1, 1, 0, 0, 1, 1854, 265, 265, 309, 309, 353, 362, 406, 150, 159, 126, 126, 93, 86, 44, 36, 29, 19, 19, 9, 7, 5, 4, 2, 1, 1, 0, 0, 1

Offset

0,8

Links

Alois P. Heinz, Rows n = 0..50, flattened

Wikipedia, Permutation

Formula

Sum_{k=0..A000217(n)} k * T(n,k) = A001710(n+1) for n >= 1.

Sum_{k=0..A000217(n)} (1+k) * T(n,k) = A038720(n) for n >= 1.

Sum_{k=0..A000217(n)} (n*(n+1)/2-k) * T(n,k) = A317527(n+1).

T(n,A161680(n)) = A331518(n).

T(n,A000217(n)) = 1.

Example

T(3,0) = 2: 231, 312.
T(3,1) = 1: 132.
T(3,2) = 1: 321.
T(3,3) = 1: 213.
T(3,6) = 1: 123.
T(4,0) = 9: 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321.
Triangle T(n,k) begins:
   1;
   0, 1;
   1, 0, 0,  1;
   2, 1, 1,  1,  0,  0, 1;
   9, 2, 2,  3,  3,  2, 1, 1, 0, 0, 1;
  44, 9, 9, 11, 11, 13, 5, 5, 4, 4, 2, 1, 1, 0, 0, 1;
  ...

Maple

b:= proc(s) option remember; (n-> `if`(n=0, 1, add(expand(
      `if`(j=n, x^j, 1)*b(s minus {j})), j=s)))(nops(s))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b({$1..n})):
seq(T(n), n=0..7);
# second Maple program:
g:= proc(n) option remember; `if`(n=0, 1, n*g(n-1)+(-1)^n) end:
b:= proc(n, i, m) option remember; `if`(n>i*(i+1)/2, 0,
     `if`(n=0, g(m), b(n, i-1, m)+b(n-i, min(n-i, i-1), m-1)))
    end:
T:= (n, k)-> b(k, min(n, k), n):
seq(seq(T(n, k), k=0..n*(n+1)/2), n=0..7);

Mathematica

g[n_] := g[n] = If[n == 0, 1, n*g[n - 1] + (-1)^n];
b[n_, i_, m_] := b[n, i, m] = If[n > i*(i + 1)/2, 0,
   If[n == 0, g[m], b[n, i-1, m] + b[n-i, Min[n-i, i-1], m-1]]];
T[n_, k_] := b[k, Min[n, k], n];
Table[Table[T[n, k], {k, 0, n*(n + 1)/2}], {n, 0, 7}] // Flatten (* Jean-François Alcover, May 24 2024, after Alois P. Heinz *)

Crossrefs

Column k=0 gives A000166.

Column k=3 gives A000255(n-2) for n>=2.

Row sums give A000142.

Row lengths give A000124.

Reversed rows converge to A331518.

T(n,n) gives A369796.

Cf. A000217, A001710, A008289, A008290, A038720, A053632, A062869, A124327, A143946, A143947, A161680, A263753, A263756, A317527, A367955, A368338.

Sequence in context: A089053 A214979 A068462 * A054973 A030351 A257994

Adjacent sequences: A369593 A369594 A369595 * A369597 A369598 A369599

Keyword

nonn,tabf

Author

Alois P. Heinz, Mar 02 2024

Status

approved