+0

counting

0
92
3

We say that a set of integers is sparse if any two elements in the set differ by at least 3. Find the number of sparse subsets of 1, 2, 3, ... , 12, 13, 14 (Note that the empty set is also sparse.)

May 15, 2021

#1
0

There are 56 such sets.

May 15, 2021
#2
+22084
+1

I do not know what the answer is, but, in listing some sets, I get more than 56 sets when counting only those that include the number 1.

May 15, 2021
#3
+113790
+2

We say that a set of integers is sparse if any two elements in the set differ by at least 3. Find the number of sparse subsets of 1, 2, 3, ... , 12, 13, 14 (Note that the empty set is also sparse.)

I get 51 that are NOT sparse

The number of subsets altogther is

1+14+14C2+14C3+14C4+14C5+14C6+14C7+14C8+14C9+14C10+14C11+14C12+14C13+14C14

=2+28+2(14C2+14C3+14C4+14C5+14C6)+14C7

=30+2(14C2+14C3+14C4+14C5+14C6)+14C7

=30+2(91+364+1001+2002+3003)+3432

=3462+2(6461)

=16384

So the number of subsets that are sparse is  16384-51 = 16333

May 16, 2021