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

0, 1, 5, 20, 84, 409, 2365, 16064, 125664, 1112073, 10976173, 119481284, 1421542628, 18348340113, 255323504917, 3809950976992, 60683990530208, 1027542662934897, 18430998766219317, 349096664728623316, 6962409983976703316, 145841989688186383337

Offset: 1

Author

R. K. Guy

Keywords

• nonn
• easy
• nice

Comments

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

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

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

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

Examples

			a(3) = 5 because the cycles in S_3 are (12), (13), (23), (123), (132).
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
		

References

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..450 (first 100 terms from T. D. Noe)
• Eric Babson, Moon Duchin, Annina Iseli, Pietro Poggi-Corradini, Dylan Thurston, Jamie Tucker-Foltz, Models of Random Spanning Trees, arXiv:2407.20226 [math.CO], 2023.
• R. K. Guy, Letter to N. J. A. Sloane, 1977
• Donald B. Johnson, Finding all the elementary circuits of a directed graph, SIAM J. Comput. 4 (1975), 77-84. MR0398155 (53 #2010).
• Jamie Tucker-Foltz, Code to compute dimension of P_n on GitHub.

Crossrefs

Cf. A059760, A000295.

Column k=1 of A136394.

Programs

Haskell

a006231 n = numerator $
   sum $ tail $ zipWith (%) (scanl1 (*) [n,(n-1)..1]) [1..n]
-- Reinhard Zumkeller, Dec 27 2011

Maple

A006231 := proc(n)
    n*( hypergeom([1,1,1-n],[2],-1)-1) ;
    simplify(%) ;
end proc: # R. J. Mathar, Aug 06 2013

Mathematica

a[n_] = n*(HypergeometricPFQ[{1,1,1-n}, {2}, -1] - 1); Table[a[n], {n, 1, 20}] (* Jean-François Alcover,  Mar 29 2011 *)
Table[Sum[Times@@Range[n-k+1,n]/k,{k,2,n}],{n,20}] (* Harvey P. Dale, Sep 23 2011 *)

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

Formula

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

a(n) = n*( 3F1(1,1,1-n; 2;-1) -1). - Jean-François Alcover, Mar 29 2011

E.g.f.: exp(x)*(log(1/(1-x))-x). - Geoffrey Critzer, Sep 12 2012

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

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

Extensions

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