A216778
Number of derangements on n elements with an even number of cycles.
Original entry on oeis.org
1, 0, 0, 0, 3, 20, 130, 924, 7413, 66744, 667476, 7342280, 88107415, 1145396460, 16035550518, 240533257860, 3848532125865, 65425046139824, 1177650830516968, 22375365779822544, 447507315596451051, 9397653627525472260, 206748379805560389930, 4755212735527888968620
Offset: 0
-
a := proc (n) local x, y, t, k; if n = 0 then 1 elif n = 1 then 0 else x := 1; y := 0; for k from 2 to n do t := y; y := (k-1)*(x+y+k-3); x := t end do; y end if end proc;
-
nn=23;Range[0,nn]!*CoefficientList[Series[Cosh[Log[1/(1-x)]-x],{x,0,nn}],x] (* Geoffrey Critzer, Jun 23 2014 *)
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.
Original entry on oeis.org
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
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) such that 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) such that 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.
-
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);
-
Table[Table[n!/(n-k)!/2 * (Sum[(-1)^j/j!, {j, 0, k}] - ((k - 1)/k!)),{k,1,n}], {n,1,10}]
A374420
Triangle T(n, k) for the number of permutations of symmetric group S_n with an odd number of non-fixed point cycles, without k <= n particular fixed points.
Original entry on oeis.org
0, 0, 0, 1, 1, 1, 5, 4, 3, 2, 20, 15, 11, 8, 6, 84, 64, 49, 38, 30, 24, 424, 340, 276, 227, 189, 159, 135, 2680, 2256, 1916, 1640, 1413, 1224, 1065, 930, 20544, 17864, 15608, 13692, 12052, 10639, 9415, 8350, 7420, 182336, 161792, 143928, 128320, 114628, 102576, 91937, 82522, 74172, 66752
Offset: 0
Triangle array T(n,k)
n: {k<=n}
0: {0}
1: {0, 0}
2: {1, 1, 1}
3: {5, 4, 3, 2}
4: {20, 15, 11, 8, 6}
5: {84, 64, 49, 38, 30, 24}
6: {424, 340, 276, 227, 189, 159, 135}
7: {2680, 2256, 1916, 1640, 1413, 1224, 1065, 930}
T(n,0) = A373340(n) = the number of permutations in S_n without k=0 particular fixed points (i.e., not filtered, so all permutations) with an odd number of cycles.
T(n,n) = A216779(n) = the number of permutations in S_n without k=n particular fixed points (i.e., filtered down to just the derangements) with an odd number of cycles.
T(2,k) = 1 because S_2 contains 1 permutation with an odd number of non-fixed point cycles without k=0,1 or 2 particular fixed points, namely the derangement (12).
T(3,2) = 3 because S_3 contains 3 permutations with an odd number of non-fixed point cycles without k=2 particular fixed points: say, without fixed points (1) and (2), namely (12)(3), (123), (132).
-
Table[Table[1/2*(Sum[(-1)^j*Binomial[k, j]*(n - j)!, {j, 0, k}] - 2^(n - k - 1)*(2 - n - k)), {k, 0, n}], {n, 0, 10}]
Showing 1-3 of 3 results.
Comments