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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

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.
(Formerly M2948)
69
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

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

REFERENCES

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

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.

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

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.

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.

M. Aguiar, A. Lauve, The characteristic polynomial of the Adams operators on graded connected Hopf algebras, 2014.

Marcelo Aguiar and Swapneel Mahajan, On the Hadamard product of Hopf monoids, 2013.

Joerg Arndt, Generating Random Permutations, PhD thesis, Australian National University, Camberra, Australia, (2010).

Joerg Arndt, Matters Computational (The 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

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.

John D. Dixon, Asymptotics of Generating the Symmetric and Alternating Groups, Electronic Journal of Combinatorics, vol 11(2), R56.

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.

A. King, Generating indecomposable permutations, Discrete Math., 306 (2006), 508-518.

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

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, arXiv:1103.4936 [math.CO].

R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence, Aequat. Math., 80 (2010), 291-318. see p. 292.

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.

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ć, Nieuw Arch. Wisk. 5/1 55-56 (2000).

S. Poirier and C. Reutenauer, Algèbres Hopf de tableaux, Ann. Sci. Math. Quebec 19 (95), no. 1, 79-90.

R. P. Stanley, The Descent Set and Connectivity Set of a Permutation, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.8.

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

N. J. A. Sloane.

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 .

Last modified September 20 21:40 EDT 2014. Contains 247020 sequences.