• Introduction
• Program
• Examples

Selecting Subsets of Power Sets with Desired Properties

by Prof. Bill Bauldry,
 Appalachian State University ,
 BauldryWC@appstate.edu

Introduction

Let A = {1, 2, 3,..., 10}. We will use Maple to generate the set B of all subsets of A of size 2 containing at least one odd integer.  More generally, we can do this for A = {1, 2, 3,..., n}for any n, generating the set B of all subsets of A of size k containing at least one integer that has any desired property (e.g. prime, power of two, etc.)

Program

>	restart; with(combinat);

Warning, the protected name Chi has been redefined and unprotected

We first generate all order-2 subsets of the power set {1, 2, 3,..., 10}.  (For large n, using the choose( )  function is more efficient than generating the entire power set of A and then selecting the order-2 subsets.)

>	k_sets := choose( [seq(i, i=1..10 )], 2 );

Next, we write a little function that takes a subset x  and returns true  if any element of x  is odd.

>	HasAnOdd := x -> convert( map(type, x, odd), `or`):

>	HasAnOdd( [ 1, 6, 8 ] );

>	HasAnOdd( [ 2, 6, 8, 10 ] );

Now we can generate B  by filtering the subsets of size 2 using our function HasAnOdd .  

>	B :=  select( HasAnOdd, k_sets );

The size of B

>

nops(B);

Here is a procedure that does the above for any size power set (n), subset size (k) and integer property (prop)

>	B_size := proc(n, k, prop)   local k_sets, HasProperty, B;   k_sets := combinat[choose]( [seq(i, i=1..n )], k );   HasProperty := x -> convert( map(type, x, prop), `or`):   B :=  select( HasProperty, k_sets );   [nops(B), B]; end proc:

Examples

n = 10, k=2, odd numbers

>	B_size( 10, 2, odd );

n = 10, k = 3, even numbers

>	B_size( 10, 3, even );

n = 10, k=2, prime numbers

>	B_size( 10, 2, prime );

Disclaimer:  While every effort has been made to validate the solutions in this worksheet, Waterloo Maple Inc. and the contributors are not responsible for any errors contained and are not liable for any damages resulting from the use of this material.