AMM problem 12377

This is my first post (or second, depending on how you look at the world). For this, I decide to post the first AMM problem I solved with my friends Satvik Saha and Sohom Gupta.

Problem Statement -

We define a one-drop number as in problem 12377 from Problems and Solutions, The American Mathematical Monthly, Volume 130, 2023, Issue 3.

An integer is a one-drop number if its decimal digits \(d_1, \dots, d_n\) satisfy

$$1 \leq d_1 \leq d_2 \dots \leq d_i > d_{i + 1} \leq \dots \leq d_n$$

for some \(i\), with \(1 \leq i < n\).

For example, the numbers \(13802\) and \(49557\) are one-drop numbers, while the numbers \(12345\) and \(352712\) are not.

We answer the following question: for \(n \geq 2\), how many \(n\)-digit one-drop numbers are there?

Solution -

There are

$$\binom{n + 18}{18} - \binom{n + 9}{9} - n\cdot\binom{n + 8}{8}$$

one-drop numbers of length \(n \geq 2\).

The digits of every \(n\)-digit one-drop number \(d_1, \dots, d_n\) can be uniquely split into two zero-drop blocks \(A\) and \(B\), with digits \(1 \leq d_1 \leq \dots \leq d_i\) and \(0 \leq d_{i + 1} \leq \dots \leq d_n\). Here, is a zero-drop block consists of a sequence of non-decreasing decimal digits; we allow the leading digit to be \(0\).

Consider all \(19\)-tuples \( (a_1, \dots, a_9, b_0, b_1, \dots, b_9) \) of non-negative integers such that

$$a_1 + \dots + a_9 + b_0 + b_1 + \dots + b_9 = n.$$

Each tuple represents an \(n\)-digit number obtained by concatenating two zero-drop blocks \(A\) and \(B\), where \(a_d\) and \(b_d\) denote the number of occurrences of the digit \(d\) in the respective blocks. Clearly, there are \(\binom{n + 18}{18}\) such tuples. Note that each tuple of this kind represents either a zero-drop or a one-drop number, and each \(n\)-digit one-drop number is uniquely represented by such a tuple.

Discard all tuples where the block \(A\) is empty, with all \(a_d = 0\); the corresponding number is zero-drop. There are as many such tuples as there are non-negative integer solutions of 

$$b_0 + b_1 + \dots + b_9 = n,$$

that is, \(\binom{n + 9}{9}\). This leaves \(\binom{n + 18}{18} - \binom{n + 9}{9}\) tuples; call this set of tuples \(S\). Note that for any element in \(S\), the block \(A\) is non-empty. Thus, it represents a proper \(n\)-digit number since the leftmost digit is non-zero.

Suppose that a tuple \( (a_1, \dots, a_9, b_0, b_1, \dots, b_9) \in S\) represents a zero-drop number. Since some \(a_d > 0\), the digit \(0\) cannot appear in block \(B\), hence the number consists only of digits \(1\) through \(9\). There are \(\binom{n + 8}{8}\) such \(n\)-digit zero drop numbers, via counting the non-negative integer solutions of

$$c_1 + \dots + c_9 = n.$$

Each of these numbers has been represented by precisely \(n\) tuples from \(S\), because the first \(i\) digits of such a number can be placed in block \(A\) with the remaining digits in block \(B\) for all \(1 \leq i \leq n\).

For example, the \(5\)-digit zero-drop number \(11234\) can be broken into blocks \(A, B\) as \(1, 1234\) or \(11, 234\) or \(112, 34\) or \(1123, 4\) or \(11234, \emptyset\), each of which correspond to distinct tuples from \(S\).

Thus, precisely \(n\cdot\binom{n + 8}{8}\) tuples from \(S\) represent zero-drop numbers. The remaining $\binom{n + 18}{18} - \binom{n + 9}{9} - n\cdot\binom{n + 8}{8}$ tuples uniquely represent all \(n\)-digit one-drop numbers. $\square$