A194602 -id:A194602 - 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).

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

Tilman Piesk, Mar 31 2012

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

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

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.

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

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

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

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

A249620 Triangle read by rows: T(m,n) = number of partitions of the multiset with m elements and signature corresponding to n-th integer partition (A194602).

Original entry on oeis.org

1, 1, 2, 2, 5, 4, 3, 15, 11, 7, 9, 5, 52, 36, 21, 26, 12, 16, 7, 203, 135, 74, 92, 38, 52, 19, 66, 29, 31, 11, 877, 566, 296, 371, 141, 198, 64, 249, 98, 109, 30, 137, 47, 57, 15, 4140, 2610, 1315, 1663, 592, 850, 250, 1075, 392, 444, 105, 560

Offset: 0

Tilman Piesk, Nov 04 2014

This triangle shows the same numbers in each row as A129306 and A096443, but in this arrangement the multisets in column n correspond to the n-th integer partition in the infinite order defined by A194602.
Row lengths: A000041 (partition numbers), Row sums: A035310
Columns: 0: A000110 (Bell), 1: A035098 (near-Bell), 2: A169587, 4: A169588
Last in row: end-1: A091437, end: A000041 (partition numbers)
The rightmost columns form a reflected version of the triangle A126442:
  n      0     1     2     4    6   10  14  21      (A000041(1,2,3...)-1)
m
1        1
2        2     2
3        5     4     3
4       15    11     7     5
5       52    36    21    12    7
6      203   135    74    38   19   11
7      877   566   296   141   64   30  15
8     4140  2610  1315   592  250  105  45  22
A249619 shows the number of permutations of the same multisets.

			See "The T(5,2)=21 partitions of {1,1,1,2,3}" link. Similar links for m=1..8 are in "Partitions of multisets" (Wikiversity).
Triangle begins:
  n     0    1   2   3   4   5   6   7   8   9  10
m
0       1
1       1
2       2    2
3       5    4   3
4      15   11   7   9   5
5      52   36  21  26  12  16   7
6     203  135  74  92  38  52  19  66  29  31  11

Tilman Piesk, Triangle rows m=0..8, flattened.
Tilman Piesk, Partitions of multisets (Wikiversity)
Tilman Piesk, The T(5,2)=21 partitions of {1,1,1,2,3}
Tilman Piesk, PHP code used to calculate the examples

Cf. A129306, A096443, A035310, A194602, A249619, A000041, A126442

A198380 Cycle type of the n-th finite permutation represented by index number of A194602.

Original entry on oeis.org

0, 1, 1, 2, 2, 1, 1, 3, 2, 4, 4, 2, 2, 4, 1, 2, 3, 4, 4, 2, 2, 1, 4, 3, 1, 3, 3, 5, 5, 3, 2, 5, 4, 6, 6, 4, 4, 6, 2, 4, 5, 6, 6, 4, 4, 2, 6, 5, 2, 5, 4, 6, 6, 4, 1, 3, 2, 4, 4, 2, 3, 5, 4, 6, 6, 5, 5, 3, 6, 4, 5, 6, 4, 6, 2, 4, 5, 6, 2, 4, 1, 2, 3, 4, 4, 6

Offset: 0

Tilman Piesk, Oct 23 2011

nonn

This sequence shows the cycle type of each finite permutation (A195663) as the index number of the corresponding partition. (When a permutation has a 3-cycle and a 2-cycle, this corresponds to the partition 3+2, etc.) Partitions can be ordered, so each partition can be denoted by its index in this order, e.g. 6 for the partition 3+2. Compare A194602.
From the properties of A194602 follows:
Entries 1,2,4,6,10,14,21...     ( A000041(n)-1 from n=2 ) correspond to permutations with exactly one n-cycle (and no other cycles).
Entries 1,3,7,15,30,56,101...   ( A000041(2n-1) from n=1 ) correspond to permutations with exactly n 2-cycles (and no other cycles), so these are the symmetric permutations.
Entries n = 1,3,4,7,9,10,12...  ( A194602(n) has an even binary digit sum ) correspond to even permutations. This goes along with the fact, that a permutation is even when its partition contains an even number of even addends.
(Compare "Table for A194602" in section LINKS. Concerning the first two properties see especially the end of this file.)

