|
|
A364318
|
|
Irregular table T read by rows: T(n,k) gives for permutations of [n] = {1, 2, ..., n}, n >= 1, the number of cycles corresponding to the k-th partition of n without part 1 (in Abramowitz-Stegun order).
|
|
0
|
|
|
0, 1, 2, 6, 3, 24, 20, 120, 90, 40, 15, 720, 504, 420, 210, 5040, 3360, 2688, 1260, 1260, 1120, 105, 40320, 25920, 20160, 18144, 9072, 15120, 2240, 2520, 362880, 226800, 172800, 151200, 72576, 75600, 120960, 56700, 50400, 18900, 25200, 945
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
The length of row n is 1 for n = 1, and A002865(n), for n >= 2.
This table selects in row n the entries of the partition array (multinomial M2 numbers) corresponding to partitions without part 1.
The characteristic array for partitions of n without part 1 is given in A145573, and the complete M_2 multinomial table is found in A036039 (see the W. Lang link there for n = 1, 2, ..., 10).
In table A008306 the entries of the present table belonging to the same length of the cycles (that is, the same number of parts of the corresponding partition) are summed.
The row sums give the subfactorial (derangement) numbers A000166. (See the W. Lang comment from Jun 01 2010 there on the M_2 multinomial array for the partitions without part 1.)
|
|
LINKS
|
|
|
FORMULA
|
T(n, k) is the table M_2 = A036039 without the entries corresponding to the partitions of n with at least one part 1 (the Abromowitz-Stegun order of partitions is used).
|
|
EXAMPLE
|
The table T begins:
n\k 1 2 3 4 5 6 7 8 ... Row sums A000166
----------------------------------------------------------------------
1: 0 0
2: 1 1
3: 2 2
4: 6 3 9
5: 24 20 44
6: 120 90 40 15 265
7: 720 504 420 210 1854
8: 5040 3360 2688 1260 1260 1120 105 14833
9: 40320 25920 20160 18144 9072 15120 2240 2520 133496
...
n = 10: 362880 226800 172800 151200 72576 75600 120960 56700 50400 18900 25200 945, with sum 1334961.
n = 11: 3628800 2217600 1663200 1425600 1330560 712800 1108800 997920 443520 415800 166320 415800 123200 34650, with sum 14684570.
...
T(8, 6) corresponds to the partition (2,3^2) of n = 8, hence its M_2 multinomial number is 8!/((2^1*1!)*(3^2*2!)) = 1120.
With the number of cycle calculation T(8, 6) = #Cy(8;2,1)*#Cy(8-2;3,2) with #Cy(N;j,ej) = (j-1)!^ej*Product_{q=0..ej-1} binomial(N - q*j, j)/ej!, Hence #Cy(8;2,1) = 1!*binomial(8, 2)/1! = 28, and #Cy(6;3,2) = 2!^2*binomial(6, 3)*binomial(6-3, 3)/2! = 40, and T(8, 6) = 28*40 = 1120.
|
|
CROSSREFS
|
Column k = 1 is A000142(n-1) = (n-1)!.
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|