A073906 -id:A073906 - 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

A073910 Smallest number m such that m and the product of digits of m are both divisible by 3n, or 0 if no such number exists.

Original entry on oeis.org

3, 6, 9, 168, 135, 36, 273, 168, 999, 0, 0, 1296, 0, 378, 495, 384, 0, 1296, 0, 0, 1197, 0, 0, 1368, 3525, 0, 2997, 672, 0, 0, 0, 384, 0, 0, 735, 1296, 0, 0, 0, 0, 0, 3276, 0, 0, 3915, 0, 0, 3168, 7497, 0, 0, 0, 0, 5994, 0, 7896, 0, 0, 0, 0, 0, 0, 7938, 2688, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Amarnath Murthy, Aug 18 2002

Here 0 is regarded as not divisible by any number.

a(n) = 0 if 10 divides 3n or n contains a prime divisor > 9. - Sascha Kurz, Aug 23 2002

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A073906, A073908, A073909, A073911, A073912, A085124.

f := 3:for i from 1 to 1000 do b := ifactors(f*i)[2]: if b[nops(b)][1]>9 or (f*i mod 10) =0 then a[i] := 0:else j := 0:while true do j := j+f*i:c := convert(j,base,10):d := product(c[k],k=1..nops(c)): if (d mod f*i)=0 and d>0 then a[i] := j:break:fi:od:fi:od:seq(a[k],k=1..1000);

a(n) = A085124(3*n). - R. J. Mathar, Jun 21 2018

More terms from Sascha Kurz, Aug 23 2002

A087132 a(n) is the sum of the squares of the sizes of the conjugacy classes in the symmetric group S_n.

Original entry on oeis.org

1, 1, 2, 14, 146, 2602, 71412, 2675724, 134269158, 8747088662, 717107850956, 72007758701716, 8736187050160132, 1258160557017484564, 212232765513231245096, 41518913481377118146520, 9309797624034705006898470, 2374942651509463493006400390, 683620331016710787068868581580

Offset: 0

Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 18 2003

nonn

This is a natural quantity to consider when viewing the symmetric group (Sym_n) as a set. a(n) is the sum over all elements of Sym_n of the size of their conjugacy class. Each conjugacy class is thus counted as many times as its size, giving a sum of squares. - Olivier Gérard, Feb 12 2012

Alois P. Heinz, Table of n, a(n) for n = 0..254 (terms n = 1..57 from Vaclav Kotesovec)
Simon R. Blackburn, John R. Britnell, and Mark Wildon, The probability that a pair of elements of a finite group are conjugate, arXiv:1108.1784 [math.GR], 2011-2012.
Philippe Flajolet, Éric Fusy, Xavier Gourdon, Daniel Panario and Nicolas Pouyanne, A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics, arXiv:math/0606370 [math.CO], 2006.

Cf. A000041, A073906, A192983, A206820. - Olivier Gérard, Feb 12 2012

Cf. A000142, A246879.

[ &+[ c[2]^2 : c in ClassesData(Sym(n))] : n in [1..10]]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006

b:= proc(n, i) option remember; uses combinat; `if`(n=0, 1,
      `if`(i<1, 0, add(b(n-i*j, i-1)*((i-1)!^j/j!*
       multinomial(n, n-i*j, i$j, 0))^2, j=0..n/i)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..21);  # Alois P. Heinz, Jul 27 2023

multinomial[n_, k_List] := n! / Times @@ (k!);
b[n_, i_] := b[n, i] = If[n == 0, 1,
    If[i < 1, 0, Sum[b[n-i*j, i-1]*((i-1)!^j/j!*
    multinomial[n, {n-i*j, Sequence@@Table[i, {j}], 0}])^2, {j, 0, n/i}]]];
a[n_] := b[n, n];
Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Mar 29 2024, after Alois P. Heinz *)

a(n) = (n!)^2 * (c/n^2 + O((log n)/n^3)), where c = prod_{k>=1}sum_{n>=0}1/(k*n!)^2 ~ 4.263403514152669778298935... (see A246879). [Corrected by Vaclav Kotesovec, Sep 21 2014]

More terms from Vladeta Jovovic, Oct 22 2003
More terms from Vaclav Kotesovec, Sep 21 2014
a(0)=1 prepended by Alois P. Heinz, Jul 27 2023

A073908 Smallest number m such that m and the product of digits of m are both divisible by 7n, or 0 if no such number exists.

