Question #4738

How many subsets does the set {a1,a2,...,an} of n elements have? How many subets are the containing the element a1? Prove your claim.

Expert's answer

First we need to formalize this& problem.

Let's consider sequence with n elements that consists with 0 and 1. Let

x={x1,x2,...xn}, xi є{0,1}, i=1,...n

If some element enters into some set we will designate it 1 in sequence& .

On each place can be 0 or 1 (two possibilities), we have n positions, then let's count all possible variants

<img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAGUAAAAmCAIAAABS0sJaAAACLklEQVRoge2ZPW7CMBhAfQEmLlBl6MjWmYG1YmZp9pygTBmqirFiQ1bXjoEbMJADZOmAIkUKUiSvEe5CJjoYBZMa489xSCP5jZDvh4djOzE6WiCgthvoGNYXDOsLhvUlgGTJ89NLStKx4+BgzX919kVpPnYchBBCKIxilbwaIfUxWPRaqp/9frVafc7nKUkxXvIhJ19FcZi/vueUHo/HdYBVWtEIqY/BopJUlOYzzwujOI5C8fjabb+TjJSJppOR6y/k9TRC6mOwqCRVqWmJMRNaIp6/Fr4L7UMjpD4Gi/KpmCZ2t44m00NRlJcJfDHZoHGuEVIfg0XVUwl8kSzxvBkv9SYaIfW5VnThu0iEZCSq9y/w9fXxVt7YimiE1MdgUfVUVV/rAAuHJcmSQb8v/IuEIZLr1YEW1QOU6sIXv3ySLPne7m7Ga4TUR14UdD9C+z/7iqOQz+4448pSKiymHsIGS9kcm2L51Wcd4H5/cPO+0OjTYCpU9qo+O+qFsOb47d/Cd/kWVfafGn2aTWWfH2FYXzBOvijNN5uo3Vb0iDYb7flLg/P4+vus9P+hNK+8P2iasy+SJcPH4f23ndqwt1R3/o8v5i/+fZAR+P0B20/w3/Z6D5VPQFSehFvwZZzyOTaOwlZ+nnHusT628qqnIex+Aob1BcP6gmF9wWjcl+Qsr4s07ktyltdFGvclOcvrIo37kpzldZHGfUnO8rqIXR9hWF8wrC8Y1hcM6wvGL01Ik8UmFu+hAAAAAElFTkSuQmCC" alt="">

Then the set {a1,a2,...an} of n elements have& 2^n subsets.

About& a1 . Let's fix the first position in sequence& . We have x={1,x2,...xn}

Let's calculate all possible variants

<img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAGoAAAAmCAIAAACj2ZnXAAACS0lEQVRoge2ZPW6DMBSAfYfcgKFjt84dslaZs4Q9J2gmhqrKWLEhq2tGGqkHYAgHYMlQISElEhIrwl3CRAerlgvEYJ5jiuRvjJL3Xj6e/zCqDADQ2AVMG6MPhNHXl7K8bJZzy1rkhLAPjT4JyvLiPr8afe1kafL0sDplp4VlYT9ofkGkjzbnfLm5lKU4DSH5wrIQQgihMIpVVa8t6bVQ30Wx3+/fXfeUnTD+aP7wqj4WsVMfHyLwsR6DCpMKQhGSb9frMIrjKHR3n5vlHP1CtXQM3sDHnfrOX8ckzVgpm+Xcdrxh/6Q/CpMKQsVRSMfsB8a8I4YCfTU8x9ag73ZJ+VDUGh2IrR48x64NUJA++vS0TX/Kk8JDgfRlabJeb6W6Fc61pLQ1mgj6FF4/SN/u7YXNI9pQmBQeqkNflib3s1nrAwx83Gx7wff7I5t0GEpCDew+tkhVVZWlyfHrDKyjD+KkUoNXVf1/9HmO3UdfHIV8fbVjYA3aSqzW5uY88PFsdt85iKSSagtV3zYjhMR/hm41e87NrFb+DOQ5Nl9xn22wbFI9oSpz5gVi9IGQ00dIfjhENypFiuhwGDxhKUS6+66dB3VCSN76RkQ/0vqyNHm8e9S/W+YLeHpYjf4IKUPmPn6ZloJf0+mGZkAQ2ZcaN0Xr0sGO6HEU/isLgxlh5R3lHdeNMBsXEEYfiJH1tV6eTojxu695gTAhdOgT358afR2I70+Nvg7E96fFd2H0iRDfn5ru60B8f9q8PJ0Q46+8k8boA2H0gTD6QPwA0YTMCyGdJocAAAAASUVORK5CYII=" alt="">

