cp's OEIS Frontend

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

%I A190476 #30 Jul 25 2023 09:25:31
%S A190476 1,0,1,1,3,11,25,127,441,1954,10011,45266,264583,1445380,8585655,
%T A190476 55660801,352151073,2482766225,17559191557,129772490863,1013321885751,
%U A190476 7972553309386,66428256850935,564371629663172,4946383948336009,45027627776367801,416996057365437135
%N A190476 The number of partitions of the set {1,2,...,n} into subsets (blocks,cells) having a prime number of elements.
%C A190476 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.
%H A190476 Alois P. Heinz, <a href="/A190476/b190476.txt">Table of n, a(n) for n = 0..250</a>
%F A190476 E.g.f.: exp(Sum_{p=prime} x^p/p!).
%F A190476 a(0) = 1; a(n) = Sum_{p<=n, p prime} binomial(n-1,p-1) * a(n-p). - _Seiichi Manyama_, Feb 26 2022
%p A190476 with(numtheory):
%p A190476 b:= proc(n, i) option remember; local p;
%p A190476       if n=0 then 1
%p A190476     elif n=1 or i<1 then 0
%p A190476     else p:= ithprime(i);
%p A190476          b(n, i-1) +add(mul(binomial(n-(h-1)*p, p), h=1..j)
%p A190476                     *b(n-j*p, i-1)/j! , j=1..iquo(n,p))
%p A190476       fi
%p A190476     end:
%p A190476 a:= n-> b(n, pi(n)):
%p A190476 seq(a(n), n=0..30); # _Alois P. Heinz_, Nov 02 2011
%t A190476 a= Table[Prime[n],{n,1,20}];
%t A190476   b= Sum[x^i/i!,{i,a}];
%t A190476   Range[0,20]! CoefficientList[Series[Exp[b],{x,0,20}],x]
%o A190476 (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
%o A190476 (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
%Y A190476 Cf. A000110, A364450.
%K A190476 nonn
%O A190476 0,5
%A A190476 _Geoffrey Critzer_, May 10 2011