cp's OEIS Frontend

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).

%I A181897 #126 Jun 29 2025 17:03:48
%S A181897 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,
%T A181897 90,40,120,1,21,70,105,210,420,504,105,630,280,840,210,504,420,720,1,
%U A181897 28,112,210,420,1120,1344,420,2520,1120,3360,1680,4032
%N 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).
%C A181897 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.
%C A181897 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.
%C A181897 The rows are counted from 1, the columns from 0.
%C A181897 Row lengths: 1, 2, 3, 5, 7, 11, ... (partition numbers A000041).
%C A181897 Row sums: 1, 2, 6, 24, 120, 720, ... (factorial numbers A000142).
%C A181897 Row maxima: 1, 1, 3, 8, 30, 144, ... (A059171).
%C A181897 Distinct entries per row: 1, 1, 3, 4, 6, 7, ... (A073906).
%C A181897 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
%C A181897 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
%H A181897 Gregory Gerard Wojnar, <a href="/A181897/b181897.txt">Table of n, a(n) for n = 1..271</a>
%H A181897 Marc-Antoine Coppo and Bernard Candelpergher, <a href="https://doi.org/10.1016/j.jnt.2014.11.007">Inverse binomial series and values of Arakawa-Kaneko zeta functions</a>, Journal of Number Theory, (150) pp. 98-119, (2015). See p. 101.
%H A181897 Bartlomiej Pawelski, <a href="https://arxiv.org/abs/2108.13997">On the number of inequivalent monotone Boolean functions of 8 variables</a>, arXiv:2108.13997 [math.CO], 2021. Mentions this sequence.
%H A181897 Bartłomiej Pawelski, <a href="https://bip.ug.edu.pl/st-tyt_nauk/117481/bartlomiej_pawelski">Counting and generating monotone Boolean functions</a>, Doctoral Diss., Univ. Gdańsk, (Poland, 2024). See pp. 26, 34.
%H A181897 Tilman Piesk, <a href="http://en.wikiversity.org/wiki/Permutations_by_cycle_type">Permutations by cycle type</a> (Wikiversity article)
%H A181897 Gregory Gerard Wojnar, <a href="/A181897/a181897.txt">Comments on A181897</a>, Sep 29 2020.
%F A181897 T(n,1) = A000217(n).
%F A181897 T(n,2) = A007290(n).
%F A181897 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
%e A181897 Triangle begins:
%e A181897   1;
%e A181897   1,  1;
%e A181897   1,  3,  2;
%e A181897   1,  6,  8,  3,  6;
%e A181897   1, 10, 20, 15, 30,  20,  24;
%e A181897   1, 15, 40, 45, 90, 120, 144, 15, 90, 40, 120;
%e A181897   ...
%t A181897 Table[CoefficientRules[ n! CycleIndex[SymmetricGroup[n], s] // Expand][[All, 2]], {n, 1, 8}] // Grid (* _Geoffrey Critzer_, Nov 09 2014 *)
%t A181897 (* Alternative program *)
%t A181897 partitionMultiplicities[aPartn_]:=Table[Count[aPartn,m],{m,Total[aPartn]}]
%t A181897 partitionBase[aPartn_]:=Sum[m*aPartn[[m]],{m,Length[aPartn]}]
%t A181897 partitionFactorial[aPartn_]:=Product[m^aPartn[[m]],{m,partitionBase[aPartn]}]
%t A181897 partitionParts[aPartn_]:=Sum[aPartn[[m]],{m,Length[aPartn]}]
%t A181897 A181897[aPartn_]:=Multinomial@@aPartn*partitionBase[aPartn]!/(partitionFactorial[aPartn]*partitionParts[aPartn]!)
%t A181897 Grid[Table[Map[A181897,ReverseSort[Map[partitionMultiplicities,Partitions[n]],LexicographicOrder]],{n,2,12}]] (* _Gregory Gerard Wojnar_, Jun 24 2025 *)
%Y A181897 Cf. A000041, A000142, A000166, A198380, A194602, A008290, A073906, A000217, A007290, A385081.
%Y A181897 Cf. A036039 and references therein for different ordering of terms within each row.
%K A181897 tabf,nonn
%O A181897 1,5
%A A181897 _Tilman Piesk_, Mar 31 2012