login
This site is supported by donations 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)
9
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)

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).

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

Cf. A059760, A000295.

Column k=1 of A136394.

Sequence in context: A006749 A002213 A099949 * A069007 A126987 A152185

Adjacent sequences:  A006228 A006229 A006230 * A006232 A006233 A006234

KEYWORD

nonn,easy,nice

AUTHOR

R. K. Guy

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 16 12:41 EDT 2019. Contains 327113 sequences. (Running on oeis4.)