# Decreasing sequence numbers with first digit $9$

Find the sum of all positive integers whose digits (in base ten) form a strictly decreasing sequence with first digit $9$.

The method I thought of for solving this was very computational and it depended on a lot of casework. Is there a nicer way to solve this question?

Note that there are $\displaystyle\sum_{n=0}^{9} \binom{9}{n} = 2^9$ such numbers.

• Form a strictly increasing what? If the first digit is $9$ it's hard for the digits to increase from there... – lulu Jul 6 '16 at 22:14
• @lulu Thanks, typo. – user19405892 Jul 6 '16 at 22:15
• So...you want the digits to decrease? Thus $9876543210$ is good, as is $9531$ but $99$ is not, yes? – lulu Jul 6 '16 at 22:15
• @lulu Yeah, that's right. – user19405892 Jul 6 '16 at 22:16
• Let's see...there are $2^9$ such numbers (any subset of $\{8,7,6,5,4,3,2,1,0\}$ can be ordered decreasingly in a unique way). So brute force is a bit grim, at least armed only with pencil and paper. There must be a shortcut... – lulu Jul 6 '16 at 22:20

For each digit $a$ from $0$ to $9$, let us count how many numbers there are in our sum with a digit of $a$ in the $10^n$ place. First, suppose $a<9$. A number with a digit of $a$ in the $10^n$ place has a subset of $\{0,1,\dots,a-1\}$ for its last $n$ digits, so there are $\binom{a}{n}$ choices for the last $n$ digits. The preceding digits (omitting the initial $9$) can form any subset of $\{8,7,\dots,a+1\}$, so there are $2^{8-a}$ choices for the preceding digits. So in total, all of the digits of $a$ in our numbers contribute $\sum_n 2^{8-a}\binom{a}{n}\cdot a10^n$ to the sum. By the binomial theorem, this is equal to $$2^{8-a}a(10+1)^a=2^8a\left(\frac{11}{2}\right)^a.$$

For $a=9$, we have no choice of preceding digits, so we just have $\binom{9}{n}$ choices. So the sum of the $9$ digits contributes $$\sum_n \binom{9}{n}9\cdot 10^n=9\cdot 11^9.$$

So in total, the sum is $$9\cdot 11^9+2^8\sum_{a=0}^8 a\left(\frac{11}{2}\right)^a.$$ Let us write $x=\frac{11}{2}$ and simplify the sum in the second term: $$\sum_{a=0}^8 ax^a=\sum_{b=1}^8\sum_{c=b}^8x^c=\sum_{b=1}^8\frac{x^9-x^b}{x-1}=\frac{8x^9-\frac{x^9-x}{x-1}}{x-1}.$$

Putting it all together, the original sum is $$9\cdot 11^9+2^8\cdot\frac{8x^9-\frac{x^9-x}{x-1}}{x-1}$$ for $x=\frac{11}{2}$. According to Wolfram Alpha, this evaluates to $23259261861$. That is, assuming I haven't made some algebra mistake somewhere.

• Nice -- I didn't know this other way to get $\sum_aax^a$. – joriki Jul 6 '16 at 23:06

If the digit with value $10^j$ is $k$, there are $\binom kj$ options for the digits after that and $2^{8-k}$ options for the digits before that (corresponding to the subsets of the digits between $k$ and $9$), except for $k=9$ there is $1$ option for the digits before (namely none). Thus the sum of the contributions from the $10^j$ digit is

$$10^j\left(\sum_{k=0}^8k\binom kj2^{8-k}+9\binom9j\right)\;,$$

and the sum of the contributions from all digits is

\begin{align} \sum_{j=0}^910^j\sum_{k=0}^8\left(k\binom kj2^{8-k}+9\binom9j\right) &= \sum_{k=0}^8k\cdot11^k2^{8-k}+9\cdot11^9 \\ &= 2^8\cdot q\frac{\mathrm d}{\mathrm dq}\left.\frac{q^9-1}{q-1}\right|_{q=\frac{11}2}+9\cdot11^9 \\ &= 2^8\cdot\frac{11}2\cdot\frac{8\left(\frac{11}2\right)^9-9\left(\frac{11}2\right)^8+1}{\left(\frac{11}2-1\right)^2}+9\cdot11^9 \\ &=23259261861\;. \end{align}

Here's code to check this result.

