6
$\begingroup$

How many six-digit positive integers can you write, if each number must have strictly increasing digits from left to right?

How is it allowed to use:

$$ \binom{9}{3}$$

Because this says out of $9$ numbers choose $c$ the order does NOT matter.

But CLEARLY as the question indicates, the order does matter! We have to pick increasing numbers?

$\endgroup$
0
12
$\begingroup$

Once you pick six different digits, there is only one way to arrange them so that the digits are increasing. I would view the answer as $9\choose 6$, but of course this is equal to $9\choose 3$.

$\endgroup$
8
  • $\begingroup$ How only one way? $6, 5, 4...$ or $5, 3, 6..$? $\endgroup$
    – Lebes
    Feb 10 '15 at 13:21
  • 1
    $\begingroup$ @Lebes: But you're required to select the strictly increasing order of your digits. So if for instance you pick the digits $\{3,7,8,2,6,1,4\}$, the only permissible $6$ digit number is $1234678$. $\endgroup$
    – paw88789
    Feb 10 '15 at 13:24
  • $\begingroup$ yes, but $\binom{9}{6}$ means, from 9 choose $6$ and order doesnt matter? $\endgroup$
    – Lebes
    Feb 10 '15 at 13:27
  • 1
    $\begingroup$ @Lebos: Think of this as a two-stage process: Stage 1: Choose six distinct digits from $9$ (can be done in $9\choose 6$ ways). Stage 2: Then arrange these digits in increasing order ($1$ way). $\endgroup$
    – paw88789
    Feb 10 '15 at 13:29
  • $\begingroup$ If there were $2$ ways, you would do: $2 \binom{9}{6}$? Just supposing? (+1) $\endgroup$
    – Lebes
    Feb 10 '15 at 13:32
11
$\begingroup$

Another way to look at this is: take any six-digit number in which the digits are increasing from left to right. Insert the three digits that were not used, keeping the digits in increasing sequence. For each possible starting number there is only one way to do this; for example, $$ 235678 \mapsto \mathbf 1\ 23\ \mathbf 4\ 5678\ \mathbf 9 \mapsto 1 23 4 5678 9.$$

The process is reversible. That is, you can get any of the desired six-digit numbers with digits increasing from left to right by starting with $123456789$ and knocking out three digits.

In fact, there is one and only one way to get each possible six-digit number with the desired property by removing three digits from $123456789$. Hence the number of six-digit numbers you can get is simply the number of ways you can choose three digits to remove from among the nine digits of $123456789$, or $\binom93$.

Of course the order in which you remove the three digits does not matter; all that matters is in the end, which three digits you have removed.


In understanding these kinds of counting problems in general, rather than saying "the order matters" or "the order does not matter", it may be better to ask, "Can I produce different outcomes by choosing the items in a different order?"

For example, if I want to count how many three-digit numbers there are with no zeros and no two digits the same, I can choose three digits one at a time and write them down in the order in which I chose them; each sequence of choices gives a new number to be counted. For example, $231$ and $123$ are both counted as distinct outcomes. This gives me $9\cdot8\cdot7 = \frac{9!}{6!} = 504$ possible outcomes.

But if I am only allowed to write three-digit numbers whose digits are in increasing order, I cannot count $231$ and $123$ as distinct outcomes. One way to deal with this is to say, if I choose $2$ first, I cannot choose $1$ later, so the sequences of choices $231$ is impossible. An easier way to deal with this, however, is to allow myself to choose the digits subject only to the restriction that I cannot choose a digit that was previously chosen; but after choosing the numbers, I have to put them into increasing order. So it is possible to choose in sequence either $2,3,1$ or $1,2,3$, but each of these results in the same outcome ($123$) in the end. In this way I see there are $3! = 6$ different sequences of numbers that can be chosen (one for each of the $3!$ permutations of three digits) that all result in the same outcome (namely, those three digits arranged in increasing order). So if I take all the possible sequences of choices, and divide by $3!$, I get the correct answer, $\binom 93 = 84.$

In the first case I was able to produce different outcomes depending on the order in which I chose the digits. Hence I use the formula for counting permutations. In the second case, I was not able to produce different outcomes in that way (because of the restriction that the digits in the result must be written in a certain sequence), so I use the formula for counting combinations.

$\endgroup$
3
  • $\begingroup$ This uses the strategy used by the answerer Neal in the original question. $\endgroup$
    – user26486
    Feb 10 '15 at 23:45
  • $\begingroup$ @user314 I posted before a link was made to the other question; I might have posted differently otherwise. But there are some subtle differences in the answers, just as there is a subtle difference in the questions. (This question doubted the correctness of "unordered" combinations to solve an "ordered" problem.) $\endgroup$
    – David K
    Feb 11 '15 at 1:55
  • $\begingroup$ I agree.${}{}{}$ $\endgroup$
    – user26486
    Feb 11 '15 at 1:59
0
$\begingroup$

Generalization: $$ \binom{n+m}{n} = \sum_{j=0}^{m-1} \binom{n+j}{n} $$ Where set of size $n+m$ consists of elements $\{a_1, a_2, \ldots a_{n+m} \}$. Split the list $\binom{n+m}{n}$ into subsets where $a_n$ (in your case $a_1 = 4$) is the smallest number, $a_{n-1}$, etc.

$\endgroup$

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