# Independent subsets of a finite set

(web version) 

## Independent nontrivial subsets

pairs_independent_nontrivial_subsets(n) := 
block([a, b, d, s : 0 ], 
  for a:1 thru n-1 do     
    for d:1 thru a do     
        ( b : n*d / a, 
          if integerp(b) and b<n 
              then 
                s : s + 
                     binomial(n,a) * 
                       binomial(a,d) * 
                         binomial(n-a,b-d) ) , 
    s)  $

pairs_independent_nontrivial_subsets(4);

L30 : makelist(i, i, 0, 30);

L_nontrivial_30  :  map(pairs_independent_nontrivial_subsets, L30);

a(n) := 
sum(
    sum(
          (b : n*d / a, 
          if integerp(b) and b<n then   
              binomial(n,a) * 
                binomial(a,d) *
                  binomial(n-a,b-d) else 0), 
    d,1,a), 
a,1,n-1) $ 

a(6);

L_a_30 : map(a, L30);

is(L_a_30 = L_nontrivial_30);

is(map(pairs_independent_nontrivial_subsets, L30) = map(a,L30) );

## Independent proper subsets

pairs_independent_proper_subsets(n) := 
   if is(n=0) then 0 else a(n) + 2*(2^n -1)  - 1 $ 

L_proper_30  :  map(pairs_independent_proper_subsets, L30);

OEIS_A158345  :  [ 1, 5, 13, 53, 61, 845, 253, 7509, 16141, 128045, 
    4093, 1785965, 16381, 23576285, 55921333, 274696789, 
    262141, 5338300157, 1048573, 63028146573, 117924207421, 
    995274180125, 16777213, 15265519672173, 14283159085861 ];

rest(rest(L_proper_30), -5) ;

is( rest(rest(L_proper_30), -5)  =  OEIS_A158345);

## All independent subsets

pairs_independent_subsets(n) := 
  if is(n=0)  then 1 else a(n) + 4*(2^n -1) $

pairs_independent_subsets(6); 

L_independent_30  :  map(pairs_independent_subsets, L30);

OEIS_A121312  :  [ 1, 4, 12, 28, 84, 124, 972, 508, 8020, 17164, 
    130092, 8188, 1794156, 32764, 23609052, 55986868, 
    274827860, 524284, 5338824444, 2097148, 63030243724, 
    117928401724, 995282568732, 33554428, 15265553226604, 
    14283226194724, 216345187553052 ];

is(rest(L_independent_30, -4) = OEIS_A121312);

transpose(matrix(L30,L_independent_30, L_proper_30, L_nontrivial_30) );