|
|
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
|
|
|
FORMULA
|
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
|
n*( hypergeom([1, 1, 1-n], [2], -1)-1) ;
simplify(%) ;
|
|
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]
(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
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
More terms from Larry Reeves (larryr(AT)acm.org), Mar 27 2001
|
|
STATUS
|
approved
|
|
|
|