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

Author

Alois P. Heinz, Mar 02 2024

Keywords

• nonn
• tabf

Examples

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

Links

• Alois P. Heinz, Rows n = 0..50, flattened
• Wikipedia, Permutation

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.

Programs

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

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.