Problem
COM-B2-M03-P001 Subsets as Strings
#1
★★☆☆☆ Level 2 of 5
Construct a bijection between subsets of \(\{1,\ldots,n\}\) and binary strings of length \(n\). Conclude that there are \(2^n\) subsets.
Write \(1\) if the element is chosen and \(0\) otherwise.
To a subset \(A\), assign the string \(a_1\ldots a_n\), where \(a_i=1\) if \(i\in A\), and \(a_i=0\) otherwise. From such a string we recover \(A=\{i:a_i=1\}\). Hence this is a bijection. There are \(2^n\) binary strings of length \(n\).
A starter problem on writing the inverse map explicitly.