A190476 The number of partitions of the set {1,2,...,n} into subsets (blocks,cells) having a prime number of elements.

1, 0, 1, 1, 3, 11, 25, 127, 441, 1954, 10011, 45266, 264583, 1445380, 8585655, 55660801, 352151073, 2482766225, 17559191557, 129772490863, 1013321885751, 7972553309386, 66428256850935, 564371629663172, 4946383948336009, 45027627776367801, 416996057365437135

Offset: 0

Author

Geoffrey Critzer, May 10 2011

Keywords

• nonn

Comments

Equivalently, a(n) is the number of equivalence relations on a set of n distinct elements such that each equivalence class contains a prime number of elements.

Links

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

Crossrefs

Cf. A000110, A364450.

Programs

Maple

with(numtheory):
b:= proc(n, i) option remember; local p;
      if n=0 then 1
    elif n=1 or i<1 then 0
    else p:= ithprime(i);
         b(n, i-1) +add(mul(binomial(n-(h-1)*p, p), h=1..j)
                    *b(n-j*p, i-1)/j! , j=1..iquo(n,p))
      fi
    end:
a:= n-> b(n, pi(n)):
seq(a(n), n=0..30); # Alois P. Heinz, Nov 02 2011

Mathematica

a= Table[Prime[n],{n,1,20}];
  b= Sum[x^i/i!,{i,a}];
  Range[0,20]! CoefficientList[Series[Exp[b],{x,0,20}],x]

PARI

my(N=40, x='x+O('x^N)); Vec(serlaplace(exp(sum(k=1, N, isprime(k)*x^k/k!)))) \\ Seiichi Manyama, Feb 26 2022

PARI

a(n) = if(n==0, 1, sum(k=1, n, isprime(k)*binomial(n-1, k-1)*a(n-k))); \\ Seiichi Manyama, Feb 26 2022

Formula

E.g.f.: exp(Sum_{p=prime} x^p/p!).

a(0) = 1; a(n) = Sum_{p<=n, p prime} binomial(n-1,p-1) * a(n-p). - Seiichi Manyama, Feb 26 2022