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

Author

John W. Layman, Apr 16 2002

Keywords

• nonn
• base
• easy

Comments

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

Examples

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

Links

• Paolo Xausa, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (9,-27,27).

Crossrefs

Cf. A064017.

Programs

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 *)

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

Extensions

Corrected by T. D. Noe, Nov 01 2006