This site is supported by donations to The OEIS Foundation.

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A003319 Number of connected permutations of [1..n] (those not fixing [1..j] for 0
 0, 1, 1, 3, 13, 71, 461, 3447, 29093, 273343, 2829325, 31998903, 392743957, 5201061455, 73943424413, 1123596277863, 18176728317413, 311951144828863, 5661698774848621, 108355864447215063, 2181096921557783605 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS Also the number of permutations with no global descents, as introduced by Aguiar and Sottile [Corollaries 6.3, 6.4 and Remark 6.5] Also the dimensions of the homogeneous components of the space of primitive elements of the Malvenuto-Reutenauer Hopf algebra of permutations. This result, due to Poirier and Reutenauer [Theoreme 2.1] is stated in this form in the work of Aguiar and Sottile [Corollary 6.3] and also in the work of Duchamp, Hivert and Thibon [Section 3.3] Related to number of subgroups of index n-1 in free group of rank 2 (i.e. maximal number of subgroups of index n-1 in any 2-generator group). See Problem 5.13(b) in Stanley's Enumerative Combinatorics, Vol. 2. Left border of triangle A144107 = A003319, with row sums = n!. [Gary W. Adamson, Sep 11 2008] Hankel transform is A059332. Hankel transform of aerated sequence is A137704(n+1). [Paul Barry, Oct 07 2008] For every n, a(n+1) is also the moment of order n for the probability density function rho(x)=exp(x)/(Ei(1,-x)*(Ei(1,-x)+2*I*Pi)) on the interval 0..infinity, with Ei the exponentiel-integral function. [Groux Roland, Jan 16 2009] Also (apparently), a(n+1) = number of rooted hypermaps with n darts on a surface of any genus (see Walsh 2012). - N. J. A. Sloane, Aug 01 2012 Also recurrent sequence A233824 (for n > 0) in Panaitopol's formula for pi(x), the number of primes <= x. - Jonathan Sondow, Dec 19 2013 REFERENCES M. Aguiar and A. Lauve, Antipode and Convolution Powers of the Identity in Graded Connected Hopf Algebras, FPSAC 2013 Paris, France DMTCS Proc. AS, 2013, 1083-1094; http://www.liafa.univ-paris-diderot.fr/fpsac13/pdfAbstracts/dmAS0198.pdf MARCELO AGUIAR AND SWAPNEEL MAHAJAN, ON THE HADAMARD PRODUCT OF HOPF MONOIDS, http://mosaic.math.tamu.edu/~maguiar/hadamard.pdf L. Comtet, Sur les coefficients de l'inverse de la serie formelle Sum n! t^n, Comptes Rend. Acad. Sci. Paris, A 275 (1972), 569-572. L. Comtet, Advanced Combinatorics, Reidel, 1974, pp. 84 (#25), 262 (#14) and 295 (#16). P. de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 2000, p. 23, N_{n,2}. M. A. Deryagina and A. D. Mednykh, On the enumeration of circular maps with given number of edges, Siberian Mathematical Journal, 54, No. 6, 2013, 624-639. J. D. Dixon, The probability of generating the symmetric group, Math. Z. 110 (1969) 199-205. J. D. Dixon, Asymptotics of generating the symmetric and alternating groups, Electron. J. Combin., Item R56 of Volume 12(1), 2005. I. M. Gessel and R. P. Stanley, Algebraic Enumeration, chapter 21 in Handbook of Combinatorics, Vol. 2, edited by R. L. Graham et al., The MIT Press, Mass, 1995. M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 22. A. King, Generating indecomposable permutations, Discrete Math., 306 (2006), 508-518. Steven Linton, James Propp, Tom Roby, Julian West, Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions, Journal of Integer Sequences, Vol. 15 (2012), #12.9.1. R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence, Aequat. Math., 80 (2010), 291-318. see p. 292. P. Ossona de Mendez and P. Rosenstiehl, Transitivity and connectivity of permutations, Combinatorics, 24 (No. 3, 2004), 487-501. L. Panaitopol, A formula for $\pi(x)$ applied to a result of Koninck-Ivi\'c, Nieuw Arch. Wisk. 5/1 55-56 (2000) S. Poirier and C. Reutenauer, Algebres Hopf de tableaux, Ann. Sci. Math. Quebec 19 (95), no. 1, 79-90. N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.13(b). R. P. Stanley, The Descent Set and Connectivity Set of a Permutation, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.8. LINKS T. D. Noe, Table of n, a(n) for n = 0..101 Marcelo Aguiar, Frank Sottile, Structure of the Malvenuto-Reutenauer Hopf algebra of permutations, arXiv:math.CO/0203282. Joerg Arndt, Fxtbook, p.281 Julien Berestycki, Eric Brunet and Zhan Shi, How many evolutionary histories only increase fitness?, arXiv preprint arXiv:1304.0246, 2013 David Callan, Counting Stabilized-Interval-Free Permutations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.1.8. Fan Chung, Ron Graham, Primitive juggling sequences, Am. Math. Monthly 115 (3) (2008) 185-194 G. Duchamp, F. Hivert, J.-Y. Thibon, Noncommutative symmetric functions VI: Free quasi-symmetric functions and related algebras, arXiv:math.CO/0105065 G. A. Edgar, Transseries for beginners, arXiv:0801.4877v5 P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 90 I. M. Gessel and R. P. Stanley Algebraic Enumeration (See pages 7-8 for generating function.) P. Hegarty and A. Martinsson, On the existence of accessible paths in various models of fitness landscapes, arXiv preprint arXiv:1210.4798, 2012 - From N. J. A. Sloane, Jan 01 2013 V. Jelínek, P. Valtr, Splittings and Ramsey Properties of Permutation Classes, arXiv preprint arXiv:1307.0027, 2013 M. K. Krotter, I. C. Christov, J. M. Ottino and R. M. Lueptow, Cutting and Shuffling a Line Segment: Mixing by Interval Exchange Transformations, Arxiv preprint arXiv:1208.2052, 2012. - From N. J. A. Sloane, Dec 25 2012 R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence Jean-Christophe Novelli and Jean-Yves Thibon, Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions (2008); arXiv:0806.3682. Discrete Math. 310 (2010), no. 24, 3584-3606. Timothy R. Walsh, Generating nonisomorphic maps and hypermaps without storing them, to appear in Proceedings of GASCom2012 FORMULA G.f.: 1-1/Sum (k! x^k ). Also a(n) = n! - Sum_{k=1..n-1} k!*a(n-k), n >= 1. a(n) = (-1)^{n-1} * det {| 1! 2! ... n! | 1 1! ... (n-1)! | 0 1 1! ... (n-2)! | ... | 0 ... 0 1 1! |} INVERTi transform of factorial numbers, A000142 starting from n=1. - Antti Karttunen, May 30 2003 Gives the row sums of the triangle [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...] DELTA [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ...] where DELTA is the operator defined in A084938; this triangle, read by rows is the sequence : 1; 0, 1; 0, 1, 2; 0, 1, 6, 6; 0, 1, 12, 34, 24; 0, 1, 20, 110, 210, 120; 0, 1, 30, 270, 974, 1452, 720; ... - Philippe Deléham, Dec 30 2003 a(n+1)=Sum_{k,0<=k<=n}A089949(n,k). - Philippe Deléham, Oct 16 2006 L.g.f.: Sum_{n>=1} a(n)*x^n/n = log( Sum_{n>=0} n!*x^n ) . - Paul D. Hanna, Sep 19 2007 G.f.: 1/(1-x/(1-2x/(1-2x/(1-3x/(1-3x/(1-4x/(1-4x/(1-.....))))))) (continued fraction); [Paul Barry, Oct 07 2008] For n > 0 let R be the n-th row of A090238. Then a(n) = Sum{i=0..n}(-1)^(i)*R[i]. [Peter Luschny, Mar 13 2009] a(n) = upper left term in M^(n-1), M = triangle A128175 as an infinite square production matrix (deleting the first "1"); as follows: 1, 1, 0, 0, 0, 0,... 2, 2, 1, 0, 0, 0,... 4, 4, 3, 1, 0, 0,... 8, 8, 7, 4, 1, 0,... 16, 16, 15, 11, 5, 1,... ... - Gary W. Adamson, Jul 14 2011 O.g.f. satisfies: A(x) = x - x*A(x) + A(x)^2 + x^2*A'(x). [Paul D. Hanna, Jul 30 2011] From Sergei N. Gladkovskii, Jun 24 2012: (Start) Let A(x) be the G.f., then A(x) = 1/Q(0), where Q(k) =  x + 1 + x*k - (k+2)*x/Q(k+1); (continued fraction Euler's 1st kind, 1-step). A(x) = (1-1/U(0))/x, when U(k) =  1 + x*(2*k+1)/(1 - 2*x*(k+1)/(2*x*(k+1) + 1/U(k+1))); (continued fraction, Euler's 3rd kind, 3-step). (End). G.f.: 1 - G(0)/2, where G(k)= 1 + 1/(1 - x*(2*k+2)/(x*(2*k+2) - 1 + x*(2*k+2)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 29 2013 G.f.: x/2*G(0), where G(k)= 1 + 1/(1 - x*(k+1)/(x*(k+1/2) + 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 06 2013 G.f.: x*G(0), where G(k)= 1 - x*(k+1)/(x - 1/G(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Aug 03 2013 G.f.: 1- 1/G(0), where G(k)= 1 - x*(k+1)/(x*(k+1) - 1/(1 - x*(k+1)/(x*(k+1) - 1/G(k+1) ))); (continued fraction). - Sergei N. Gladkovskii, Aug 07 2013 G.f.: x*W(0) , where W(k) = 1 - x*(k+1)/( x*(k+1) - 1/(1 - x*(k+2)/( x*(k+2) - 1/W(k+1) ))); (continued fraction). - Sergei N. Gladkovskii, Aug 25 2013 a(n) = A233824(n-1) if n > 0. (Proof. Set b(n) = A233824(n), so that b(n) = n*n! - Sum_{k=1..n-1} k!*b(n-k). To get a(n+1) = b(n) for n >= 0, induct on n, use (n+1)! = n*n! + n!, and replace k with k+1 in the sum.) - Jonathan Sondow, Dec 19 2013 EXAMPLE O.g.f.: x + x^2 + 3*x^3 + 13*x^4 + 71*x^5 + 461*x^6 + 3447*x^7 + 29093*x^8 + ... MAPLE INVERTi([seq(n!, n=1..20)]); f:=proc(n) option remember; if n=1 then 1 else n*n!-add((n-j)!*f(j), j=1..n-1); fi; end; [seq(f(n), n=1..50)]; # N. J. A. Sloane, Dec 28 2011 series(1-1/hypergeom([1, 1], [], x), x=0, 50); # Mark van Hoeij, Apr 18 2013 MATHEMATICA a[0]=0; a[n_] := a[n] = n! - Sum[k!*a[n-k], {k, 1, n-1}]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Oct 11 2011, after given formula *) CoefficientList[Assuming[Element[x, Reals], Series[1-E^(1/x)* x/ExpIntegralEi[1/x], {x, 0, 20}]], x] (* Vaclav Kotesovec, Mar 07 2014 *) PROG (PARI) {a(n) = local(A); if( n<1, 0, A = vector(n); A[1] = 1; for( k=2, n, A[k] = (k - 2) * A[k-1] + sum( j=1, k-1, A[j] * A[k-j])); A[n])} /* Michael Somos, Jul 24 2011 */ (PARI) {a(n)=local(A=x); for(i=1, n, A=x-x*A+A^2+x^2*A' +x*O(x^n)); polcoeff(A, n)} /* Paul D. Hanna, Jul 30 2011] CROSSREFS Leading diagonal of A059438. See A167894 for another version. Cf. A051296, A084938, A074664, A113869, A144107. Sequence in context: A167894 * A158882 A233824 A192239 A192936 A000261 Adjacent sequences:  A003316 A003317 A003318 * A003320 A003321 A003322 KEYWORD nonn,easy,nice,changed AUTHOR EXTENSIONS More terms from Michael Somos, Jan 26 2000 Additional comments from Marcelo Aguiar (maguiar(AT)math.tamu.edu), Mar 28 2002 Added a(0)=0 (some of the formulas may now need adjusting). - N. J. A. Sloane, Sep 12 2012 STATUS approved

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

Content is available under The OEIS End-User License Agreement .