# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/ Search: id:a159324 Showing 1-1 of 1 %I A159324 #43 Jun 01 2021 11:59:41 %S A159324 0,0,2,16,118,926,7956,75132,777456,8771184,107307360,1416252960, %T A159324 20068629120,304002322560,4903642679040,83928856838400, %U A159324 1519397749094400,29010025797580800,582647327132774400,12280347845905305600,271030782903552000000,6251213902855219200000 %N A159324 n! times the average number of comparisons required by an insertion sort of n (distinct) elements. %H A159324 Alois P. Heinz, Table of n, a(n) for n = 0..448 %H A159324 Wikipedia, Insertion sort %H A159324 Index entries for sequences related to sorting %F A159324 a(n) = a(n-1)*(n) + n! *(n+1)/2 - (n-1)!. %F A159324 a(n) = Sum_k A159323(n,k) = Sum_k A129178(n,k) * (n(n-1)/2 - k). %F A159324 a(n) = n!/4 *(n^2+3*n-4*H(n)), where H(n) = Sum_{k=1..n} 1/k. - _Gary Detlefs_, Sep 02 2010 %F A159324 a(n) = A138772(n+1) - A000254(n). - _Gary Detlefs_, May 13 2012 %F A159324 a(n) = ((2*n^3-n^2-5*n+2)*a(n-1)-(n+2)*(n-1)^3*a(n-2))/((n-2)*(n+1)) for n>2. - _Alois P. Heinz_, Dec 16 2016 %F A159324 a(n) = 2 * A285231(n+1). - _Alois P. Heinz_, Apr 15 2017 %e A159324 For n=3, insertion sorting 123, 213, 213, 231, 312, 321 takes 3+3+3+2+3+2 = 4*3+2*2 = 16 comparisons. %p A159324 a:= proc(n) option remember; %p A159324 `if`(n<2, 0, a(n-1)*n + (n-1)! * (n-1)*(n+2)/2) %p A159324 end: %p A159324 seq(a(n), n=0..30); # _Alois P. Heinz_, May 14 2012 %p A159324 # second Maple program: %p A159324 a:= proc(n) option remember; `if`(n<3, [0$2, 2][n+1], %p A159324 ((2*n^3-n^2-5*n+2)*a(n-1)-(n+2)*(n-1)^3*a(n-2))/((n-2)*(n+1))) %p A159324 end: %p A159324 seq(a(n), n=0..30); # _Alois P. Heinz_, Dec 16 2016 %t A159324 a[n_] := n! ((n+1)(n+2)/4 - HarmonicNumber[n] - 1/2); Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Apr 12 2017, after _Gary Detlefs_ *) %Y A159324 Row sums of triangle A159323. %Y A159324 Cf. A000254, A001008, A002805, A138772, A212395, A285231. %K A159324 nonn %O A159324 0,3 %A A159324 Harmen Wassenaar (towr(AT)ai.rug.nl), Apr 10 2009 # Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE