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,5

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

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

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]

Prog

(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

Crossrefs

Cf. A000110, A364450.

Sequence in context: A352013 A164303 A129082 * A060746 A111935 A175441

Adjacent sequences: A190473 A190474 A190475 * A190477 A190478 A190479

Keyword

nonn

Author

Geoffrey Critzer, May 10 2011

Status

approved