Original entry on oeis.org

7, 378, 273, 476, 175, 378, 3577, 728, 1197, 0, 0, 672, 0, 7742, 735, 784, 0, 3276, 0, 0, 7497, 0, 0, 7896, 1575, 0, 7938, 69776, 0, 0, 0, 12768, 0, 0, 37975, 3276, 0, 0, 0, 0, 0, 71736, 0, 0, 9765, 0, 0, 8736, 47677, 0, 0, 0, 0, 7938, 0, 74872, 0, 0, 0, 0, 0, 0, 7497

Offset: 1

Amarnath Murthy, Aug 18 2002

Here 0 is regarded as not divisible by any number.

a(n) = 0 if n is divisible by 10 or contains a prime divisor > 9. - Sascha Kurz, Aug 23 2002

			a(8) = 728 is divisible by 7*8 = 56 and also 7*2*8 = 112 = 2*56.

Cf. A073906, A085124, A073909, A073910, A073911, A073912.

f := 7:for i from 1 to 400 do b := ifactors(f*i)[2]: if b[nops(b)][1]>9 or (f*i mod 10) =0 then a[i] := 0:else j := 0:while true do j := j+f*i:c := convert(j,base,10): d := product(c[k],k=1..nops(c)): if (d mod f*i)=0 and d>0 then a[i] := j:break:fi: od:fi:od:seq(a[k],k=1..400);

a(n) = A085124(7*n). - R. J. Mathar, Jun 21 2018

More terms from Sascha Kurz, Aug 23 2002

A073909 Smallest number m such that m and the product of digits of m are both divisible by 2n, or 0 if no such number exists.

Original entry on oeis.org

2, 4, 6, 8, 0, 168, 378, 48, 36, 0, 0, 168, 0, 476, 0, 288, 0, 1296, 0, 0, 378, 0, 0, 384, 0, 0, 1296, 728, 0, 0, 0, 448, 0, 0, 0, 1368, 0, 0, 0, 0, 0, 672, 0, 0, 0, 0, 0, 384, 7742, 0, 0, 0, 0, 1296, 0, 784, 0, 0, 0, 0, 0, 0, 3276, 2688, 0, 0, 0, 0, 0, 0, 0, 3168, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Amarnath Murthy, Aug 18 2002

Here 0 is regarded as not divisible by any number.

a(n) = 0 if n is divisible by 5 or contains a prime divisor > 9. - Sascha Kurz, Aug 23 2002

Cf. A073906, A085124, A073908, A073910, A073911, A073912.

f := 2:for i from 1 to 400 do b := ifactors(f*i)[2]: if b[nops(b)][1]>9 or (f*i mod 10) =0 then a[i] := 0:else j := 0:while true do j := j+f*i:c := convert(j,base,10): d := product(c[k],k=1..nops(c)): if (d mod f*i)=0 and d>0 then a[i] := j:break:fi: od:fi:od:seq(a[k],k=1..400);

a(n) = A085124(2*n). - R. J. Mathar, Jun 21 2018

More terms from Sascha Kurz, Aug 23 2002

A073911 Smallest number m such that m and the product of digits of m are both divisible by 5n, or 0 if no such number exists.

Original entry on oeis.org

5, 0, 135, 0, 525, 0, 175, 0, 495, 0, 0, 0, 0, 0, 3525, 0, 0, 0, 0, 0, 735, 0, 0, 0, 55125, 0, 3915, 0, 0, 0, 0, 0, 0, 0, 1575, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15975, 0, 0, 0, 37975, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9765, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 155625, 0, 0, 0, 0, 0, 31995, 0, 0

Offset: 1

Amarnath Murthy, Aug 18 2002

Here 0 is regarded as not divisible by any number.

a(n) = 0 if n is divisible by 2 or contains a prime divisor > 9. - Sascha Kurz, Aug 23 2002

Cf. A073906, A085124, A073908, A073909, A073910, A073912.

f := 5:for i from 1 to 400 do b := ifactors(f*i)[2]: if b[nops(b)][1]>9 or (f*i mod 10) =0 then a[i] := 0:else j := 0:while true do j := j+f*i:c := convert(j,base,10): d := product(c[k],k=1..nops(c)): if (d mod f*i)=0 and d>0 then a[i] := j:break:fi: od:fi:od:seq(a[k],k=1..400);

a(n) = A085124(5*n). - R. J. Mathar, Jun 21 2018

