OFFSET
0,4
COMMENTS
In the present entry, the prime-intersection graph is the graph whose vertices are the subsets of {1,...,n}, and two subsets are adjacent when the cardinality of their intersection is a prime number.
If |A| = k then deg_n(k) = 2^(n-k) * Sum_{p prime, p <= k} binomial(k,p), minus 1 if k is prime.
a(n) is odd iff n == 3 (mod 4). Sketch: modulo 4, terms with n - p even vanish; when n is even, all remaining p are odd and binomial(n,p) is even (Lucas). When n is odd, only p=2 contributes, so a(n) == binomial(n,2) (mod 2), which is odd iff n == 3 (mod 4).
LINKS
Pablo Cadena-Urzúa, Table of n, a(n) for n = 0..1000.
FORMULA
a(n) = (1/2) * Sum_{p prime, p <= n} binomial(n,p) * (3^(n-p) - 1).
E.g.f.: ((exp(3*z) - exp(z))/2) * (Sum_{p prime} z^p/p!).
a(n) ~ 2^(2n-1)/log(n/4).
EXAMPLE
For n=4, contributions are p=2: binomial(4,2)*(3^2-1)=48; p=3: binomial(4,3)*(3^1-1)=8; total (48+8)/2=28.
MATHEMATICA
a[n_]:=Sum[Binomial[n, Prime[p]]*(3^(n-Prime[p])-1)/2, {p, PrimePi[n]}]; Array[a, 27, 0] (* James C. McMahon, Sep 04 2025 *)
PROG
(PARI) a(n) = {my(s=0); forprime(p=2, n, s+=binomial(n, p)*(3^(n-p)-1)); s/2};
(Python)
import sympy as sp
def a(n): return sum(sp.binomial(n, p)*(3**(n-p)-1) for p in sp.primerange(0, n+1))//2
CROSSREFS
KEYWORD
nonn
AUTHOR
Pablo Cadena-Urzúa, Aug 28 2025
STATUS
approved