1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
My name is Ann [436]
3 years ago
9

Let abe a finite set and let a∈a. prove that the number of subsets of a that contain a1 equals the number of subsets of a that d

o not contain a1.
Mathematics
1 answer:
vladimir1956 [14]3 years ago
5 0
Here's a combinatorial proof. Suppose A has n elements.

For a subset to contain a, it must consist of at least one element. So if any given subset has k elements, where 1\le k\le n, then a is not one of the other k-1 elements. This means the number of subsets containing a is

\displaystyle\sum_{k=1}^n\binom11\binom{n-1}{k-1}

Put another way, we are choosing elements from A to form a subset of k elements. We want a to be in each subset, so we have n-1 other elements of A from which to choose. Then we sum over all the possible sizes of the desired subset.

On the other hand, if we want to build subsets not containing a, then we have n-1 total elements to choose from, and we can make subsets of size ranging from 0 to n-1, so the number of subsets not containing a is

\displaystyle\sum_{k=0}^{n-1}\binom10\binom{n-1}k

We have \dbinom10=\dbinom11=1, and in the second sum we can shift the index up by 1 to get

\displaystyle\sum_{k=1}^{n-1+1}\binom10\binom{n-1}{k-1}

which is the same as the first count.
You might be interested in
At a rat of 64 kilometers per hour, how far will a car travel in 7 1/2 hours?_______
Snowcat [4.5K]

We use the formula d = s*t where d is distance, s is speed and t is time.

d = 64km*7.5

d = 480km

Therefore, a car would tracel 480 km.

5 0
3 years ago
Read 2 more answers
A recipe for one full cake calls for one fourth cup of sugarIf three eighths of a cup of sugar is used, how many cakes were made
marin [14]

Answer:

1 1/2 cakes

Step-by-step explanation:

3/8 ÷ 1/4

3/8 * 4/1

12/8

3/2

1 1/2

5 0
2 years ago
Write an equation to represent the following statement.<br> The sum of j and 47 is 55<br> .
scZoUnD [109]

Answer:

j + 47 = 53

Step-by-step explanation:

3 0
3 years ago
Read 2 more answers
Two boats leave the same port, heading in opposite directions. One boat travels at 10 miles per hour and the other boat travels
Natalka [10]

Answer:

idk

Step-by-step explanation:

idk

8 0
3 years ago
A map has the scale 1/3inch = 8 miles. If city a and city b are 12 inches apart on my map then how far apart are the city’s in r
Feliz [49]
The equation would be
12 ÷ 1/3 =
12 x 3/1 =
12 x 3 =

36 miles
6 0
1 year ago
Other questions:
  • I really need help plzz
    11·1 answer
  • Factor:<br>4h^2 – 12h + 9 = 0​
    12·1 answer
  • 7(x+2)=2x-1 solve for the variable
    7·1 answer
  • Find the sum.<br> 19+(-19)
    15·1 answer
  • How to work on this? (x+1) (x+1) (x+1) what the answers will be?
    13·1 answer
  • What is the slope of the line with the points of (100,120) (50,95)
    7·1 answer
  • It took 12 kg of rope to fill box A about how many kg of rope woulf it take to fill box B <br>​
    5·1 answer
  • AXYZ is reflected across the line x = 3. What is the reflection image of X
    13·1 answer
  • Braden has m muffins. He splits them evenly among 4 boxes. Write an expression that shows how many muffins are in each box.
    12·2 answers
  • Izzy goes on 13 boat rides over the summer.
    14·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!