#include <stdio.h>
#include <math.h>
//#include "cs49/Recursion.h"


#define BIT(i,x)   (((1<<(i)) & (x)) >> i)
#define SETBIT(i,x)  ((x) |= (1 << (i)))
#define CLEARBIT(i,x)  ((x) &= ~(1 << (i)))


#define UNION(x,y) ((x) | (y))
// z belongs to the union of x,y  if z belongs to
// one of x and y (or both)
// the z-th bit of x | y is set if and only if
// the z-th bit of x is set or the z-th bit of y is set

#define INTERSECTION(x,y)  ((x) & (y))

#define ELEMENTOF(x,y)   ((y) & (1U<<x))
// careful.  If using with longs you need
// #define ELEMENTOF(x,y)   ((y) & (1UL<<x))
// and using with long longs you need
//#define ELEMENTOF(x,y)   ((y) & (1ULL<<x))

#define N 32
static long long binomial[N][N];

unsigned long long slowchoose(int n, int m)
{  if(m==0 || m==n) return 1;
   return slowchoose(n-1,m-1)+ slowchoose(n-1,m);
}

unsigned long long choose(int n, int m)
// binomial coefficient, number of ways of choosing n things out of m things
// assumes 0 <= n <= m
{ unsigned long long ans;
  if(binomial[n][m])
	  return binomial[n][m];
  if(n==0 || n==m)
      { binomial[n][m] = 1;
        return 1;
      }
  ans = choose(n-1,m-1) + choose(n,m-1);
  binomial[n][m] = ans;
  if(ans >> 60)
     printf("Warning:  binomial coefficient too big\n");
  return ans;
}





int nElements(int p, int m)
// count the bits of p among the 0th to m-1st bit that are set
// and return that number
{  int k, ans = 0;
   for(k=0;k<m;k++)
	  if( (1U << k) & p) ++ans;
   return ans;
}


// Pick two n-element subsets out of
// {0,1,2...,m-1}.   What are the chances
// they are disjoint?

int CountDisjoint(int n, int m)
// return the number of disjoint pairs of n-element
// subsets of S = {0,1,..,m-1}.
{ int nSets = 1U << m;  // 2 to the power m
  int p,q;
  int count = 0;
  for(p=0;p<nSets;p++)
  { if(nElements(p,m) != n) continue;
	for(q=p;q<nSets;q++)
    { if(nElements(q,m) != n) continue;
	  if(INTERSECTION(p,q) == 0)
         { if(p==q) ++count;
	       else count += 2;
         }
	}
  }
  return count;
}


double TheChances(int n, int m)
// return the probability that two n-element subsets
// of {0,1,...,m-1} are disjoint.
{ unsigned long long nSubsets = choose(n,m);
  int nDisjoint = CountDisjoint(n,m);
  double ans = nDisjoint/(double) (nSubsets *nSubsets);
             // not (double)  (nDisjoint/(nSubsets* nSubsets);
             // OK:  (double) nDisjoint / (nSubsets*nSubsets);

  return ans;
}


int main(int argc, char *argv[])
{ int n,m=5;
  printf("\n");
  for(n=0;n<32;n++)
      printf("%d",BIT(n,m));
  CLEARBIT(2,m);
  printf("\n");
  for(n=0;n<32;n++)
        printf("%d",BIT(n,m));
  SETBIT(1,m);
  printf("\n");
    for(n=0;n<32;n++)
          printf("%d",BIT(n,m));

  printf("\nn    m     ans\n");
  for(m=3;m<6;m++)
  for(n=1;n<4;n++)
	  printf("\n%d  %d   %lf",n,m,TheChances(n,m));
}