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, 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

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

Table of n, a(n) for n=1..42.

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

Cf. A000166, A002865, A008306, A135573.

Column k = 1 is A000142(n-1) = (n-1)!.

Sequence in context: A359256 A304085 A302783 * A008306 A231171 A331431

Adjacent sequences: A364315 A364316 A364317 * A364319 A364320 A364321

Keyword

nonn,tabf

Author

Wolfdieter Lang, Aug 14 2023

Status

approved