The first position is fixed.

2^(n-1) subsets contain the element a1

Let's consider sequence with n elements that consists with 0 and 1. Let

x={x1,x2,...xn}, xi є{0,1}, i=1,...n

If some element enters into some set we will designate it 1 in sequence& .

On each place can be 0 or 1 (two possibilities), we have n positions, then let's count all possible variants

<img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAGUAAAAmCAIAAABS0sJaAAACLklEQVRoge2ZPW7CMBhAfQEmLlBl6MjWmYG1YmZp9pygTBmqirFiQ1bXjoEbMJADZOmAIkUKUiSvEe5CJjoYBZMa489xSCP5jZDvh4djOzE6WiCgthvoGNYXDOsLhvUlgGTJ89NLStKx4+BgzX919kVpPnYchBBCKIxilbwaIfUxWPRaqp/9frVafc7nKUkxXvIhJ19FcZi/vueUHo/HdYBVWtEIqY/BopJUlOYzzwujOI5C8fjabb+TjJSJppOR6y/k9TRC6mOwqCRVqWmJMRNaIp6/Fr4L7UMjpD4Gi/KpmCZ2t44m00NRlJcJfDHZoHGuEVIfg0XVUwl8kSzxvBkv9SYaIfW5VnThu0iEZCSq9y/w9fXxVt7YimiE1MdgUfVUVV/rAAuHJcmSQb8v/IuEIZLr1YEW1QOU6sIXv3ySLPne7m7Ga4TUR14UdD9C+z/7iqOQz+4448pSKiymHsIGS9kcm2L51Wcd4H5/cPO+0OjTYCpU9qo+O+qFsOb47d/Cd/kWVfafGn2aTWWfH2FYXzBOvijNN5uo3Vb0iDYb7flLg/P4+vus9P+hNK+8P2iasy+SJcPH4f23ndqwt1R3/o8v5i/+fZAR+P0B20/w3/Z6D5VPQFSehFvwZZzyOTaOwlZ+nnHusT628qqnIex+Aob1BcP6gmF9wWjcl+Qsr4s07ktyltdFGvclOcvrIo37kpzldZHGfUnO8rqIXR9hWF8wrC8Y1hcM6wvGL01Ik8UmFu+hAAAAAElFTkSuQmCC" alt="">

Then the set {a1,a2,...an} of n elements have& 2^n subsets.

About& a1 . Let's fix the first position in sequence& . We have x={1,x2,...xn}

Let's calculate all possible variants

<img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAGoAAAAmCAIAAACj2ZnXAAACS0lEQVRoge2ZPW6DMBSAfYfcgKFjt84dslaZs4Q9J2gmhqrKWLEhq2tGGqkHYAgHYMlQISElEhIrwl3CRAerlgvEYJ5jiuRvjJL3Xj6e/zCqDADQ2AVMG6MPhNHXl7K8bJZzy1rkhLAPjT4JyvLiPr8afe1kafL0sDplp4VlYT9ofkGkjzbnfLm5lKU4DSH5wrIQQgihMIpVVa8t6bVQ30Wx3+/fXfeUnTD+aP7wqj4WsVMfHyLwsR6DCpMKQhGSb9frMIrjKHR3n5vlHP1CtXQM3sDHnfrOX8ckzVgpm+Xcdrxh/6Q/CpMKQsVRSMfsB8a8I4YCfTU8x9ag73ZJ+VDUGh2IrR48x64NUJA++vS0TX/Kk8JDgfRlabJeb6W6Fc61pLQ1mgj6FF4/SN/u7YXNI9pQmBQeqkNflib3s1nrAwx83Gx7wff7I5t0GEpCDew+tkhVVZWlyfHrDKyjD+KkUoNXVf1/9HmO3UdfHIV8fbVjYA3aSqzW5uY88PFsdt85iKSSagtV3zYjhMR/hm41e87NrFb+DOQ5Nl9xn22wbFI9oSpz5gVi9IGQ00dIfjhENypFiuhwGDxhKUS6+66dB3VCSN76RkQ/0vqyNHm8e9S/W+YLeHpYjf4IKUPmPn6ZloJf0+mGZkAQ2ZcaN0Xr0sGO6HEU/isLgxlh5R3lHdeNMBsXEEYfiJH1tV6eTojxu695gTAhdOgT358afR2I70+Nvg7E96fFd2H0iRDfn5ru60B8f9q8PJ0Q46+8k8boA2H0gTD6QPwA0YTMCyGdJocAAAAASUVORK5CYII=" alt="">

The first position is fixed.

2^(n-1) subsets contain the element a1

## Comments

## Leave a comment