login
a(n) = Sum_{k=2..n} n(n-1)...(n-k+1)/k.
(Formerly M3908)
11

%I M3908 #92 Jul 30 2024 05:08:45

%S 0,1,5,20,84,409,2365,16064,125664,1112073,10976173,119481284,

%T 1421542628,18348340113,255323504917,3809950976992,60683990530208,

%U 1027542662934897,18430998766219317,349096664728623316,6962409983976703316,145841989688186383337

%N a(n) = Sum_{k=2..n} n(n-1)...(n-k+1)/k.

%C a(n) is also the number of permutations in the symmetric group S_n that are pure cycles, see example. - Avi Peretz (njk(AT)netvision.net.il), Mar 24 2001

%C Also the number of elementary circuits in a complete directed graph with n nodes [D. B. Johnson, 1975]. - _N. J. A. Sloane_, Mar 24 2014

%C If one takes 1,2,3,4, ..., n and starts creating parenthetic products of k-tuples and adding, one gets a(n+1). For 1,2,3,4 one gets (1)+(2)+(3)+(4) = 10; (1*2)+(2*3)+(3*4) = 20; (1*2*3)+(2*3*4) = 30; (1*2*3*4) = 24; and 10+20+30+24 = 84 = a(5). - _J. M. Bergot_, Apr 24 2014

%C Let P_n be the set of probability distributions over orderings of n objects that can be obtained by drawing n real numbers from independent probability distributions and sorting. Then a(n) is conjectured to be the dimension of P_n, as a semi-algebraic subset of R^(n!). - _Jamie Tucker-Foltz_, Jul 29 2024

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A006231/b006231.txt">Table of n, a(n) for n = 1..450</a> (first 100 terms from T. D. Noe)

%H Eric Babson, Moon Duchin, Annina Iseli, Pietro Poggi-Corradini, Dylan Thurston, Jamie Tucker-Foltz, <a href="https://arxiv.org/abs/2407.20226">Models of Random Spanning Trees</a>, arXiv:2407.20226 [math.CO], 2023.

%H R. K. Guy, <a href="/A006231/a006231.pdf">Letter to N. J. A. Sloane, 1977</a>

%H Donald B. Johnson, <a href="http://dx.doi.org/10.1137/0204007">Finding all the elementary circuits of a directed graph</a>, SIAM J. Comput. 4 (1975), 77-84. MR0398155 (53 #2010).

%H Jamie Tucker-Foltz, <a href="https://github.com/mggg/MST-Distribution/blob/main/dimension_bounds.py">Code to compute dimension of P_n on GitHub</a>.

%F a(n+1) - a(n) = A000522(n) - 1.

%F a(n) = n*( 3F1(1,1,1-n; 2;-1) -1). - _Jean-François Alcover_, Mar 29 2011

%F E.g.f.: exp(x)*(log(1/(1-x))-x). - _Geoffrey Critzer_, Sep 12 2012

%F G.f.: (Q(0) - 1)/(1-x)^2, where Q(k)= 1 + (2*k + 1)*x/( 1 - x - 2*x*(1-x)*(k+1)/(2*x*(k+1) + (1-x)/Q(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, May 09 2013

%F Conjecture: a(n) + (-n-2)*a(n-1) + (3*n-2)*a(n-2) + 3*(-n+2)*a(n-3) + (n-3)*a(n-4) = 0. - _R. J. Mathar_, Aug 06 2013

%e a(3) = 5 because the cycles in S_3 are (12), (13), (23), (123), (132).

%e a(4) = 20 because there are 24 permutations of {1,2,3,4} but we don't count (12)(34), (13)(24), (14)(23) or the identity permutation. - _Geoffrey Critzer_, Nov 03 2012

%p A006231 := proc(n)

%p n*( hypergeom([1,1,1-n],[2],-1)-1) ;

%p simplify(%) ;

%p end proc: # _R. J. Mathar_, Aug 06 2013

%t a[n_] = n*(HypergeometricPFQ[{1,1,1-n}, {2}, -1] - 1); Table[a[n], {n, 1, 20}] (* _Jean-François Alcover_, Mar 29 2011 *)

%t Table[Sum[Times@@Range[n-k+1,n]/k,{k,2,n}],{n,20}] (* _Harvey P. Dale_, Sep 23 2011 *)

%o (Haskell)

%o a006231 n = numerator $

%o sum $ tail $ zipWith (%) (scanl1 (*) [n,(n-1)..1]) [1..n]

%o -- _Reinhard Zumkeller_, Dec 27 2011

%o (PARI) a(n) = n--; sum(ip=1, n, sum(j=1, n-ip+1, prod(k=j, j+ip-1, k))); \\ _Michel Marcus_, May 07 2014 after comment by _J. M. Bergot_

%Y Cf. A059760, A000295.

%Y Column k=1 of A136394.

%K nonn,easy,nice

%O 1,3

%A _R. K. Guy_

%E More terms from Larry Reeves (larryr(AT)acm.org), Mar 27 2001