It seems easy to grasp that number of ways of choosing $n$ items from $n$ items is 1. But I am unable to understand why is it 1 for choosing 0 items.
$\begingroup$
$\endgroup$
14
-
47$\begingroup$ Is it possible to choose none of the $n$ items? Is there more than one way to do that? $\endgroup$– bofCommented Oct 22, 2018 at 6:51
-
19$\begingroup$ The only choice you can make is $\lbrace \rbrace$ $\endgroup$– P. QuintonCommented Oct 22, 2018 at 6:51
-
12$\begingroup$ What do you think it should be? $\endgroup$– Martin RCommented Oct 22, 2018 at 6:52
-
8$\begingroup$ The number of bitstrings of length $n$ containing $n$ ones is the same as the number containing $n$ zeros. $\endgroup$– bofCommented Oct 22, 2018 at 6:53
-
5$\begingroup$ Actually, choosing $0$ items is the same as choosing $n$ and then taking those which have not been chosen instead. (Or generally, the number of ways to choose $k$ is the same as to choose $n-k$.) $\endgroup$– Carsten SCommented Oct 22, 2018 at 11:34
|
Show 9 more comments
14 Answers
$\begingroup$
$\endgroup$
7
When you phrase it in plain English, the answer isn't necessarily totally clear. It might seem reasonable to argue that there are $0$ ways of choosing $0$ things from $n$, since choosing $0$ things isn't really a choice. However, when mathematicians talk about "the number of ways to choose $0$ from $n$," we mean something a bit more specific.
A few ways of describing what we mean:
- The number of subsets of an $n$-element set with $0$ elements (and we always assume the empty set counts)
- The number of functions from a $0$-element set to an $n$-element set, up to permutations of the domain (there's exactly one function from the empty set to any set).
- The coefficient of $x^0y^n$ in the expansion of the binomial $(x+y)^n$.
All of these agree that there is one way to choose $0$ out of $n$ things, and all of these perspectives are mathematically very useful. Thus the perspective that there is a way to choose $0$ out of $n$ things is universal in mathematics.
This wasn't always so obvious to everyone: for instance, I have heard of an early 20th century mathematician who insisted in his books that all intersections be nonempty to be defined. It seems to me that this would be consistent with refusing to accept the empty set as a subset, and with saying there are $0$ ways to choose $0$ things from $n$. But this would make for lots of inconvenient circumlocutions, so we've settled pretty firmly on the other solution.
answered Oct 22, 2018 at 7:50
-
15$\begingroup$ +1 for the last sentence. There are many examples in math where one could make a reasonable argument for another definition/convention than what is standard, but the standard preserves nice properties that would have to be modified. $\endgroup$ Commented Oct 22, 2018 at 20:40
-
20$\begingroup$ "It might seem [that] choosing 0 things isn't really a choice." It is if I offer you a plate of cookies and say "Take as many as you want." $\endgroup$ Commented Oct 23, 2018 at 11:57
-
3$\begingroup$ @DavidRicherby An interesting example, because many who make such an offer would not accept choosing to take none! $\endgroup$– JiKCommented Oct 23, 2018 at 14:58
-
$\begingroup$ Being an element of the intersection of a collection of sets means being element of every member of the collection. Which would be vacuously true for any candidate element in the case of an empty intersection. So the value of an empty intersection could logically only be a set with everything as element; but we know that such a set cannot exists. Therefore an empty intersection (contrary to an empty union) is not defined; your anonymous mathematician was right. $\endgroup$ Commented Oct 23, 2018 at 16:06
-
$\begingroup$ @Marc I mean an intersection which is empty, not which is indexed over an empty family. $\endgroup$ Commented Oct 23, 2018 at 21:01
$\begingroup$
$\endgroup$
5
Perhaps a little duality argument can help to provide some intuition.
Given a bag of $n$ balls, consider these two tasks:
- choose $k$ balls inside the bag, and remove them from the bag
- choose $n-k$ balls inside the bag, and remove all the others from the bag
Intuition suggests that these tasks are essentially the same: choosing which $k$ balls we remove corresponds to choosing which $n-k$ balls we keep in the bag.
Indeed, there are as many ways to choose $k$ balls (to remove) as there are to choose $n-k$ balls (to keep).
In particular, to determine how many ways we have to choose (and remove) $0$ balls, we can equivalently count how many ways we have to choose (and keep) $n-0=n$ balls. In your own question, you agree on there being only one way to choose $n$ balls out of $n$. Hence, "one way to choose what to keep" can be restated as "one way to choose what to remove".
-
3$\begingroup$ I like this intuitive argument. Selecting one from n is equivalent to selecting all but one from n. $\endgroup$ Commented Oct 22, 2018 at 15:02
-
4$\begingroup$ This is especially useful when explaining to a student why
nCr = nCn-r. $\endgroup$– nurdyguyCommented Oct 23, 2018 at 17:52 -
$\begingroup$ Nice way to look at it. There are so many good answers to this question. $\endgroup$– subbaCommented Oct 24, 2018 at 11:46
-
$\begingroup$ A very helpful explanation. Typo alert: "there are so many ways ... as" should be "there are as many ways ... as". I tried to edit it but the change was too few characters, and I didn't want to make dummy changes. $\endgroup$– LarsHCommented Oct 25, 2018 at 11:55
-
$\begingroup$
$\endgroup$
1
There are several good answers already. I'll try an intuitive explanation. If there are four possible items to buy and several people find none of them attractive enough they will each leave the store with the same contents in their shopping bag. You can't tell the bags apart (assuming they're not personalized ...). There's only one way to buy nothing.
answered Oct 22, 2018 at 15:19
-
$\begingroup$ I was thinking about writing a human and intuitive explanation, but I found this one to be better than I could ever have given. $\endgroup$ Commented Oct 25, 2018 at 13:58
$\begingroup$
$\endgroup$
6
Well, since it's possible to choose 0 items from $n$, there must be at least one way to do it. And every way to do it is the same (I admit, this part is harder to formalize), so there is at most one way.
For comparison, there is no way to choose $n+1$ items out of $n$, and equivalently ${n \choose n+1} = 0$.
answered Oct 22, 2018 at 13:12
-
$\begingroup$ Alice has a box containing n distinct items from which she is to choose m for inclusion in Bob's (initially empty) box. Carol has a pad of paper, and is instructed to write down a prediction of what Alice will put in Bob's box. She's allowed to write as many predictions as she wants on separate pages. For any given m and n, Dave must construct a table showing the smallest number of pages Carol can use to cover every possible way Alice can set up Bob's box. Dave knows that where _m_=0, Carol can simply turn in a single blank page (or the words "Bob's box is empty". $\endgroup$ Commented Oct 22, 2018 at 20:53
-
$\begingroup$ Strictly speaking, I don't think the binomial coefficient is defined for $k > n$. $\endgroup$ Commented Oct 23, 2018 at 7:46
-
3$\begingroup$ @HelloGoodbye If we really want to, we can define $\binom xk$ for any $x$ ($x$ bigger than $k$ or even irrational or even an element of some weird algebraic object that's not the real numbers) provided $k$ is a natural number. $\endgroup$ Commented Oct 24, 2018 at 2:30
-
2$\begingroup$ @HelloGoodbye One can define the binomial coefficient for all real $k$ and $n$ using the Gamma function. For integer $n$ and $k$ with $k > n$, the coefficient is indeed zero. $\endgroup$ Commented Oct 24, 2018 at 20:47
-
$\begingroup$ @MishaLavrov Absolutely, you are right in that. $\endgroup$ Commented Oct 25, 2018 at 16:05
$\begingroup$
$\endgroup$
Your question is equivalent to asking "how many subsets of a set of size of $n$ elements have $0$ elements in it" and we only have $\emptyset$.
$\begingroup$
$\endgroup$
2
You have written in your question that you understand that "number of ways of choosing n items from n items is 1". What do you mean by choosing? Does it mean selecting or does it stands for rejecting ? Or is it just a matter of language and requirement? Basically it's the latter. And that being said,
number of ways of selecting n items =number of ways of rejecting n items
number of ways of selecting n-1 items =number of ways of rejecting n-1 items
.
.
.
number of ways of selecting 0 items =number of ways of rejecting 0 items
Now,
Logically,
number of ways of rejecting n items =number of ways of selecting 0 items
number of ways of rejecting n-1 items =number of ways of selecting 1 items
.
.
.
number of ways of rejecting 0 items =number of ways of selecting n items
Now ,
number of ways of selecting n items =number of ways of rejecting n items =1
=>
number of ways of rejecting n items =number of ways of selecting 0 items =1
Hence Proved!
-
$\begingroup$ Can you please quote the reason for downvoting? That would really help. $\endgroup$ Commented Oct 22, 2018 at 16:54
-
$\begingroup$ This answer is essentially saying the same thing as the answer by @chi and that answer was well received. I up voted this one also. Down-voters, please compare to chi's answer for a different way to look at what this answer is saying. $\endgroup$– AaronCommented Oct 22, 2018 at 18:29
$\begingroup$
$\endgroup$
You can choose any k items from a bag of n item. And there are different number of ways to choose k items. choosing 0 items from the bag means insert your hand inside the bag and come up with empty hand, just to entertain the kid. You can still do that. So there is no 0 way of doing it. There is still 1 way of doing this.
$\begingroup$
$\endgroup$
The other answers are fine, but for a geometric twist:
Pascal's triangle would be a lot less elegant without this definition:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
(And so on.) Even if there wasn't any other compelling reason for defining $n \choose k$ in such a way that ${n\choose 0} = 0$, the symmetry of the triangle itself could lead you there. It would be odd if the last 4 entries of the bottom row were ${4\choose 1}, \ldots, {4 \choose 4}$ but the first entry wasn't $4 \choose 0$.
answered Oct 23, 2018 at 15:13
$\begingroup$
$\endgroup$
1
First of all, this requires us to be precise about what we mean by a "way". A "way" in this context is not meant to include things like, for example, whether you take items using one or two hands, or you reach into the box using kitchen tongs to remove balls, whether you perform a dance such as the Fandango, Twerking, or now the Yeet, before you remove balls, or any of a number of such acts. If that were allowed, then the number of "ways" would be very hard to define, and certainly much greater than $\binom{n}{k}$.
Rather what defines a "way" is solely which balls were selected - given that, as this problem requires, the balls all look different and so are individually identifiable as different from each other, and thus we are able to describe such a thing. That is, it is simply what you'd write down on a piece of paper regarding which balls you pulled out, like a shopping list, and also like a shopping list, noting that the order in which you wrote them down is another unimportant detail when it comes to which ones you will actually have.
So what you're asking is, "is there a selection of balls which contains no balls?" Sure. Don't withdraw any. Leave the notepaper on which the selection is to be recorded, blank. Or write "I didn't choose any" - the difference between those is the same as all the other ones I mentioned above. Those are all selections that contain no balls. They do not enumerate balls.
But of course there is a counterargument, and perhaps this is the source of your difficulty. The counterargument you could make here is that a selection "with no balls on it" or a list "with no items" written on it is not a selection, or not a list. Or you could argue that withdrawing no items, or doing nothing, is not actually an action. With regard to the first one, I think the intuition behind this is probably why most cultures did not invent the concept of zero as a number. Conversely, the fact we accept zero as a number - which makes it possible to talk about this at all - means we are by definition talking about cases where we have nothing in hand, or where things are empty, and thus an empty list - here, an empty set - should be a conceivable possibility if you are to admit that the number "0" used in the question is even meaningful, which is needed for the question to make sense in the first place. Thus we will admit a blank sheet of paper as a list with no items.
Moreover, many would say that the idea that "doing nothing" or choosing "nothing" doesn't count as doing something or as making a choice, is a grievous mistake, with consequences that reach far beyond mathematics. You may have heard the phrase "all it takes for evil to triumph is for good humans to do nothing".
You would thus indeed be very wise to heed that
$$\binom{n}{0} = 1$$
answered Oct 25, 2018 at 6:24
-
$\begingroup$ ▲ for tackling a misunderstanding the questioner may have. The first paragraph seems a bit long to me, but perhaps it helps them! $\endgroup$– PJTraillCommented Oct 25, 2018 at 13:05
$\begingroup$
$\endgroup$
3
Imaginate as an option:
1) Pick $0$ elements
2) Pick $1$ element
3) Pick $2$ elements
...
n+1) Pick $n$ elements
(EDIT) Life examples:
I. Voting: You can choose between Candidate A, Candidate B or no one by not voting.
Note that choosing nobody is a choose as well (not on paper of course).
II. Shopping: You want to buy a specific type of bread (like: gluten free)- so if there is- you pick or if there is no- 'that's your default vallue'.
Your set here is $\text{{0,1}}$ with the cardinality of $2$ results.
III. A school mate in 2005:
"As you see (Chris) I have ten fingers: 1,2,3...10.
Let's count now from zero to be sure: 0,1,2...9"
This puzzle is not the best sample (since he could start to counter by minus one for example) but the point was: Finger #$0$ is a finger as well .
answered Oct 22, 2018 at 6:54
-
3
-
$\begingroup$ @DaG Yes- tommorrow I made an edit ( hopefully without english grammar mistakes). $\endgroup$ Commented Oct 22, 2018 at 17:40
-
$\begingroup$ @DaG I not unclude terms like the Empty Set to not complicate my primary answer $\endgroup$ Commented Oct 23, 2018 at 6:23
$\begingroup$
$\endgroup$
Think of it like this: Choose the items that you don't want to choose. By choosing $k$ items out of $n$ not to choose, you will effectively have chosen $n - k$ out of the $n$ items, and it becomes obvious that there are equally many ways of choosing $k$ items out of $n$ as there are ways of choosing $n-k$ items out of $n$.
So, there are equally many ways of choosing 0 items out of $n$ as there are ways of choosing $n$ items out of $n$.
$\begingroup$
$\endgroup$
How to choose 0 items: Choose n items, then pick the ones that remain. There is one way to choose n items, therefore there is only one way to pick the ones that remain.
$\begingroup$
$\endgroup$
Of course by the formula
$\frac{n!}{r! (n-r)!}$ clearly we get that here
Taking $n=$(any random value) I keep it as n where $n \in \mathbb N$
$r=0$
Putting these values we get,
$\frac{n!}{0!(n-0)!}$
$\Rightarrow \frac {n!}{n!.0!}$
$\Rightarrow \frac {1}{0!}$
$\Rightarrow \frac {1}{1}$
$\Rightarrow 1$
Now for the explanation
Suppose you have 5 apples and you want to select none of them so you don't have any choice other than 1 that you will select none
This constitutes your single choice that is the single choice.
$\begingroup$
$\endgroup$
Yet another way of looking at it: The number of ways we can choose k elements from n is equal to the number of sets in the power set of {1, .., n} consisting of exactly k elements. The power set P(S) of a set S is the set of all subsets of S, including S itself and the empty set.
Example:
Suppose we're considering 3 choose 2. The appropriate power set is {$\phi$, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}. The sets that contain two elements are {1,2}, {1,3} and {2,3}, so 3 choose 2 is 3.
Whereas the number of sets containing 0 elements is always 1 (the empty set).
