cp's OEIS Frontend

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

%I A385081 #22 Jul 09 2025 23:08:07
%S A385081 1,2,3,6,20,24,15,90,40,120,210,504,420,720,105,1260,1120,3360,2688,
%T A385081 1260,5040,2520,9072,15120,25920,2240,20160,18144,40320,945,18900,
%U A385081 25200,75600,120960,56700,226800,50400,172800,151200,72576,362880
%N A385081 Irregular triangle T(n,k) of refined derangement counts in the symmetric group S_(n+1), refined per cycle type.
%C A385081 The triangle consists of selected entries from A181897.
%C A385081 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).
%C A385081 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.
%H A385081 Gregory Gerard Wojnar, <a href="/A385081/b385081.txt">Table of n, a(n) for n = 1..230</a>
%H A385081 Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a385/A385081.java">Java program</a> (github)
%F A385081 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.
%e A385081 The triangle begins:
%e A385081     1
%e A385081     2
%e A385081     3,   6
%e A385081    20,  24
%e A385081    15,  90,  40, 120
%e A385081   210, 504, 420, 720
%t A385081 partitionMultiplicities[aPartn_]:=Table[Count[aPartn,m],{m,Total[aPartn]}]
%t A385081 partitionBase[aPartn_]:=Sum[m*aPartn[[m]],{m,Length[aPartn]}]
%t A385081 partitionFactorial[aPartn_]:=Product[m^aPartn[[m]],{m,partitionBase[aPartn]}]
%t A385081 partitionParts[aPartn_]:=Sum[aPartn[[m]],{m,Length[aPartn]}]
%t A385081 A385081[aPartn_]:=Multinomial@@aPartn*partitionBase[aPartn]!/(partitionFactorial[aPartn]*partitionParts[aPartn]!)
%t A385081 Grid[Table[Map[A385081,Select[ReverseSort[Map[partitionMultiplicities,Partitions[n]],LexicographicOrder],#[[1]]==0&]],{n,2,12}]]
%Y A385081 Cf. A181897, A000166.
%K A385081 nonn,tabf
%O A385081 1,2
%A A385081 _Gregory Gerard Wojnar_, Jun 16 2025