login
A069515
Number of transpositions (interchanges of adjacent digits, sometimes called inversions) needed to change all n-digit base 3 numbers into nondecreasing order.
1
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,....
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
KEYWORD
nonn,base,easy
AUTHOR
John W. Layman, Apr 16 2002
EXTENSIONS
Corrected by T. D. Noe, Nov 01 2006
STATUS
approved