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
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
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.
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
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
More terms from Larry Reeves (larryr(AT)acm.org), Mar 27 2001
STATUS
approved