A069515 Number of transpositions (interchanges of adjacent digits, sometimes called inversions) needed to change all n-digit base 3 numbers into nondecreasing order.

0, 3, 24, 135, 648, 2835, 11664, 45927, 174960, 649539, 2361960, 8444007, 29760696, 103630995, 357128352, 1219657095, 4132485216, 13904090883, 46490458680, 154580775111, 511395045480, 1684116865683, 5523066491184

Offset

1,2

Comments

The corresponding problem for base 2 numbers gives a(n)=A001793(n-1) for n=2,3,4,....

Links

Paolo Xausa, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (9,-27,27).

Formula

a(n) = 3a(n-1)+(2n-1)3^(n-2).

a(n) = (n-1)(n+1)3^(n-2). - Ralf Stephan, Sep 02 2003

G.f.: 3*x^2*(1-x)/(1-3*x)^3. - Colin Barker, May 01 2012

Example

The base 3 number 1210 requires 4 transpositions: 1210->1201->1021->0121->0112.

Mathematica

LinearRecurrence[{9, -27, 27}, {0, 3, 24}, 50] (* Paolo Xausa, Mar 18 2024 *)
nxt[{n_, a_}]:={n+1, 3a+(2n+1)3^(n-1)}; NestList[nxt, {1, 0}, 30][[;; , 2]] (* Harvey P. Dale, Aug 23 2024 *)

Crossrefs

Cf. A064017.

Sequence in context: A183900 A001089 A359884 * A206949 A215636 A056350

Adjacent sequences: A069512 A069513 A069514 * A069516 A069517 A069518

Keyword

nonn,base,easy

Author

John W. Layman, Apr 16 2002

Extensions

Corrected by T. D. Noe, Nov 01 2006

Status

approved