|
%I #82 Jan 23 2023 13:13:09
%S 0,1,3,3,5,15,21,14,18,45,55,33,39,91,105,60,68,153,171,95,105,231,
%T 253,138,150,325,351,189,203,435,465,248,264,561,595,315,333,703,741,
%U 390,410,861,903,473,495,1035,1081,564,588,1225,1275,663,689,1431,1485,770
%N Numerator of average number of swaps needed to bubble sort a string of n distinct letters.
%C Denominators are given by the simple periodic sequence [1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, ...] (= A014695) thus we get an average of 1/2, 3/2, 3, 5, 15/2, 21/2, 14, 18, etc. swappings required to bubble sort a string of 2, 3, 4, 5, 6, ... letters.
%D E. Reingold, J. Nievergelt and N. Deo, Combinatorial Algorithms, Prentice-Hall, 1977, section 7.1, p. 287.
%H G. C. Greubel, <a href="/A064038/b064038.txt">Table of n, a(n) for n = 1..5000</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SimpleGraph.html">Simple Graph</a>.
%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (3,-6,10,-12,12,-10,6,-3,1).
%F a(n) = numerator(A001809(n)/(n!)).
%F a(4n) = A033991(n).
%F a(4n+1) = A007742(n).
%F a(4n+2) = A014634(n).
%F a(4n+3) = A033567(n+1).
%F a(n+1) = A061041(8*n-4). - _Paul Curtz_, Jan 03 2011
%F G.f.: -x^2*(1+4*x^3+x^6) / ( (x-1)^3*(1+x^2)^3 ). - _R. J. Mathar_, Jan 03 2011
%F a(n+1) = A060819(n)*A060819(n+1).
%F a(n+1) = A000217(n)/(period 4:repeat 2,1,1,2=A014695(n+2)=A130658(n+3)).
%F a(n) = 3*a(n-4) -3*a(n-8) +a(n-12). - _Paul Curtz_, Mar 04 2011
%F a(n) = +3*a(n-1) -6*a(n-2) +10*a(n-3) -12*a(n-4) +12*a(n-5) -10*a(n-6) +6*a(n-7) -3*a(n-8) +1*a(n-9). - _Joerg Arndt_, Mar 04 2011
%F a(n+1) = A026741(A000217(n)). - _Paul Curtz_, Apr 04 2011
%F a(n) = numerator(Sum_{k=0..n-1} k/2). - _Arkadiusz Wesolowski_, Aug 09 2012
%F a(n) = n*(n-1)*(3-i^(n*(n-1)))/8, where i=sqrt(-1). - _Bruno Berselli_, Oct 01 2012, corrected by _Vaclav Kotesovec_, Aug 09 2022
%F Sum_{n>=2} 1/a(n) = 4 - Pi/2. - _Amiram Eldar_, Aug 09 2022
%p [seq(numer((n*(n-1))/4), n=1..120)];
%t f[n_] := Numerator[n (n - 1)/4]; Array[f, 56]
%t f[n_] := n/GCD[n, 4]; Array[f[#] f[# - 1] &, 56]
%t LinearRecurrence[{3,-6,10,-12,12,-10,6,-3,1},{0,1,3,3,5,15,21,14,18},80] (* _Harvey P. Dale_, Jan 23 2023 *)
%o (PARI) vector(100, n, numerator(n*(n-1)/4)) \\ _G. C. Greubel_, Sep 21 2018
%o (Magma) [Numerator(n*(n-1)/4): n in [1..100]]; // _G. C. Greubel_, Sep 21 2018
%Y Cf. A014695 (denominators), A190186, A190187, A350660.
%Y Cf. A000217, A001809, A007742, A014634, A026741, A033567, A033991, A060819, A061041.
%K easy,nonn,frac
%O 1,3
%A _Antti Karttunen_, Aug 23 2001
|
