login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006231 a(n) = Sum_{k=2..n} n(n-1)...(n-k+1)/k.
(Formerly M3908)
11
0, 1, 5, 20, 84, 409, 2365, 16064, 125664, 1112073, 10976173, 119481284, 1421542628, 18348340113, 255323504917, 3809950976992, 60683990530208, 1027542662934897, 18430998766219317, 349096664728623316, 6962409983976703316, 145841989688186383337 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,3
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
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)
Donald B. Johnson, Finding all the elementary circuits of a directed graph, SIAM J. Comput. 4 (1975), 77-84. MR0398155 (53 #2010).
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
EXAMPLE
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
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 *)
PROG
(Haskell)
a006231 n = numerator $
sum $ tail $ zipWith (%) (scanl1 (*) [n, (n-1)..1]) [1..n]
-- Reinhard Zumkeller, Dec 27 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
CROSSREFS
Column k=1 of A136394.
Sequence in context: A006749 A002213 A099949 * A069007 A126987 A152185
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
More terms from Larry Reeves (larryr(AT)acm.org), Mar 27 2001
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:27 EDT 2024. Contains 370951 sequences. (Running on oeis4.)