login
This site is supported by donations to The OEIS Foundation.

 

Logo


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 < j < n). Also called indecomposable permutations, or irreducible permutations.
(Formerly M2948)
92

%I M2948

%S 0,1,1,3,13,71,461,3447,29093,273343,2829325,31998903,392743957,

%T 5201061455,73943424413,1123596277863,18176728317413,311951144828863,

%U 5661698774848621,108355864447215063,2181096921557783605,46066653228356851631,1018705098450570562877

%N Number of connected permutations of [1..n] (those not fixing [1..j] for 0 < j < n). Also called indecomposable permutations, or irreducible permutations.

%C Also the number of permutations with no global descents, as introduced by Aguiar and Sottile [Corollaries 6.3, 6.4 and Remark 6.5].

%C 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].

%C 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.

%C Left border of triangle A144107 = A003319, with row sums = n!. - _Gary W. Adamson_, Sep 11 2008

%C Hankel transform is A059332. Hankel transform of aerated sequence is A137704(n+1). - _Paul Barry_, Oct 07 2008

%C 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 exponential-integral function. - _Groux Roland_, Jan 16 2009

%C 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

%C Also recurrent sequence A233824 (for n > 0) in Panaitopol's formula for pi(x), the number of primes <= x. - _Jonathan Sondow_, Dec 19 2013

%C Also the number of mobiles (cyclic rooted trees) with an arrow from each internal vertex to a descendant of that vertex. - _Brad R. Jones_, Sep 12 2014

%C Up to sign, Möbius numbers of the shard intersection orders of type A, see Theorem 1.3 in Reading reference. - _F. Chapoton_, Apr 29 2015

%C Row sums of A111184 and A089949. - _Peter Bala_, Feb 17 2017

%C Alternating row sums of A090238. - _Peter Luschny_, Apr 12 2017

%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 25, Example 20.

%D E. W. Bowen, Letter to N. J. A. Sloane, Aug 27 1976.