Tilman Piesk, Table of n, a(n) for n = 0..5039
Tilman Piesk, Table including permutations of 8 elements and partitions written as sums for n = 0..40319
Tilman Piesk, Permutations by cycle type (Wikiversity article)
Tilman Piesk, Table for A194602

Cf. A195663, A195664, A055089 (ordered finite permutations).
Cf. A194602 (ordered partitions interpreted as binary numbers).
Cf. A181897 (number of n-permutations with cycle type k).

Changed offset to 0 by Tilman Piesk, Jan 25 2012

A211350 Refined triangle A124323: T(n,k) is the number of partitions of an n-set that are of type k (k-th integer partition, defined by A194602).

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 6, 4, 3, 1, 1, 10, 10, 15, 5, 10, 1, 1, 15, 20, 45, 15, 60, 6, 15, 15, 10, 1, 1, 21, 35, 105, 35, 210, 21, 105, 105, 70, 7, 105, 21, 35, 1, 1, 28, 56, 210, 70, 560, 56, 420, 420, 280, 28, 840, 168, 280, 8, 105, 210, 280, 28

Offset: 1

Tilman Piesk, Apr 09 2012

Name could also be "Triangle of multinomial coefficients, read by rows (version 4)", compare A036040, A080575, A178867. The latter and this one differ only in the order of columns.
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,5,15,52,203... (Bell numbers A000110)
Row maxima: 1,1,3,6,15,60,210,840,3780,12600,69300,415800... (A102356)
Distinct entries per row: 1,1,2,4,4,7,7,13,17,23,26,40... (A102465)
Rightmost columns are those from Pascal's triangle A007318 without the second one (i.e. triangle A184049). The other columns - (always?) without a 1 at the top - are multiples of these columns from Pascal's triangle; so actually only the top elements of each column are needed to calculate the other entries; these top elements are in A211360. (The top elements of the related triangle A178867 are in A178866.)

Tilman Piesk, Rows n=1..12 of triangle, flattened
Tilman Piesk, Partition related number triangles

Cf. A124323, A194602, A178867, A000041, A000110, A102356, A102465, A184049, A211360.

A211351 Refined triangle A091867: T(n,k) is the number of noncrossing partitions of an n-set that are of type k (k-th integer partition, defined by A194602).

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 6, 4, 2, 1, 1, 10, 10, 10, 5, 5, 1, 1, 15, 20, 30, 15, 30, 6, 5, 6, 3, 1, 1, 21, 35, 70, 35, 105, 21, 35, 42, 21, 7, 21, 7, 7, 1, 1, 28, 56, 140, 70, 280, 56, 140, 168, 84, 28, 168, 56, 56, 8, 14, 28, 28, 8, 8, 4, 1

Offset: 1

Tilman Piesk, Apr 09 2012

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,5,14,42,132... (Catalan numbers A000108)
Row maxima: 1,1,3,6,10,30,105,280,756,2520,6930,18480 (A130760)
Distinct entries per row: 1,1,2,4,3,7,7,11,12,18,18,30
Rightmost columns are those from Pascal's triangle A007318 without the second one (i.e. triangle A184049). The other columns - (always?) without a 1 at the top - are multiples of these columns from Pascal's triangle; so actually only the top elements of each column are needed to calculate the other entries; these top elements are in A211361.

Tilman Piesk, Rows n=1..12 of triangle, flattened
Tilman Piesk, Partition related number triangles

Cf. A091867, A000108, A130760, A184049, A211361.

A249619 Triangle T(m,n) = number of permutations of a multiset with m elements and signature corresponding to n-th integer partition (A194602).

Original entry on oeis.org

