|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
The corresponding problem for base 2 numbers gives a(n)=A001793(n-1) for n=2,3,4,....
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = 3a(n-1)+(2n-1)3^(n-2).
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,base,easy,changed
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