More terms from Sascha Kurz, Aug 23 2002

A073912 Smallest number m such that m and the product of digits of m are both divisible by 8n, or 0 if no such number exists.

Original entry on oeis.org

8, 48, 168, 288, 0, 384, 728, 448, 1368, 0, 0, 384, 0, 784, 0, 2688, 0, 3168, 0, 0, 7896, 0, 0, 2688, 0, 0, 4968, 12768, 0, 0, 0, 4864, 0, 0, 0, 4896, 0, 0, 0, 0, 0, 8736, 0, 0, 0, 0, 0, 2688, 74872, 0, 0, 0, 0, 22896, 0, 14784, 0, 0, 0, 0, 0, 0, 33768, 14848, 0, 0, 0, 0, 0

Offset: 1

Amarnath Murthy, Aug 18 2002

Here 0 is regarded as not divisible by any number.

a(n) = 0 if 5 divides n or n contains a prime divisor > 9. - Sascha Kurz, Aug 23 2002 [Corrected by Sean A. Irvine, Dec 23 2024]

Cf. A073906, A085124, A073908, A073909, A073910, A073911.

f := 8:for i from 1 to 400 do b := ifactors(f*i)[2]: if b[nops(b)][1]>9 or (f*i mod 10) =0 then a[i] := 0:else j := 0:while true do j := j+f*i:c := convert(j,base,10): d := product(c[k],k=1..nops(c)): if (d mod f*i)=0 and d>0 then a[i] := j:break:fi: od:fi:od:seq(a[k],k=1..400);

a(n) = A085124(8*n). - R. J. Mathar, Jun 21 2018

More terms from Sascha Kurz, Aug 23 2002

A102465 a(n) = number of distinct values of Product_{i=1..r} x_i!i!^x_i, where (x_1, ..., x_r) is an r-tuple of nonnegative integers with Sum_{i=1..r} ix_i = n.

Original entry on oeis.org

1, 1, 2, 4, 4, 7, 7, 13, 17, 23, 26, 40, 45, 60, 64, 102, 115, 148, 169, 225, 261, 337, 375, 470, 552, 668, 780, 954, 1078, 1331, 1469, 1811, 2055, 2475, 2776, 3343, 3764, 4447, 4983, 5898, 6622, 7771, 8646, 10192, 11403, 13238, 14680, 17011, 19010, 21877

Offset: 1

Vladeta Jovovic, Feb 23 2005

nonn

Cf. A073906.

Cf. A102462, A102463.

b:= proc(n, i) option remember; `if`(n=0, {1}, `if`(i<1, {},
       {seq(map(x-> x*i!^j*j!, b(n-i*j, i-1))[], j=0..n/i)})) end:
a:= n-> nops(b(n, n)):
seq(a(n), n=1..40);    # Alois P. Heinz, Apr 13 2012

b[n_, i_] := b[n, i] = If[n == 0, {1}, If[i < 1, {}, Table[# i!^j j!& /@ b[n - i j, i - 1], {j, 0, n/i}] // Flatten // Union]];
a[n_] := Length[b[n, n]];
Array[a, 40] (* Jean-François Alcover, Nov 09 2020, after Alois P. Heinz *)

More terms from David Wasserman, Apr 11 2008

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

A073910 Smallest number m such that m and the product of digits of m are both divisible by 3n, or 0 if no such number exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

Extensions

A087132 a(n) is the sum of the squares of the sizes of the conjugacy classes in the symmetric group S_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

Extensions

A073908 Smallest number m such that m and the product of digits of m are both divisible by 7n, or 0 if no such number exists.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

Extensions

A073909 Smallest number m such that m and the product of digits of m are both divisible by 2n, or 0 if no such number exists.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Formula

Extensions

A073911 Smallest number m such that m and the product of digits of m are both divisible by 5n, or 0 if no such number exists.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Formula

Extensions

A073912 Smallest number m such that m and the product of digits of m are both divisible by 8n, or 0 if no such number exists.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Formula

Extensions

A102465 a(n) = number of distinct values of Product_{i=1..r} x_i!*i!^x_i, where (x_1, ..., x_r) is an r-tuple of nonnegative integers with Sum_{i=1..r} i*x_i = n.

Views

Author

A102465 a(n) = number of distinct values of Product_{i=1..r} x_i!i!^x_i, where (x_1, ..., x_r) is an r-tuple of nonnegative integers with Sum_{i=1..r} ix_i = n.