login
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.
2
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
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
KEYWORD
nonn,tabl
AUTHOR
STATUS
approved