2
$\begingroup$

Example: How many 7-digit binary strings have three 1's? Answer: $ { 7 \choose 3} = 35 $

definition of $ { n \choose k} $ : If n and k are integers, then $ { n \choose k} $ denotes the number of subsets that can be made by choosing k elements from an n-element set.

According to the above definition, $ { 7 \choose 3} = \frac{7!}{3!4!} = 35 $

My difficulty: in the example we're choosing 3 elements from from a 7-element set, however what is this 7-element set?

I thought about this because when we calculate 7! , it means we have some set of 7 elements, and in this example's case we have a binary string, which is composed of the set { 0 , 1 } , i.e. a 2-element set and not a 7-element set.

$\endgroup$
2
  • $\begingroup$ Isn't $\frac{7!}{3!4!} = 35$? $\endgroup$ – Ak. Jan 25 at 10:45
  • $\begingroup$ Yes, I edited calculation error.. $\endgroup$ – hazelnut_116 Jan 25 at 10:56
3
$\begingroup$

You can think of it this way: Your seven-element set is $\{1, 2, 3, 4, 5, 6, 7\}$, corresponding to the indices of the digits which form your string (i.e., $3$ corresponds to the third digit).

Now you choose three elements out of this set, corresponding to the spots of your string where a "one digit" should appear. (This is a binary decision, meaning that the other elements are "zero digits".)

$\endgroup$
3
$\begingroup$

The $7$ elements are the terms in the $7$-tuple that form the $7$-digit string.

Each of these elements is distinct.

The "choice" part of the exercise is: "Is this element a $1$ or a $0$?"

Hence this exercise is equivalent to the exercise of choosing $3$ elements from a $7$-element set.

It is "how many ways can I choose $3$ elements of this string of $7$ digits so that these $3$ elements are $1$ and all the others are $0$?"

And of course the answer is $\dbinom 7 3 = \dfrac {7!} {3!4!} = \dfrac {5040}{6 \times 24}$ which works out to be $35$.

$\endgroup$
2
  • $\begingroup$ But why the elements of the 7 tuple are distinct? each of them can have only 2 possible values ( 0 and 1 ) $\endgroup$ – hazelnut_116 Jan 25 at 11:02
  • $\begingroup$ @hazelnut_116 Because there are 7 of them. The "distinctness" is in their position. The first one, the second one, the third one, ..., the seventh one. $\endgroup$ – Prime Mover Jan 25 at 11:18
0
$\begingroup$

No.

$${ 7 \choose 3} = \frac{7!}{3!4!} = \frac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2}{(3 \cdot 2)(4 \cdot 3 \cdot 2)} = 7 \cdot 5 = 35.$$

$\endgroup$
1
  • $\begingroup$ I miscalculated, I edited the question. $\endgroup$ – hazelnut_116 Jan 25 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.