cp's OEIS Frontend

A255597 Upper bound on the number of different Euler diagrams for n classes.

%I A255597 #40 Mar 01 2025 08:39:42
%S A255597 1,1,3,29,1667,3254781,10650037396483,113423713055347294030815229,
%T A255597 12864938683278671740537145090971257103576706009186307
%N A255597 Upper bound on the number of different Euler diagrams for n classes.
%C A255597 Obtained via an iterative method. Each new class added to an existing diagram must create at least a new zone, and at most a number of new zones equal to the existing zones.
%H A255597 Mathematics Stack Exchange, <a href="http://math.stackexchange.com/questions/863844/how-many-euler-diagrams-with-n-sets-exist">How many Euler diagrams with n sets exist?</a>.
%H A255597 Wikipedia, <a href="https://en.wikipedia.org/wiki/Euler_diagram">Euler diagram</a>.
%F A255597 a(n) = Sum_{k>=1} e(n,k), where k is the number of zones, and the elements e(n,k) are defined recursively as: e(0,1) = 1; e(n,k) = Sum_{c=1..k-1} binomial(c,k-c)*e(n-1,c).
%F A255597 a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*A007018(k). - _Jason Yuen_, Mar 01 2025
%e A255597 For n=3 (3 different classes) there are 29 possible Euler diagrams that do not reduce to smaller cases. Of these 11 are in fact repetitions and need to be eliminated to perfect the upper bound.
%o A255597 (C)
%o A255597 #include <stdio.h>
%o A255597 #include <stdlib.h>
%o A255597 #include <math.h>
%o A255597 #define MAXCLU 7
%o A255597 #define MAXZONE 256
%o A255597 long long combi(int n, int k){
%o A255597     if (n<k) return 0;
%o A255597     long long ans=1;
%o A255597     k=k>n-k?n-k:k;
%o A255597     int j=1;
%o A255597     for(;j<=k;j++,n--){
%o A255597         if(n%j==0){
%o A255597             ans*=n/j;
%o A255597         }else if(ans%j==0){
%o A255597             ans=ans/j*n;
%o A255597         }
%o A255597         else{
%o A255597             ans=(ans*n)/j;
%o A255597         }
%o A255597     }
%o A255597     return ans;
%o A255597 }
%o A255597 int main(){
%o A255597     long long  a[MAXCLU][MAXZONE];
%o A255597     long long sum[MAXCLU];
%o A255597     int j,k,i;
%o A255597     for (j=0;j<MAXCLU;j++){
%o A255597         sum[j]=0;
%o A255597         for (k=1;k<MAXZONE;k++) a[j][k]=0;
%o A255597     }
%o A255597     a[0][1] = 1;
%o A255597     for(j=1;j<MAXCLU;j++)
%o A255597         for (k=1;k<(exp2(j)+1);k++)
%o A255597             for (i=1;i<k;i++)
%o A255597                 a[j][k] = a[j][k] + a[j-1][i]*combi(i,k-i);
%o A255597     for (j=0;j<MAXCLU;j++)
%o A255597         for (k=1;k<exp2(j)+1;k++)
%o A255597             sum[j]= sum[j] + a[j][k];
%o A255597     for (k=0;k<=exp2(MAXCLU-1);k++){
%o A255597         for (j=0;j<MAXCLU;j++){
%o A255597             if (j<5){
%o A255597                 if (k==0) printf("%5lld",sum[j]);
%o A255597                 else printf("%5lld",a[j][k]);
%o A255597             }
%o A255597             else{
%o A255597                 if (k==0) printf("%15lld",sum[j]);
%o A255597                 else printf("%15lld",a[j][k]);
%o A255597             }
%o A255597         }
%o A255597         printf("\n");
%o A255597         if (k==0) printf("\n");
%o A255597     }
%o A255597 }
%Y A255597 This sequence is linked to A007018 by the binomial transform: A007018(n) = Sum_{k=0..n} C(n,k)*a(k).
%K A255597 nonn
%O A255597 0,3
%A A255597 _Maurizio De Leo_, Feb 27 2015
%E A255597 More terms from _Jason Yuen_, Mar 01 2025