A152464 Number of n-digit bouncy numbers in which every pair of adjacent digits are distinct.

0, 0, 525, 3105, 18939, 114381, 693129, 4195557, 25405586, 153820395, 931359050, 5639156409, 34143908573, 206733865761, 1251728824798, 7578945799704, 45888871327435, 277847147039527, 1682304127857000, 10185986079451152

Offset: 1

Author

Jon E. Schoenfield, Dec 05 2008

Keywords

• base
• nonn

Comments

We might call such numbers "strictly bouncy numbers"; they exclude most n-digit "bouncy numbers" (cf. A152054) for n >= 4.

As n increases, a(n) approaches c/(2*cos(Pi*9/19))^n,

where c is 2.32290643963522604128193759601...

Is c the result of some simple expression?

From Jon E. Schoenfield, Dec 16 2008: (Start)

We could define the recursive formula

f(n) = 5*f(n-1) + 10*f(n-2) - 20*f(n-3) - 15*f(n-4) + 21*f(n-5) + 7*f(n-6) - 8*f(n-7) - f(n-8) + f(n-9)

and use a(n)=f(n) for n > 2 (a(n)=0 otherwise). Working backwards, given the terms f(11)=a(11) down through f(3)=a(3), the recursive formula would yield f(2)=81, f(1)=17 and f(0)=1, followed by the values 2, -1, 2, -2, 4, -5, 10, -14, 28, -42, 84, -132, etc., for negative values of n; these values are negative Catalan numbers for even n and twice (positive) Catalan numbers for odd n, down to f(-16).

The above results apply for numbers in base 10. In general, for base m+1 (so that the largest possible value for a digit is m), we can write

a(n) = f(n) for n > 2, 0 otherwise, where

f(n) = Sum_{j=1..m} (-1)^floor((j-1)/2)*binomial(floor((m+j)/2),j)*f(n-j) for n > 2,

f(2) = m^2, f(1) = 2*m - 1, f(0)=1,

f(n) = 2*Catalan((-1-n)/2) for odd n, 2 - 2m < n < 0 and

f(n) = -Catalan(-n/2) for even n, 2 - 2m <= n < 0.

(The expressions for n < 0 work more than far enough down to give enough terms to begin generating f(3), f(4), etc.) (End)

Links

• Index entries for linear recurrences with constant coefficients, signature (5,10,-20,-15,21,7,-8,-1,1).

Crossrefs

Cf. A043096, A152054.

Formula

a(n) = Sum_{i=1..9} (u(n,i) + d(n,i)) for n > 2 (0 otherwise), where

u(n,i) = Sum_{j=i+1..9} d(n-1,j) for n > 1,

d(n,i) = Sum_{j=0..i-1} u(n-1,j) for n > 1,

u(1,i) = 1, and

d(1,i) = 1.

Extensions

Correction to formula for odd negative n by Jon E. Schoenfield, Dec 22 2008