A069515 - OEIS

%I #26 Aug 23 2024 10:57:08

%S 0,3,24,135,648,2835,11664,45927,174960,649539,2361960,8444007,

%T 29760696,103630995,357128352,1219657095,4132485216,13904090883,

%U 46490458680,154580775111,511395045480,1684116865683,5523066491184

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

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

%H Paolo Xausa, <a href="/A069515/b069515.txt">Table of n, a(n) for n = 1..1000</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (9,-27,27).

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

%F a(n) = (n-1)(n+1)3^(n-2). - _Ralf Stephan_, Sep 02 2003

%F G.f.: 3*x^2*(1-x)/(1-3*x)^3. - _Colin Barker_, May 01 2012

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

%t LinearRecurrence[{9, -27, 27}, {0, 3, 24}, 50] (* _Paolo Xausa_, Mar 18 2024 *)

%t nxt[{n_,a_}]:={n+1,3a+(2n+1)3^(n-1)}; NestList[nxt,{1,0},30][[;;,2]] (* _Harvey P. Dale_, Aug 23 2024 *)

%Y Cf. A064017.

%K nonn,base,easy

%O 1,2

%A _John W. Layman_, Apr 16 2002

%E Corrected by _T. D. Noe_, Nov 01 2006