A216779
Number of derangements on n elements with an odd number of cycles.
Original entry on oeis.org
0, 0, 1, 2, 6, 24, 135, 930, 7420, 66752, 667485, 7342290, 88107426, 1145396472, 16035550531, 240533257874, 3848532125880, 65425046139840, 1177650830516985, 22375365779822562, 447507315596451070, 9397653627525472280, 206748379805560389951, 4755212735527888968642
Offset: 0
-
a := proc (n) local x, y, t, k; if n <= 1 then 0 else x := 0; 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[Sinh[Log[1/(1-x)]-x],{x,0,nn}],x] (* Geoffrey Critzer, Jun 23 2014 *)
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.
Original entry on oeis.org
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
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.
-
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
-
Table[Table[n!/(n-k)!/2 * (Sum[(-1)^j/j!, {j, 0, k}] - ((k - 1)/k!)), {k, 0, n}], {n, 0, 10}]
A374419
Triangle read by rows: T(n,k) = number of permutations in symmetric group S_n with an even number of non-fixed point cycles, without k<=n particular fixed points.
Original entry on oeis.org
1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 4, 3, 3, 3, 3, 36, 32, 29, 26, 23, 20, 296, 260, 228, 199, 173, 150, 130, 2360, 2064, 1804, 1576, 1377, 1204, 1054, 924, 19776, 17416, 15352, 13548, 11972, 10595, 9391, 8337, 7413, 180544, 160768, 143352, 128000, 114452, 102480, 91885, 82494, 74157, 66744
Offset: 0
Triangle array T(n,k) begins:
n: {k<=n}
0: {1}
1: {1, 0}
2: {1, 0, 0}
3: {1, 0, 0, 0}
4: {4, 3, 3, 3, 3}
5: {36, 32, 29, 26, 23, 20}
6: {296, 260, 228, 199, 173, 150, 130}
7: {2360, 2064, 1804, 1576, 1377, 1204, 1054, 924}
T(n,0) = A373339(n) = the number of permutations in S_n without k=0 particular fixed points (i.e., not filtered, so all permutations) with an even number of cycles.
T(n,n) = A216778(n) = the number of permutations in S_n without k=n particular fixed points (i.e., filtered down to just the derangements) with an even number of cycles.
T(4,1<=k<=4) = 3 because S_4 contains 3 permutations with an even number of non-fixed point cycles without k=1,2,3 or 4 particular fixed points, namely the 3 (2,2)-cycles: (12)(34), (13)(24), (14)(23).
T(4,0) = 4 is one more than the above because it includes the permutation without k=0 particular fixed points, i.e., the identity permutation of 4 fixed points.
-
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