1, 1, 2, 1, 6, 3, 1, 24, 12, 4, 6, 1, 120, 60, 20, 30, 5, 10, 1, 720, 360, 120, 180, 30, 60, 6, 90, 15, 20, 1, 5040, 2520, 840, 1260, 210, 420, 42, 630, 105, 140, 7, 210, 21, 35, 1, 40320, 20160, 6720, 10080, 1680, 3360, 336, 5040, 840, 1120, 56

Offset: 0

Tilman Piesk, Nov 04 2014

This triangle shows the same numbers in each row as A036038 and A078760 (the multinomial coefficients), but in this arrangement the multisets in column n correspond to the n-th integer partition in the infinite order defined by A194602.
Row lengths: A000041 (partition numbers), Row sums: A005651
Columns: 0: A000142 (factorials), 1: A001710, 2: A001715, 3: A133799, 4: A001720, 6: A001725, 10: A001730, 14: A049388
Last in row: end-2: A037955 after 1 term mismatch, end-1: A001405, end: A000012
The rightmost columns form the triangle A173333:
  n       0      1     2     4    6  10  14  21      (A000041(1,2,3...)-1)
m
1         1
2         2      1
3         6      3     1
4        24     12     4     1
5       120     60    20     5    1
6       720    360   120    30    6   1
7      5040   2520   840   210   42   7   1
8     40320  20160  6720  1680  336  56   8   1
A249620 shows the number of partitions of the same multisets. A187783 shows the number of permutations of special multisets.

			Triangle begins:
  n     0    1    2    3   4   5  6   7   8   9 10
m
0       1
1       1
2       2    1
3       6    3    1
4      24   12    4    6   1
5     120   60   20   30   5  10  1
6     720  360  120  180  30  60  6  90  15  20  1

Tilman Piesk, Triangle rows m=0..25, flattened
Tilman Piesk, Illustration of the multisets for m=0..6

Cf. A036038, A078760, A005651, A005651, A249620, A000041, A173333.

A211352 Refined triangle A211356: T(n,k) is the number of partitions up to rotation of an n-set that are of type k (k-th integer partition, defined by A194602).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 2, 2, 3, 1, 2, 1, 1, 3, 4, 9, 3, 10, 1, 5, 3, 3, 1, 1, 3, 5, 15, 5, 30, 3, 15, 15, 10, 1, 15, 3, 5, 1, 1, 4, 7, 29, 10, 70, 7, 56, 54, 37, 4, 105, 21, 35, 1, 18, 29, 37, 4, 7, 7, 1

Offset: 1

Tilman Piesk, Apr 09 2012

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,3,7,12,43... (A084423)
Row maxima: 1,1,1,2,3,10,30,105,420,1268,6300...
Distinct entries per row: 1,1,1,2,3,6,6,13,17,25,25...
Rightmost columns are those from the triangle of circular binomial coefficients A047996 without the second column (i.e.triangle A037306).

Tilman Piesk, Rows n=1..11 of triangle, flattened
Tilman Piesk, Partition related number triangles

Cf. A211356, A000041, A084423, A047996, A037306.

A211353 Refined triangle A211357: T(n,k) is the number of noncrossing partitions up to rotation of an n-set that are of type k (k-th integer partition, defined by A194602).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 3, 4, 6, 3, 5, 1, 2, 1, 1, 1, 1, 3, 5, 10, 5, 15, 3, 5, 6, 3, 1, 3, 1, 1, 1, 1, 4, 7, 19, 10, 35, 7, 19, 21, 12, 4, 21, 7, 7, 1, 3, 4, 4, 1, 1, 1, 1, 1, 4, 10, 28, 14, 70, 14, 48, 56, 28, 10

Offset: 1

Tilman Piesk, Apr 09 2012

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,3,6,10,28... (A054357)
Row maxima: 1,1,1,2,2,6,15,35,84,252,630,1542...
Distinct entries per row: 1,1,1,2,2,6,6,9,11,17,17,30...
Rightmost columns are those from the triangle of circular binomial coefficients A047996 without the second column (i.e.triangle A037306).

