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,5

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

Links

Table of n, a(n) for n=1..57.

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.

Tilman Piesk, Permutations by cycle type (Wikiversity article)

Gregory Gerard Wojnar, Comments on A181897, Sep 29 2020

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

Example

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

Mathematica

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

Crossrefs

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

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

Sequence in context: A114586 A052174 A227790 * A337977 A212207 A111049

Adjacent sequences: A181894 A181895 A181896 * A181898 A181899 A181900

Keyword

tabf,nonn

Author

Tilman Piesk, Mar 31 2012

Status

approved