• Can you check the answer for this question: Determine the sum of all positive integers whose digits (in base ten) form either a strictly increasing or a strictly decreasing sequence. I get $25937423487$. – user19405892 Jul 6 '16 at 23:04
• @user19405892: It looks like you included numbers that start with '0'? I get $25617209040$ (but you can check for yourself by adapting the code I posted). – joriki Jul 6 '16 at 23:12
• How did you involve the derivative to calculate the sum? – user19405892 Jul 7 '16 at 0:41
• @user19405892: $\sum_kkq^k=q\frac{\mathrm d}{\mathrm dq}\sum_kq^k$. – joriki Jul 7 '16 at 2:33
• @user19405892 are you familiar with the derivative? Just remember that $kq^{k-1} = \frac{d}{dk} q^k$ (it is just the power rule). Multiply both sides by $q$ and you get that $kq^k = k\frac{d}{dk} q^k$. All that is left to do is take $q$ and $\frac{d}{dq}$ outside the sum (taking the derivative out isn't always valid, but it is here because polynomials are nice functions in this regard) – Brevan Ellefsen Jul 7 '16 at 3:44

Here a simple way to compute it with haskell. The idea is to take all subsequences of "876543210", prepend "9", parse that as an integer and sum them all:

Prelude> (sum $map (read.("9"++))$ Data.List.subsequences "876543210")::Integer
23259261861

• Could have used ('9':) (but that doesn't generalize as well), and the type annotation is not needed. – Christian Sievers Jul 6 '16 at 23:40

Suppose we treat the general problem of computing the sum of the contributions of the subsets of $[n]$ containing $n$ where the contribution is to order the elements of the set in a decreasing sequence, multiply by a power of ten corresponding to the element's position starting from the right and sum these values. (We will modify this at the end to account for the zero digit.)

Let $A_{n, q}$ be the sum of the contributions from subsets of $[n]$ with leading value $n$ and $q$ additional digits. We get the recurrence

$$A_{n+1, q} = \sum_{m=1}^n \left(A_{m, q-1} + {m-1\choose q-1} 10^q \times (n+1)\right).$$

The boundary conditions here are $A_{n, 0} = n$, $A_{0, q} = 0$ and $A_{n, q} = 0$ when $q\ge n.$

Introduce the generating function $$A(z, u) = \sum_{n\ge 0} \sum_{q\ge 0} A_{n,q} u^q z^n.$$

Multiply the recurrence by $u^q z^{n+1}$ and sum over $n\ge 0$ and $q\ge 1$ to get

$$A(z, u) - \sum_{n\ge 0} (n+1) z^{n+1} = \sum_{n\ge 0} \sum_{q\ge 1} u^q z^{n+1} \sum_{m=1}^n [z^m] [u^{q-1}] A(z, u) \\ + \sum_{n\ge 0} \sum_{q\ge 1} u^q z^{n+1} \sum_{m=1}^n {m-1\choose q-1} 10^q \times (n+1).$$

The first term is

$$\sum_{n\ge 0} u z^{n+1} \sum_{m=1}^n [z^m] \sum_{q\ge 1} u^{q-1} [u^{q-1}] A(z, u) \\ = \sum_{n\ge 0} u z^{n+1} \sum_{m=1}^n [z^m] A(z, u) \\ = uz \sum_{n\ge 0} z^{n} [z^n] \frac{1}{1-z} A(z, u) \\ = \frac{uz}{1-z} A(z, u).$$

The second term is

$$\sum_{n\ge 0} (n+1) z^{n+1} \sum_{m=1}^n \sum_{q\ge 1} u^q {m-1\choose q-1} 10^q \\ = \sum_{n\ge 0} (n+1) z^{n+1} \sum_{m=1}^n 10u (1+10u)^{m-1} = 10u \sum_{n\ge 0} (n+1) z^{n+1} \frac{(1+10u)^n-1}{(1+10u)-1} \\ = \sum_{n\ge 0} (n+1) z^{n+1} ((1+10u)^n-1) = \frac{z}{(1-(1+10u)z)^2} - \frac{z}{(1-z)^2}.$$

Solving the equation we get

$$A(z, u) = \frac{z(1-z)}{(1-(1+10u)z)^2 (1-z(1+u))}.$$

At this point we no longer need the classification according to the number of digits since we seek to sum the contributions having from $0$ extra digits to $n-1$ extra digits, the maximum possible. We thus set $u=1$ and obtain

$$B(z) = \frac{z(1-z)}{(1-11z)^2 (1-2z)} \\ = \frac{10}{99} \frac{1}{(1-11z)^2} - \frac{101}{891} \frac{1}{1-11z} + \frac{1}{81} \frac{1}{1-2z}.$$

Extracting coefficients and multiplying by $11$ to account for the zero digit which may or may not be present at the end we finally obtain the closed form

$$\frac{10}{9} (n+1) 11^n -\frac{101}{81} 11^n + \frac{11}{81} 2^n \\ = \frac{10}{9} n 11^n - \frac{11}{81} (11^n - 2^n).$$

This produces the following sequence starting at $n=1$:

$$11, 253, 4257, 63085, 872861, 11569833, 148920497, \\ 1876301845, 23259261861, 284671240513, 3448396611737, \\ 41419505367405, 493973128085261,\ldots$$

In particular the value for $n=9$ is

$$\bbox[5px,border:2px solid #00A000]{\Large 23259261861.}$$

The Maple code for the above was as follows:

with(combinat);

A :=
proc(n, q)
option remember;
if q = 0 then return n end if;

binomial(m - 1, q - 1)*10^q*n, m = 1 .. n - 1)
end;

AZU :=
proc()
option remember;
local LHS, RHS;

LHS := AGFSYM - z/(1-z)^2;

RHS := u*z/(1-z)*AGFSYM + z/(1-(1+10*u)*z)^2-z/(1-z)^2;

solve(LHS=RHS, AGFSYM);
end;

AGF := (n, q) -> coeftayl(coeftayl(AZU(), u=0, q), z=0, n);

X := n -> 10/9*n*11^n - 11/81*(11^n-2^n);

ENUM :=
proc(n)
option remember;
local dset, dlst, val, res;

res := 0;

for dset in powerset(n) do
dlst :=
sort([seq(el-1, el in dset), n]);