Tilman Piesk, Rows n=1..12 of triangle, flattened
Tilman Piesk, Partition related number triangles

Cf. A211357, A000041, A054357, A047996, A037306.

A211354 Refined triangle A211358: T(n,k) is the number of partitions up to rotation and reflection of an n-set that are of type k (k-th integer partition, defined by A194602).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 2, 2, 3, 1, 2, 1, 1, 3, 3, 8, 3, 6, 1, 5, 3, 3, 1, 1, 3, 4, 12, 4, 18, 3, 11, 9, 7, 1, 12, 3, 4, 1, 1, 4, 5, 22, 8, 38, 5, 39, 33, 25, 4, 57, 12, 19, 1, 17, 22, 25, 4, 5, 7, 1, 1, 4, 7, 30, 10, 76, 10, 85, 76, 55

Offset: 1

Tilman Piesk, Apr 09 2012

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,3,7,12,37... (A084708)
Row maxima: 1,1,1,2,3,8,18,57,228,668,3220
Distinct entries per row: 1,1,1,2,3,5,8,14,17,26,30
Rightmost columns are those from the triangle A052307  without the second column.

Tilman Piesk, Rows n=1..11 of triangle, flattened
Tilman Piesk, Partition related number triangles

Cf. A211358, A000041, A084708, A052307.

A211355 Refined triangle A211359: T(n,k) is the number of noncrossing partitions up to rotation and reflection of an n-set that are of type k (k-th integer partition, defined by A194602).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 3, 3, 5, 3, 3, 1, 2, 1, 1, 1, 1, 3, 4, 8, 4, 9, 3, 4, 4, 2, 1, 3, 1, 1, 1, 1, 4, 5, 14, 8, 19, 5, 14, 13, 8, 4, 12, 4, 4, 1, 3, 4, 3, 1, 1, 1, 1, 1, 4, 7, 20, 10, 38, 10, 30, 32, 16, 7, 48

Offset: 1

Tilman Piesk, Apr 09 2012

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,3,6,10,24... (A111275)
Row maxima: 1,1,1,2,2,5,9,19,48,132,330,781
Distinct entries per row: 1,1,1,2,2,4,6,9,15,21,28,43
Rightmost columns are those from the triangle A052307  without the second column.

Tilman Piesk, Rows n=1..12 of triangle, flattened
Tilman Piesk, Partition related number triangles

Cf. A211359, A000041, A111275, A052307.

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A249620 Triangle read by rows: T(m,n) = number of partitions of the multiset with m elements and signature corresponding to n-th integer partition (A194602).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A198380 Cycle type of the n-th finite permutation represented by index number of A194602.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A211350 Refined triangle A124323: T(n,k) is the number of partitions of an n-set that are of type k (k-th integer partition, defined by A194602).

Views

Author

Keywords

Comments

Links

Crossrefs

A211351 Refined triangle A091867: T(n,k) is the number of noncrossing partitions of an n-set that are of type k (k-th integer partition, defined by A194602).

Views

Author

Keywords

Comments

Links

Crossrefs

A249619 Triangle T(m,n) = number of permutations of a multiset with m elements and signature corresponding to n-th integer partition (A194602).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A211352 Refined triangle A211356: T(n,k) is the number of partitions up to rotation of an n-set that are of type k (k-th integer partition, defined by A194602).

Views

Author

Keywords

Comments

Links

Crossrefs

A211353 Refined triangle A211357: T(n,k) is the number of noncrossing partitions up to rotation of an n-set that are of type k (k-th integer partition, defined by A194602).

Views

Author

Keywords

Comments

Links

Crossrefs

A211354 Refined triangle A211358: T(n,k) is the number of partitions up to rotation and reflection of an n-set that are of type k (k-th integer partition, defined by A194602).

Views

Author

Keywords

Comments

Links

Crossrefs

A211355 Refined triangle A211359: T(n,k) is the number of noncrossing partitions up to rotation and reflection of an n-set that are of type k (k-th integer partition, defined by A194602).

Views

Author

Keywords

Comments

Links

Crossrefs