Combinations and permutations with falling numbers

1,039

Solution 1

Unless there's some unmentioned rule in this problem, I don't agree with the answer. For n=5, we would just pick 5 digits of our 10 with $ \binom{10}{5}$ results, which can't repeat, since each must be greater than its predecessor. They aren't ordered, but we then order them from least to greatest, from units digit to ten thousands digit. The sum you have listed would include 1 digit falling numbers, 2 digit falling numbers, and so on up to 5 digit falling numbers.

Solution 2

The number of ways of selecting a falling number with five digits is the number of ways five digits can be selected from the string $987654321$. For instance, the choice $\color{blue}{9}87\color{blue}{65}4\color{blue}{3}21\color{blue}{0}$ yields the number $96530$. Thus, there are $\binom{10}{5}$ five-digit falling numbers. By similar argument, there are $\binom{10}{6}$ six-digit falling numbers.

In general, there are $\binom{n}{k}$ falling numbers of length $k$. Therefore, the sum $$\binom{10}{1} + \binom{10}{2} + \binom{10}{3} + \binom{10}{4} + \binom{10}{5}$$ represents the number of falling numbers with up to $5$ digits and $$\binom{10}{1} + \binom{10}{2} + \binom{10}{3} + \binom{10}{4} + \binom{10}{5} + \binom{10}{6}$$ represents the number of falling numbers with up to $6$ digits. The total number of falling numbers is $$\sum_{k = 1}^{10} \binom{10}{k} = 2^{10} - 1$$

Share:
1,039

Related videos on Youtube

slowlearningnarcotics
Author by

slowlearningnarcotics

Updated on October 31, 2020

Comments

  • slowlearningnarcotics
    slowlearningnarcotics about 3 years

    A falling number is an integer whose decimal representation has the property that each digit except the units digit is larger than the one to its right. For example 96521 is a falling number but 89642 is not. How many n-digit falling numbers are there, for n = 5 and 6?

    10 C 1 + 10 C 2 + 10 C 3 + 10 C 4 + 10 C 5 = 637 numbers for n = 5

    10 C 1 + 10 C 2 + 10 C 3 + 10 C 4 + 10 C 5 + 10 C 6 = 847 numbers for n = 6

    • Can someone just walk me through how this makes sense?
    • N. F. Taussig
      N. F. Taussig about 8 years
      The answers you gave do not make sense for the problem you stated. Please check the statement of the problem and explain the source of the problem and its answers.
  • slowlearningnarcotics
    slowlearningnarcotics about 8 years
    hmm so for n = 5 it would be (10 C 5)^5? Can you elaborate on this?
  • Kevin Long
    Kevin Long about 8 years
    It would just be 10 choose 5. Once I know which 5 digits I'm using, their order is predetermined. For example, say I pick 3, 5, 6, 2 and 1. I know that the number I make from them must have the least digit in the ones place, the second least in the tens place, and so on, so I must get 65321. I can get no other falling number from it, and every falling number corresponds to such a subset of [10], so I can show a bijection between n-element subsets of [10] and falling numbers of n digits.
  • slowlearningnarcotics
    slowlearningnarcotics about 8 years
    Wouldn't our greatest number be limited to 4-9 in the case of n = 5 and 5-9 in the case of n = 6? Why are we picking out of 10 choices if this is the case? sorry I am just having a hard time grasping this
  • Kevin Long
    Kevin Long about 8 years
    If I choose 5 different digits of the 10 available, I am guaranteed for the greatest to be at least 4, because if I were to pick the least digits, I'd get 0,1,2,3 and 4. Any other combination would result in me having greatest digits greater than 4. The point is that once I pick 5 digits, there's only one way to get a falling number, and a falling number can always be represented by a set of digits.
  • Robert Israel
    Robert Israel about 8 years
    To see that the total number of falling numbers is $2^{10}-1$, you can construct a one-to-one correspondence $f$ from $\{1,2,\ldots, 2^{10}-1\}$ to the falling numbers as follows. Let the binary representation of $x$ be $d_{9} d_8 \ldots d_0$, $d_i \in \{0,1\}$. Then the base-10 digits of $f(x)$ (in decreasing order) are those $j$ for which $d_j = 1$. Thus the binary representation of $5$ is $0000000101$, $d_2 = d_0 = 1$, so $f(5) = 20$,