A181897 Triangle of refined rencontres numbers: T(n,k) is the number of permutations of n elements with cycle type k (k-th integer partition, defined by A194602).

1, 1, 1, 1, 3, 2, 1, 6, 8, 3, 6, 1, 10, 20, 15, 30, 20, 24, 1, 15, 40, 45, 90, 120, 144, 15, 90, 40, 120, 1, 21, 70, 105, 210, 420, 504, 105, 630, 280, 840, 210, 504, 420, 720, 1, 28, 112, 210, 420, 1120, 1344, 420, 2520, 1120, 3360, 1680, 4032

Offset: 1

Author

Tilman Piesk, Mar 31 2012

Keywords

• tabf
• nonn

Comments

T(n,k) tells how often k appears among the first n! entries of A198380, i.e., how many permutations of n elements have the cycle type denoted by k.

This triangle is a refinement of the rencontres numbers A008290, which tell only how many permutations of n elements actually move a certain number of elements. How many of these permutations have a certain cycle type is a more detailed question, answered by this triangle.

The rows are counted from 1, the columns from 0.

Row lengths: 1, 2, 3, 5, 7, 11, ... (partition numbers A000041).

Row sums: 1, 2, 6, 24, 120, 720, ... (factorial numbers A000142).

Row maxima: 1, 1, 3, 8, 30, 144, ... (A059171).

Distinct entries per row: 1, 1, 3, 4, 6, 7, ... (A073906).

It follows from the formula given by Carlos Mafra that the rows of the triangle correspond to the coefficients of the modified Bell polynomials. - Sela Fried, Dec 08 2021

For k>0, the k-th column of triangle T(n,k) is a scaled copy of binomial coefficients binomial(n,q) where q is the least value for which p(q) exceeds or equals k+1, with p() being the integer partitions counting function, A000041(q). E.g., for column 4, the relevant binomial coefficients have q=4 as p(4)=5; for column 5, we have q=5 as p(5)>6; for column 6, we have q=5 as p(5)=7. The scale factor for column k is given by A385081(k+1). This triangle gives coefficients for expressing the characteristic polynomial and determinant of a matrix solely in terms of traces; see extended comment, below, under "Links". - Gregory Gerard Wojnar, Jun 24 2025

Examples

			Triangle begins:
  1;
  1,  1;
  1,  3,  2;
  1,  6,  8,  3,  6;
  1, 10, 20, 15, 30,  20,  24;
  1, 15, 40, 45, 90, 120, 144, 15, 90, 40, 120;
  ...
		

Links

• Gregory Gerard Wojnar, Table of n, a(n) for n = 1..271
• Marc-Antoine Coppo and Bernard Candelpergher, Inverse binomial series and values of Arakawa-Kaneko zeta functions, Journal of Number Theory, (150) pp. 98-119, (2015). See p. 101.
• Bartlomiej Pawelski, On the number of inequivalent monotone Boolean functions of 8 variables, arXiv:2108.13997 [math.CO], 2021. Mentions this sequence.
• Bartłomiej Pawelski, Counting and generating monotone Boolean functions, Doctoral Diss., Univ. Gdańsk, (Poland, 2024). See pp. 26, 34.
• Tilman Piesk, Permutations by cycle type (Wikiversity article)
• Gregory Gerard Wojnar, Comments on A181897, Sep 29 2020.

Crossrefs

Cf. A000041, A000142, A000166, A198380, A194602, A008290, A073906, A000217, A007290, A385081.

Cf. A036039 and references therein for different ordering of terms within each row.

Programs

Mathematica

Table[CoefficientRules[ n! CycleIndex[SymmetricGroup[n], s] // Expand][[All, 2]], {n, 1, 8}] // Grid (* Geoffrey Critzer, Nov 09 2014 *)
(* Alternative program *)
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]}]
A181897[aPartn_]:=Multinomial@@aPartn*partitionBase[aPartn]!/(partitionFactorial[aPartn]*partitionParts[aPartn]!)
Grid[Table[Map[A181897,ReverseSort[Map[partitionMultiplicities,Partitions[n]],LexicographicOrder]],{n,2,12}]] (* Gregory Gerard Wojnar, Jun 24 2025 *)

Formula

T(n,1) = A000217(n).

T(n,2) = A007290(n).

Let m2, m3, ... count the appearances of 2, 3, ... in the cycle type. E.g., the cycle type 2, 2, 2, 3, 3, 4 implies m2=3, m3=2, m4=1. Then T(n;m2,m3,m4,...) = n!/((2^m2 3^m3 4^m4 ...) m1!m2!m3!m4! ...) where m1 = n - 2m2 - 3m3 - 4m4 - ... . - Carlos Mafra, Nov 25 2014