A198380 -id:A198380 - cp's OEIS frontend

A195663 Array read by antidiagonals: Consecutive finite permutations of positive integers in reverse colexicographic order.

1, 2, 2, 3, 1, 1, 4, 3, 3, 3, 5, 4, 2, 1, 2, 6, 5, 4, 2, 3, 3, 7, 6, 5, 4, 1, 2, 1, 8, 7, 6, 5, 4, 1, 2, 2, 9, 8, 7, 6, 5, 4, 4, 1, 1, 10, 9, 8, 7, 6, 5, 3, 4, 4, 4, 11, 10, 9, 8, 7, 6, 5, 3, 2, 1, 2, 12, 11, 10, 9, 8, 7, 6, 5, 3, 2, 4, 4, 13, 12, 11, 10, 9, 8, 7, 6, 5, 3, 1, 2, 1, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 3, 1, 3, 3

Offset: 0

Tilman Piesk, Sep 22 2011

Row n is the n-th finite permutation of {1,2,3,4,...}.

			The first 24 permutations of positive integers in rev colex order:
00  -->  1 2 3 4 5 6 7 8 ...
01  -->  2 1 3 4 ...
02  -->  1 3 2 4 ...
03  -->  3 1 2 4 ...
04  -->  2 3 1 4 ...
05  -->  3 2 1 4 ...
06  -->  1 2 4 3 ...
07  -->  2 1 4 3 ...
08  -->  1 4 2 3 ...
09  -->  4 1 2 3 ...
10  -->  2 4 1 3 ...
11  -->  4 2 1 3 ...
12  -->  1 3 4 2 ...
13  -->  3 1 4 2 ...
14  -->  1 4 3 2 ...
15  -->  4 1 3 2 ...
16  -->  3 4 1 2 ...
17  -->  4 3 1 2 ...
18  -->  2 3 4 1 ...
19  -->  3 2 4 1 ...
20  -->  2 4 3 1 ...
21  -->  4 2 3 1 ...
22  -->  3 4 2 1 ...
23  -->  4 3 2 1 ...

Tilman Piesk, Table of n, a(n) for n = 0..7259
Tilman Piesk, Detailed table of the 24 permutations of 1...4
Tilman Piesk, Table of the 40320 permutations of 1...8, a supporting file of A198380
OEIS-Wiki, Orderings section rev colex
Tilman Piesk, MATLAB code used for the calculation

Cf. A055089 (a very compact representation of these permutations).

Cf. A195664 (same for nonnegative integers, so all entries are smaller by 1).

a(n) = A195664(n)+1.

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

Original entry on oeis.org

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

A055090 Number of cycles (excluding fixed points) of the n-th finite permutation in reversed colexicographic ordering (A055089).

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2

Offset: 0

Antti Karttunen, Apr 18 2000

nonn

Among the first n! entries k appears A136394(n,k) times. - Tilman Piesk, Apr 06 2012

Tilman Piesk, Table of n, a(n) for n = 0..5039
Tilman Piesk, Table for A198380 (a[n] is the number of addends in parentheses on the right of this table)
Tilman Piesk, Permutations and partitions in the OEIS (Wikiversity)
Index entries for sequences related to factorial base representation

Cf. A195663, A195664, A055089 (ordered finite permutations).
Cf. A198380 (cycle type of the n-th finite permutation).
Cf. A136394, A055089, A055090, A055093, A055091, A060128, A290095.

with(group); seq(nops(convert(PermRevLexUnrank(j),'disjcyc')),j=0..)];
# Procedure PermRevLexUnrank given in A055089.

a(n) = A055093(n) - A055091(n).

a(n) = A056170(A290095(n)) = A060128(A060126(n)). - Antti Karttunen, Dec 30 2017

Name changed by Tilman Piesk, Apr 06 2012

A195664 Array read by antidiagonals: Consecutive finite permutations of nonnegative integers in reverse colexicographic order.

Original entry on oeis.org

0, 1, 1, 2, 0, 0, 3, 2, 2, 2, 4, 3, 1, 0, 1, 5, 4, 3, 1, 2, 2, 6, 5, 4, 3, 0, 1, 0, 7, 6, 5, 4, 3, 0, 1, 1, 8, 7, 6, 5, 4, 3, 3, 0, 0, 9, 8, 7, 6, 5, 4, 2, 3, 3, 3, 10, 9, 8, 7, 6, 5, 4, 2, 1, 0, 1, 11, 10, 9, 8, 7, 6, 5, 4, 2, 1, 3, 3, 12, 11, 10, 9, 8, 7, 6, 5, 4, 2, 0, 1, 0, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 2, 0, 2, 2

Offset: 0

Tilman Piesk, Sep 22 2011

Row n is the n-th finite permutation of {0,1,2,3...}.

			The first 24 permutations of nonnegative integers in rev colex order:
00  -->  0 1 2 3 4 5 6 7 ...
01  -->  1 0 2 3 ...
02  -->  0 2 1 3 ...
03  -->  2 0 1 3 ...
04  -->  1 2 0 3 ...
05  -->  2 1 0 3 ...
06  -->  0 1 3 2 ...
07  -->  1 0 3 2 ...
08  -->  0 3 1 2 ...
09  -->  3 0 1 2 ...
10  -->  1 3 0 2 ...
11  -->  3 1 0 2 ...
12  -->  0 2 3 1 ...
13  -->  2 0 3 1 ...
14  -->  0 3 2 1 ...
15  -->  3 0 2 1 ...
16  -->  2 3 0 1 ...
17  -->  3 2 0 1 ...
18  -->  1 2 3 0 ...
19  -->  2 1 3 0 ...
20  -->  1 3 2 0 ...
21  -->  3 1 2 0 ...
22  -->  2 3 1 0 ...
23  -->  3 2 1 0 ...

Tilman Piesk, Table of n, a(n) for n = 0..7259
Tilman Piesk, Detailed table of the 24 permutations of 1...4 (A195663)
Tilman Piesk, Table of the 40320 permutations of 1...8, a supporting file of A198380
OEIS-Wiki, Orderings section rev colex

Cf. A195663 (same for positive integers, so all entries are bigger by 1).

a(n) = A195663(n)-1.

cp's OEIS Frontend

A195663 Array read by antidiagonals: Consecutive finite permutations of positive integers in reverse colexicographic order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

A055090 Number of cycles (excluding fixed points) of the n-th finite permutation in reversed colexicographic ordering (A055089).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

Extensions

A195664 Array read by antidiagonals: Consecutive finite permutations of nonnegative integers in reverse colexicographic order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula