A271426 -id:A271426 - cp's OEIS frontend

A271424 Number T(n,k) of set partitions of [n] with minimal block length multiplicity equal to k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 0, 4, 0, 1, 0, 11, 3, 0, 1, 0, 51, 0, 0, 0, 1, 0, 132, 55, 15, 0, 0, 1, 0, 771, 105, 0, 0, 0, 0, 1, 0, 3089, 945, 0, 105, 0, 0, 0, 1, 0, 18388, 1218, 1540, 0, 0, 0, 0, 0, 1, 0, 96423, 15456, 3150, 0, 945, 0, 0, 0, 0, 1, 0, 627529, 26785, 24255, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 0

Alois P. Heinz, Apr 07 2016

At least one block length occurs exactly k times, and all block lengths occur at least k times.

			T(4,1) = 11: 1234, 123|4, 124|3, 12|3|4, 134|2, 13|2|4, 1|234, 1|23|4, 14|2|3, 1|24|3, 1|2|34.
T(4,2) = 3: 12|34, 13|24, 14|23.
T(4,4) = 1: 1|2|3|4.
T(6,3) = 15: 12|34|56, 12|35|46, 12|36|45, 13|24|56, 13|25|46, 13|26|45, 14|23|56, 15|23|46, 16|23|45, 14|25|36, 14|26|35, 15|24|36, 16|24|35, 15|26|34, 16|25|34.
Triangle T(n,k) begins:
  1;
  0,     1;
  0,     1,     1;
  0,     4,     0,    1;
  0,    11,     3,    0,   1;
  0,    51,     0,    0,   0,   1;
  0,   132,    55,   15,   0,   0, 1;
  0,   771,   105,    0,   0,   0, 0, 1;
  0,  3089,   945,    0, 105,   0, 0, 0, 1;
  0, 18388,  1218, 1540,   0,   0, 0, 0, 0, 1;
  0, 96423, 15456, 3150,   0, 945, 0, 0, 0, 0, 1;

Alois P. Heinz, Rows n = 0..140, flattened
Wikipedia, Partition of a set

Columns k=0-10 give A000007, A271426, A271762, A271763, A271764, A271765, A271766, A271767, A271768, A271769, A271770.
Row sums give A000110.
Main diagonal gives A000012.
T(2n,n) gives A001147.
T(3n,n) gives A271715.
Cf. A271423.

with(combinat):
b:= proc(n, i, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(multinomial(n, n-i*j, i$j)
        *b(n-i*j, i-1, k)/j!, j={0, $k..n/i})))
    end:
T:= (n, k)-> b(n$2, k)-`if`(n=k,0,b(n$2, k+1)):
seq(seq(T(n, k), k=0..n), n=0..12);

multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i<1, 0, Sum[multinomial[n, Join[{n-i*j}, Array[i&, j]]]* b[n-i*j, i-1, k]/j!, {j, Join[{0}, Range[k, n/i]] // Union}]]]; T[n_, k_] := b[n, n, k] - If[n == k, 0, b[n, n, k + 1]]; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 16 2017, adapted from Maple *)

A318120 Number of set partitions of {1,...,n} with relatively prime block sizes.

Original entry on oeis.org

1, 1, 1, 4, 11, 51, 162, 876, 3761, 20782, 109293, 678569, 4038388, 27644436, 186524145, 1379760895, 10323844183, 82864869803, 674798169662, 5832742205056, 51385856585637, 474708148273586, 4486977535287371, 44152005855084345, 444577220573083896

Offset: 0

Gus Wiseman, Dec 16 2018

nonn

			The a(4) = 11 set partitions:
  {{1},{2},{3},{4}}
   {{1},{2},{3,4}}
   {{1},{2,3},{4}}
   {{1},{2,4},{3}}
   {{1,2},{3},{4}}
   {{1,3},{2},{4}}
   {{1,4},{2},{3}}
    {{1},{2,3,4}}
    {{1,2,3},{4}}
    {{1,2,4},{3}}
    {{1,3,4},{2}}

Alois P. Heinz, Table of n, a(n) for n = 0..576

a(n) >= A271426(n).

Cf. A000110, A000258, A000311, A000670, A000740, A000837, A005651, A005804, A008277, A124794, A319182, A320289.

b:= proc(n, t) option remember; `if`(n=0, `if`(t<2, 1, 0),
      add(b(n-j, igcd(t, j))*binomial(n-1, j-1), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..25);  # Alois P. Heinz, Dec 30 2019

numSetPtnsOfType[ptn_]:=Total[ptn]!/Times@@Factorial/@ptn/Times@@Factorial/@Length/@Split[ptn];
Table[Total[numSetPtnsOfType/@Select[IntegerPartitions[n],GCD@@#==1&]],{n,10}]
(* Second program: *)
b[n_, t_] := b[n, t] = If[n == 0, If[t < 2, 1, 0],
     Sum[b[n - j, GCD[t, j]]*Binomial[n - 1, j - 1], {j, 1, n}]];
a[n_] := b[n, 0];
a /@ Range[0, 25] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)

a(n) = Sum_{|y| = n, GCD(y) = 1} n! / (Product_i y_i! * Product_i (y)_i!) where the sum is over all relatively prime integer partitions of n and (y)_i is the multiplicity of i in y.

cp's OEIS Frontend

A271424 Number T(n,k) of set partitions of [n] with minimal block length multiplicity equal to k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica