A364342 a(n) is the number of base-10 nonbouncy numbers below 10^n.

10, 100, 475, 1675, 4954, 12952, 30817, 67987, 140907, 277033, 520565, 940455, 1641355, 2778305, 4576113, 7354549, 11560664, 17809754, 26936719, 40059819, 58659104, 84672094, 120609609, 169694999, 236030401, 324794055, 442473145, 597137095, 798756745, 1059575359

Offset

1,1

Comments

A bouncy number has digits that are neither monotonically increasing nor decreasing from left to right. A nonbouncy number is a number that is not bouncy. That is, either the digits are monotonically increasing or they are monotonically decreasing from left to right.

Links

Table of n, a(n) for n=1..30.

Project Euler, Problem 113. Non-bouncy numbers.

Index entries for linear recurrences with constant coefficients, signature (11,-55,165,-330,462,-462,330,-165,55,-11,1).

Formula

a(1) = 10, a(2) = 100. For n > 2, a(n) = binomial(n+9, n) + (n+1)*binomial(n+10, n+1)/10 - 10*n - 1.

G.f.: x*(10 - 10*x - 75*x^2 + 300*x^3 - 546*x^4 + 588*x^5 - 390*x^6 + 150*x^7 - 25*x^8 - 2*x^9 + x^10)/(1 - x)^11. - Stefano Spezia, Jul 20 2023

Example

a(3) = 475 because binomial(3+9, 3) + (3+1)*binomial(3+10, 3+1)/10 - 10*3 - 1 = 475.
a(4) = 1675 because binomial(4+9, 4) + (4+1)*binomial(4+10, 4+1)/10 - 10*4 - 1 = 1675.

Mathematica

a[n_] := -1 - 10 n + Binomial[9 + n, n] + 1/10 (1 + n) Binomial[10 + n, 1 + n]; Table[a[n], {n, 100}]

Crossrefs

Cf. A152054, A204692.

Sequence in context: A207713 A222716 A111434 * A208074 A092707 A224263

Adjacent sequences: A364339 A364340 A364341 * A364343 A364344 A364345

Keyword

nonn,base,easy

Author

Peter Cullen Burbery, Jul 19 2023

Status

approved