Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the 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