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

%I #109 Apr 16 2023 20:36:10

%S 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 90,40,120,1,21,70,105,210,420,504,105,630,280,840,210,504,420,720,1,

%U 28,112,210,420,1120,1344,420,2520,1120,3360,1680,4032

%N 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 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 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 The rows are counted from 1, the columns from 0.

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

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

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

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

%C 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

%H 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 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 Tilman Piesk, <a href="http://en.wikiversity.org/wiki/Permutations_by_cycle_type">Permutations by cycle type</a> (Wikiversity article)

%H Gregory Gerard Wojnar, <a href="/A181897/a181897.txt">Comments on A181897</a>, Sep 29 2020

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

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

%F 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 Triangle begins:

%e 1;

%e 1, 1;

%e 1, 3, 2;

%e 1, 6, 8, 3, 6;

%e 1, 10, 20, 15, 30, 20, 24;

%e 1, 15, 40, 45, 90, 120, 144, 15, 90, 40, 120;

%e ...

%t Table[CoefficientRules[ n! CycleIndex[SymmetricGroup[n], s] // Expand][[All, 2]], {n, 1, 8}] // Grid (* _Geoffrey Critzer_, Nov 09 2014 *)

%Y Cf. A000041, A000142, A198380, A194602, A008290, A073906, A000217, A007290.

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

%K tabf,nonn

%O 1,5

%A _Tilman Piesk_, Mar 31 2012