A385081 Irregular triangle T(n,k) of refined derangement counts in the symmetric group S_(n+1), refined per cycle type.

1, 2, 3, 6, 20, 24, 15, 90, 40, 120, 210, 504, 420, 720, 105, 1260, 1120, 3360, 2688, 1260, 5040, 2520, 9072, 15120, 25920, 2240, 20160, 18144, 40320, 945, 18900, 25200, 75600, 120960, 56700, 226800, 50400, 172800, 151200, 72576, 362880

Offset: 1

Author

Gregory Gerard Wojnar, Jun 16 2025

Keywords

• nonn
• tabf

Comments

The triangle consists of selected entries from A181897.

Each permutation in the symmetric group S_N has a cycle type specified by an integer partition of N. We encode a partition of N as an N-tuple of multiplicities of j=1..N; e.g., the partition 8 = 1+1+2+4 is encoded as (2,1,0,1,0,0,0,0), abbreviated (2,1,0,1). In general (m_j: j=1..N), and this partition corresponds to a cycle type (a)(b)(cd)(efgh) in S_8. Derangements have no fixed points, hence correspond to partitions with no addends of 1; i.e., m_1=0. A181897 counts all permutations via cycle type (not just derangements), with the partitions ordered reverse lexicographically in terms of their multiplicities N-tuples. E.g., partitions of 4 are ordered: (4), (2,1), (1,0,1), (0,0,0,1). In fact, the columns of A181897 (as a triangular array) are scaled columns of binomial coefficients binomial(p,q) with q fixed for each column, scaled by the entries in this listing (see new comment in A181897 for details).

The number of terms in the n-th row of this irregular triangle is given by p(n+1)-p(n) where p(n) = A000041(n) is the partitions counting function. The row sum of row n is A000166(n+1). The number of 'parts' of a partition P is K(P) := Sum_{j=1..N} m_j; if this sequence is signed by (-1)^(1+N+K), then the signed sum of row n is equal to n. The last entry in row n is n!. The first entry in odd rows n is equal to n!!. The first entry in even rows n is equal to n*(n+1)!!/3.

Examples

			The triangle begins:
    1
    2
    3,   6
   20,  24
   15,  90,  40, 120
  210, 504, 420, 720
		

Links

• Gregory Gerard Wojnar, Table of n, a(n) for n = 1..230
• Sean A. Irvine, Java program (github)

Crossrefs

Cf. A181897, A000166.

Programs

Mathematica

partitionMultiplicities[aPartn_]:=Table[Count[aPartn,m],{m,Total[aPartn]}]
partitionBase[aPartn_]:=Sum[m*aPartn[[m]],{m,Length[aPartn]}]
partitionFactorial[aPartn_]:=Product[m^aPartn[[m]],{m,partitionBase[aPartn]}]
partitionParts[aPartn_]:=Sum[aPartn[[m]],{m,Length[aPartn]}]
A385081[aPartn_]:=Multinomial@@aPartn*partitionBase[aPartn]!/(partitionFactorial[aPartn]*partitionParts[aPartn]!)
Grid[Table[Map[A385081,Select[ReverseSort[Map[partitionMultiplicities,Partitions[n]],LexicographicOrder],#[[1]]==0&]],{n,2,12}]]

Formula

Given a partition P of N encoded as its multiplicities N-tuple (m_j: j=1..N) with K(P) = Sum_{j=1..N} m_j 'parts'. Define P! := Product_{j=1..N} j^m_j. Then the number of permutations in the symmetric group S_N of cycles type labelled by P is #P = multinomial(K(P); (m_j){j=1..N}) * N! / (P! * K(P)!), as stated in A181897 by Carlos Mafra.