A373418 Triangle read by rows: T(n,k) is the number of permutations in symmetric group S_n with (n-k) fixed points and an odd 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 odd number of parts.

0, 0, 0, 0, 0, 1, 0, 0, 3, 2, 0, 0, 6, 8, 6, 0, 0, 10, 20, 30, 24, 0, 0, 15, 40, 90, 144, 135, 0, 0, 21, 70, 210, 504, 945, 930, 0, 0, 28, 112, 420, 1344, 3780, 7440, 7420, 0, 0, 36, 168, 756, 3024, 11340, 33480, 66780, 66752, 0, 0, 45, 240, 1260, 6048, 28350, 111600, 333900, 667520, 667485

Offset

0,9

Comments

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

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

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

T(n,n-1) - T(n,n) = 0,-1,1,2,6,9,15,20,28,35,45,54,...

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

Cf. A084265(n) with 2 terms 0,-1 prepended (moving its offset from 0 to -2). - Julian Hatfield Iacoponi, Jun 07 2024

Links

Table of n, a(n) for n=0..65.

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) - Julian Hatfield Iacoponi, Jun 07 2024

Example

Triangle begins:
   n: {k<=n}
   0: {0}
   1: {0, 0}
   2: {0, 0,  1}
   3: {0, 0,  3,   2}
   4: {0, 0,  6,   8,    6}
   5: {0, 0, 10,  20,   30,   24}
   6: {0, 0, 15,  40,   90,  144,   135}
   7: {0, 0, 21,  70,  210,  504,   945,    930}
   8: {0, 0, 28, 112,  420, 1344,  3780,   7440,   7420}
   9: {0, 0, 36, 168,  756, 3024, 11340,  33480,  66780,  66752}
  10: {0, 0, 45, 240, 1260, 6048, 28350, 111600, 333900, 667520, 667485}
T(n,0) = 0 because the sole permutation in S_n with n fixed points, namely the identity permutation, has 0 non-fixed point cycles, not an odd number.
T(n,1) = 0 because there are no permutations in S_n with (n-1) fixed points.
Example:
T(3,3) = 2 since S_3 contains 3 permutations with 0 fixed points and an odd number of non-fixed point cycles, namely the derangements (123) and (132).
Worked Example:
T(7,6) = 945 permutations in S_7 with 1 fixed point and an odd number of non-fixed point cycles;
T(7,6) = 945 possible 6- and (2,2,2)-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=(6)) + N(7,y=(2^3))
       = (7!/6) + (7!/(2^3)/3!)
       = 7! * (1/6 + 1/48)
       = 5040 * (3/16);
T(7,6) = 945. - Julian Hatfield Iacoponi, Jun 07 2024

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, 0)):
seq(T(n), n=0..10);

Mathematica

Table[Table[n!/(n-k)!/2 * (Sum[(-1)^j/j!, {j, 0, k}] - ((k - 1)/k!)), {k, 1, n}], {n, 1, 10}] (*Julian Hatfield Iacoponi, Jun 07 2024*).

Crossrefs

Cf. A373417 (even case), A373340 (row sums), A216779 (main diagonal).

Sequence in context: A261180 A062707 A160230 * A293500 A240659 A246159

Adjacent sequences: A373415 A373416 A373417 * A373419 A373420 A373421

Keyword

nonn,tabl

Author

Julian Hatfield Iacoponi, Jun 04 2024

Status

approved