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,3

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

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

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

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.

Crossrefs

Cf. A043096, A152054.

Sequence in context: A308242 A260606 A181112 * A284961 A217742 A204692

Adjacent sequences: A152461 A152462 A152463 * A152465 A152466 A152467

Keyword

base,nonn

Author

Jon E. Schoenfield, Dec 05 2008

Extensions

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

Status

approved