%D L. Comtet, Advanced Combinatorics, Reidel, 1974, pp. 84 (#25), 262 (#14) and 295 (#16).

%D P. de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 2000, p. 23, N_{n,2}.

%D 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.

%D M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 22.

%D H. P. Robinson, Letter to N. J. A. Sloane, Nov 19 1973.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, Chap. 1, Ex. 128; Vol. 2, 1999, see Problem 5.13(b).

%H Seiichi Manyama, <a href="/A003319/b003319.txt">Table of n, a(n) for n = 0..449</a> (first 102 terms from T. D. Noe)

%H Marcelo Aguiar, Frank Sottile, <a href="http://arxiv.org/abs/math.CO/0203282">Structure of the Malvenuto-Reutenauer Hopf algebra of permutations</a>, arXiv:math/0203282 [math.CO], 2002-2005.

%H Marcelo Aguiar, Aaron Lauve, <a href="https://hal.inria.fr/hal-01229682">Convolution Powers of the Identity</a>, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, pp.1053-1064, 2013, DMTCS Proceedings. <hal-01229682>.

%H M. Aguiar and A. Lauve, <a href="https://www.irif.fr/~chapuy//fpsac13websiteBackup/fpsac13/pdfAbstracts/dmAS0198.pdf">Antipode and Convolution Powers of the Identity in Graded Connected Hopf Algebras</a>, FPSAC 2013 Paris, France DMTCS Proc. AS, 2013, 1083-1094.

%H M. Aguiar, A. Lauve, <a href="http://www.math.tamu.edu/~maguiar/adams.pdf">The characteristic polynomial of the Adams operators on graded connected Hopf algebras</a>, 2014.

%H Marcelo Aguiar and Swapneel Mahajan, <a href="http://mosaic.math.tamu.edu/~maguiar/hadamard.pdf">On the Hadamard product of Hopf monoids</a>, 2013.

%H Joerg Arndt, <a href="http://jjj.de/pub/arndt-rand-perm-thesis.pdf">Generating Random Permutations</a>, PhD thesis, Australian National University, Canberra, Australia, (2010).

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p. 281

%H R Bacher, C Reutenauer, <a href="http://arxiv.org/abs/1511.00426">Number of right ideals and a q-analogue of indecomposable permutations</a>, arXiv preprint arXiv:1511.00426 [math.CO], 2015.

%H Paul Barry, <a href="https://arxiv.org/abs/1804.06801">A note on number triangles that are almost their own production matrix</a>, arXiv:1804.06801 [math.CO], 2018.

%H Julien Berestycki, Eric Brunet and Zhan Shi, <a href="http://arxiv.org/abs/1304.0246">How many evolutionary histories only increase fitness?</a>, arXiv preprint arXiv:1304.0246 [math.PR], 2013.

%H Daniel Birmajer, Juan B. Gil, Michael D. Weiner, <a href="https://arxiv.org/abs/1803.07727">A family of Bell transformations</a>, arXiv:1803.07727 [math.CO], 2018.

%H E. W. Bowen & N. J. A. Sloane, <a href="/A003319/a003319.pdf">Correspondence, 1976</a>

%H David Callan, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Callan/callan91.html">Counting Stabilized-Interval-Free Permutations</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.1.8.

%H Peter Cameron's Blog, <a href="https://cameroncounts.wordpress.com/2011/04/09/the-symmetric-group-11/">The symmetric group, 11</a>, Posted 09/04/2011.

%H Fan Chung, R. L. Graham, <a href="http://www.jstor.org/stable/27642443">Primitive juggling sequences</a>, Am. Math. Monthly 115 (3) (2008) 185-194

%H L. Comtet, <a href="http://gallica.bnf.fr/ark:/12148/bpt6k5619085m/f9.image">Sur les coefficients de l'inverse de la série formelle Sum n! t^n</a>, Comptes Rend. Acad. Sci. Paris, A 275 (1972), 569-572.

%H L. Comtet, <a href="/A003319/a003319_1.pdf">Series inversions</a>, C. R. Acad. Sc. Paris, t. 275 (25 septembre 1972), 569-572. (Annotated scanned copy)

%H M. A. Deryagina and A. D. Mednykh, <a href="http://dx.doi.org/10.1134/S0037446613040058">On the enumeration of circular maps with given number of edges</a>, Siberian Mathematical Journal, 54, No. 6, 2013, 624-639.

%H J. D. Dixon, <a href="http://dx.doi.org/10.1007/BF01110210">The probability of generating the symmetric group</a>, Math. Z. 110 (1969) 199-205.

%H John D. Dixon, <a href="http://www.combinatorics.org/Volume_12/Abstracts/v12i1r56.html">Asymptotics of Generating the Symmetric and Alternating Groups</a>, Electronic Journal of Combinatorics, vol 11(2), R56.

%H G. Duchamp, F. Hivert, J.-Y. Thibon, <a href="https://arxiv.org/abs/math/0105065">Noncommutative symmetric functions VI: Free quasi-symmetric functions and related algebras</a>, arXiv:math/0105065 [math.CO], 2001.

%H G. A. Edgar, <a href="http://arxiv.org/abs/0801.4877">Transseries for beginners</a>, arXiv:0801.4877 [math.RA], 2008-2009.

%H Jesse Elliott, <a href="https://arxiv.org/abs/1809.06633">Asymptotic expansions of the prime counting function</a>, arXiv:1809.06633 [math.NT], 2018.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 90.

%H A. L. L. Gao, S. Kitaev, P. B. Zhang. <a href="https://arxiv.org/abs/1605.05490">On pattern avoiding indecomposable permutations</a>, arXiv:1605.05490 [math.CO], 2016.

%H I. M. Gessel and R. P. Stanley <a href="http://people.brandeis.edu/~gessel/homepage/papers/enum.pdf">Algebraic Enumeration</a> (See pages 7-8 for generating function.)

%H R. K. Guy, <a href="/A003320/a003320.pdf">Letter to N. J. A. Sloane, Mar 1974</a>

%H P. Hegarty and A. Martinsson, <a href="http://arxiv.org/abs/1210.4798">On the existence of accessible paths in various models of fitness landscapes</a>, arXiv preprint arXiv:1210.4798 [math.PR], 2012. - From _N. J. A. Sloane_, Jan 01 2013

%H V. Jelínek, P. Valtr, <a href="http://arxiv.org/abs/1307.0027">Splittings and Ramsey Properties of Permutation Classes</a>, arXiv preprint arXiv:1307.0027 [math.CO], 2013.

%H B. R. Jones, <a href="http://summit.sfu.ca/item/14554">On tree hook length formulas, Feynman rules and B-series</a>, Master's thesis, Simon Fraser University, 2014.

%H A. King, <a href="http://dx.doi.org/10.1016/j.disc.2006.01.005">Generating indecomposable permutations</a>, Discrete Math., 306 (2006), 508-518.

%H Y. Koh and S. Ree, <a href="http://dx.doi.org/10.1016/j.disc.2006.11.014">Connected permutation graphs</a>, Discrete Math. 307 (2007), 2628-2635.

%H M. K. Krotter, I. C. Christov, J. M. Ottino and R. M. Lueptow, <a href="http://arxiv.org/abs/1208.2052">Cutting and Shuffling a Line Segment: Mixing by Interval Exchange Transformations</a>, arXiv preprint arXiv:1208.2052 [physics.flu-dyn], 2012. - From _N. J. A. Sloane_, Dec 25 2012

%H Ajay Kumar, Chanchal Kumar, <a href="https://www.ias.ac.in/public/Volumes/pmsc/forthcoming/PMSC-D-17-00160.pdf">Monomial ideals induced by permutations avoiding patterns</a>, 2018.

%H Steven Linton, James Propp, Tom Roby, Julian West, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Roby/roby4.html">Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions</a>, Journal of Integer Sequences, Vol. 15 (2012), #12.9.1.

%H R. J. Martin and M. J. Kearney, <a href="http://arXiv.org/abs/1103.4936">An exactly solvable self-convolutive recurrence</a>, arXiv:1103.4936 [math.CO], 2011.

%H R. J. Martin and M. J. Kearney, <a href="http://dx.doi.org/10.1007/s00010-010-0051-0">An exactly solvable self-convolutive recurrence</a>, Aequat. Math., 80 (2010), 291-318. see p. 292.

%H Richard J. Martin and Michael J. Kearney, <a href="http://dx.doi.org/10.1007/s00493-014-3183-3">Integral representation of certain combinatorial recurrences</a>, Combinatorica: 35:3 (2015), 309-315.

%H Jean-Christophe Novelli and Jean-Yves Thibon, <a href="http://arxiv.org/abs/0806.3682">Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions</a> (2008); arXiv:0806.3682 [math.CO]. Discrete Math. 310 (2010), no. 24, 3584-3606.

%H P. Ossona de Mendez and P. Rosenstiehl, <a href="http://dx.doi.org/10.1007/s00493-004-0029-4">Transitivity and connectivity of permutations</a>, Combinatorica, 24 (No. 3, 2004), 487-501.

%H L. Panaitopol, <a href="http://www.nieuwarchief.nl/serie5/pdf/naw5-2000-01-1-055.pdf">A formula for pi(x) applied to a result of Koninck-Ivić</a>, Nieuw Arch. Wisk. 5/1 55-56 (2000).

%H Vincent Pilaud, <a href="http://arxiv.org/abs/1505.07665">Brick polytopes, lattice quotients, and Hopf algebras</a>, arXiv:1505.07665 [math.CO], 2015.

%H S. Poirier and C. Reutenauer, <a href="http://www.labmath.uqam.ca/~annales/volumes/19-1/PDF/079-090.pdf">Algèbres Hopf de tableaux</a>, Ann. Sci. Math. Quebec 19 (95), no. 1, 79-90.

%H N. Reading <a href="http://dx.doi.org/10.1007/s10801-010-0255-3">Noncrossing partitions and the shard intersection order</a>. J. Algebraic Combin. 33 (2011), no. 4. arXiv preprint <a href="http://arxiv.org/abs/0909.3288">arXiv:0909.3288</a>, [math.CO], 2009.

%H Herman P. Robinson, <a href="/A003116/a003116_1.pdf">Letter to N. J. A. Sloane, Nov 19 1973</a>.

%H R. P. Stanley, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Stanley/stanley80.html">The Descent Set and Connectivity Set of a Permutation</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.8.

%H Timothy R. Walsh, <a href="http://www.info2.uqam.ca/~walsh_t/papers/GENERATING NONISOMORPHIC.pdf">Space-efficient generation of nonisomorphic maps and hypermaps</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.3.

%F G.f.: 1-1/Sum (k! x^k ).

%F Also a(n) = n! - Sum_{k=1..n-1} k!*a(n-k), n >= 1 [Bowen, 1976].

%F Also coefficients in the divergent series expansion log Sum_{n>=0} n!*x^n = Sum_{n>=1} a(n+1)*x^n/n [Bowen, 1976].

%F a(n) = (-1)^{n-1} * det {| 1! 2! ... n! | 1 1! ... (n-1)! | 0 1 1! ... (n-2)! | ... | 0 ... 0 1 1! |}.

%F INVERTi transform of factorial numbers, A000142 starting from n=1. - _Antti Karttunen_, May 30 2003

%F 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

%F a(n+1) = Sum_{k=0..n} A089949(n,k). - _Philippe Deléham_, Oct 16 2006

%F L.g.f.: Sum_{n>=1} a(n)*x^n/n = log( Sum_{n>=0} n!*x^n ). - _Paul D. Hanna_, Sep 19 2007

%F 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

%F 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

%F From _Gary W. Adamson_, Jul 14 2011: (Start)

%F a(n) = upper left term in M^(n-1), M = triangle A128175 as an infinite square production matrix (deleting the first "1"); as follows:

%F 1, 1, 0, 0, 0, 0, ...

%F 2, 2, 1, 0, 0, 0, ...

%F 4, 4, 3, 1, 0, 0, ...

%F 8, 8, 7, 4, 1, 0, ...

%F 16, 16, 15, 11, 5, 1, ...

%F ... (End)

%F O.g.f. satisfies: A(x) = x - x*A(x) + A(x)^2 + x^2*A'(x). - _Paul D. Hanna_, Jul 30 2011

%F From _Sergei N. Gladkovskii_, Jun 24 2012: (Start)

%F Let A(x) be the g.f.; then

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

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

%F (End).

%F 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

%F 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

%F 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

%F 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

%F 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

%F 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

%F a(n) ~ n! * (1 - 2/n - 1/n^2 - 5/n^3 - 32/n^4 - 253/n^5 - 2381/n^6 - 25912/n^7 - 319339/n^8 - 4388949/n^9 - 66495386/n^10), for coefficients see A260503. - _Vaclav Kotesovec_, Jul 27 2015

%F For n>0, a(n) = (A059439(n) - A259472(n))/2. - _Vaclav Kotesovec_, Aug 03 2015

%F From _Peter Bala_, May 23 2017: (Start)

%F G.f. A(x) = x/(1 + x - 2*x/(1 + 2*x - 3*x/(1 + 3*x - 4*x/(1 + 4*x - ...)))). Cf. A000698.

%F 1 + A(x) = 1/(1 - x/(1 + x - x/(1 - 2*x/(1 - 2*x/(1 - 3*x/(1 - 3*x/(1 - 4*x/(1 - 4*x/(1 - ...))))))))). (End)

%e G.f. = x + x^2 + 3*x^3 + 13*x^4 + 71*x^5 + 461*x^6 + 3447*x^7 + 29093*x^8 + ...

%p INVERTi([seq(n!,n=1..20)]);

%p 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

%p series(1-1/hypergeom([1,1],[],x),x=0,50); # _Mark van Hoeij_, Apr 18 2013

%t 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 *)

%t CoefficientList[Assuming[Element[x,Reals],Series[1-E^(1/x)* x/ExpIntegralEi[1/x],{x,0,20}]],x] (* _Vaclav Kotesovec_, Mar 07 2014 *)

%t a[ n_] := If[ n < 2, Boole[n == 1], a[n] = (n - 2) a[n - 1] + Sum[ a[k] a[n - k], {k, n - 1}]]; (* _Michael Somos_, Feb 23 2015 *)

%t Table[SeriesCoefficient[x/(1 + ContinuedFractionK[-Floor[(k + 2)/2]*x, 1, {k, 1, n}]), {x, 0, n}], {n, 0, 20}] (* _Vaclav Kotesovec_, Sep 29 2017 *)

%o (PARI) {a(n) = my(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 */

%o (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 */

%o (Sage)

%o def A003319_list(len):

%o R, C = [0], [1]+[0]*(len-1)

%o for n in (1..len-1):

%o for k in range(n, 0, -1):

%o C[k] = C[k-1] * k

%o C[0] = -sum(C[k] for k in (1..n))

%o R.append(-C[0])

%o return R

%o print A003319_list(21) # _Peter Luschny_, Feb 19 2016

%Y Leading diagonal of A059438.

%Y See A167894 for another version.

%Y Bisections give A272656, A272657.

%Y Cf. A051296, A084938, A074664, A113869, A144107.

%Y Cf. A260503, A259472, A261214, A261239, A261253, A261254.

%Y Cf. A111184, A089949, A090238, A000698

%K nonn,easy,nice

%O 0,4

%A _N. J. A. Sloane_

%E More terms from _Michael Somos_, Jan 26 2000

%E Additional comments from Marcelo Aguiar (maguiar(AT)math.tamu.edu), Mar 28 2002

%E Added a(0)=0 (some of the formulas may now need adjusting). - _N. J. A. Sloane_, Sep 12 2012

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 February 20 21:16 EST 2019. Contains 320350 sequences. (Running on oeis4.)