A373417 Triangle T(n,k) for the number of permutations in symmetric group S_n with (n-k) fixed points and an even number of non-fixed point cycles. Equivalent to the number of cycles of n items with cycle type defined by non-unity partitions of k<=n that contain an even number of parts.

1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 3, 1, 0, 0, 0, 15, 20, 1, 0, 0, 0, 45, 120, 130, 1, 0, 0, 0, 105, 420, 910, 924, 1, 0, 0, 0, 210, 1120, 3640, 7392, 7413, 1, 0, 0, 0, 378, 2520, 10920, 33264, 66717, 66744, 1, 0, 0, 0, 630, 5040, 27300, 110880, 333585, 667440, 667476

Offset: 0

Author

Julian Hatfield Iacoponi, Jun 04 2024

Keywords

• nonn
• tabl

Comments

A343418(n) + a(n) = A098825(n) = partial derangement "rencontres" triangle.

A343418(n) - a(n) = (k-1) * binomial(n,k) = A127717(n-1,k-1).

Difference of 1st and 2nd leading diagonals (n > 0).

T(n,n) - T(n,n-1) = -1,0,0,3,5,10,14,21,27,36,44,...

= (-1) + (1+0) + (3+2) + (5+4) + (7+6) + (9+8) + ...

Cf. A176222(n) with 2 terms -1,0 prepended (moving its offset from 3 to 1).

Examples

			Triangle array T(n,k):
  n:  {k<=n}
  0:  {1}
  1:  {1, 0}
  2:  {1, 0, 0}
  3:  {1, 0, 0, 0}
  4:  {1, 0, 0, 0,   3}
  5:  {1, 0, 0, 0,  15,   20}
  6:  {1, 0, 0, 0,  45,  120,   130}
  7:  {1, 0, 0, 0, 105,  420,   910,    924}
  8:  {1, 0, 0, 0, 210, 1120,  3640,   7392,   7413}
  9:  {1, 0, 0, 0, 378, 2520, 10920,  33264,  66717,  66744}
  10: {1, 0, 0, 0, 630, 5040, 27300, 110880, 333585, 667440, 667476}
T(n,0) = 1 due to sole permutation in S_n with n fixed points, namely the identity permutation, with 0 non-fixed point cycles, an even number. (T(0,0)=1 relies on S_0 containing an empty permutation.)
T(n,1) = 0 due to no permutations in S_n with (n-1) fixed points.
T(n,2) = T(n,3) = 0 due to only non-unity partitions of 2 and 3 being of odd length, namely the trivial partitions (2),(3).
Example:
T(4,4) = 3 since S_4 contains 3 permutations with 0 fixed points and an even number of non-fixed point cycles, namely the derangements: (12)(34),(13)(24),(14)(23).
Worked Example:
T(7,6) = 910 permutations in S_7 with 1 fixed point and an even number of non-fixed point cycles.
T(7,6) = 910 possible (4,2)- and (3,3)-cycles of 7 items.
N(n,y) = possible y-cycles of n items.
N(n,y) = (n!/(n-k)!) / (M(y) * s(y)).
y = partition of k<=n with q parts = (p_1, p_2, ..., p_i, ..., p_q)
s.t. k = Sum_{i=1..q} p_i.
Or:
y = partition of k<=n with d distinct parts, each with multiplicity m_j = (y_1^m_1, y_2^m_2, ..., y_j^m_j, ..., y_d^m_d)
s.t. k = Sum_{j=1..d} m_j*y_j.
M(y) = Product_{i=1..q} p_i = Product_{j=1..d} y_j^m_j.
s(y) = Product_{j=1..d} m_j! ("symmetry of repeated parts").
Note: (n!/(n-k)!) / s(y) = multinomial(n, {m_j}).
Therefore:
T(7,6) = N(7,y=(4,2)) + N(7,y=(3^2))
       = (7!/(4*2)) + (7!/(3^2)/2!)
       = 7! * (1/8 + 1/18)
       = 5040 * (13/72)
T(7,6) = 910.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 0..11475 (rows n = 0..150, flattened)

Crossrefs

Cf. A373418 (odd case), A373339 (row sums), A216778 (main diagonal).

Programs

Maple

b:= proc(n, t) option remember; `if`(n=0, t, add(expand(`if`(j>1, x^j, 1)*
      b(n-j, irem(t+signum(j-1), 2)))*binomial(n-1, j-1)*(j-1)!, j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 1)):
seq(T(n), n=0..10);  # Alois P. Heinz, Jun 04 2024

Mathematica

Table[Table[n!/(n-k)!/2 * (Sum[(-1)^j/j!, {j, 0, k}] - ((k - 1)/k!)), {k, 0, n}], {n, 0, 10}]

Formula

T(n,k) = (n!/(n-k)!/2) * (Sum_{j=0..k} (-1)^j/j! - (k-1)/k!) Cf. Sum_{j=0..k} (-1)^j/j! = A053557(k) / A053556(k).