|
| |
|
|
A003319
|
|
Number of connected permutations of [1..n] (those not fixing [1..j] for 0<j<n). Also called indecomposable permutations.
(Formerly M2948)
|
|
66
|
|
|
|
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
|
|
|
REFERENCES
|
Marcelo Aguiar (Texas A&M University) and Frank Sottile (University of Massachusetts at Amherst). math.CO/0203282 Structure of the Malvenuto-Reutenauer Hopf algebra of permutations.
MARCELO AGUIAR AND SWAPNEEL MAHAJAN, ON THE HADAMARD PRODUCT OF HOPF MONOIDS, http://mosaic.math.tamu.edu/~maguiar/hadamard.pdf - From N. J. A. Sloane, Dec 24 2012
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}.
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.
G. Duchamp (University of Rouen), F. Hivert and J.-Y. Thibon (University of Marne-la-Vallee). math.CO/0105065 Noncommutative symmetric functions VI: Free quasi-symmetric functions and related algebras.
G. A. Edgar, Transseries for beginners, arXiv 0801.4877v5
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.
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
M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 22.
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
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); http://arxiv.org/abs/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\'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
Joerg Arndt, Fxtbook, p.281
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
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.)
R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence
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 DELEHAM, 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).
|
|
|
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[n_] := a[n] = n! - Sum[k!*a[n-k], {k, 1, n-1}]; Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Oct 11 2011, after given formula *)
|
|
|
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.
Cf. A051296, A084938, A074664, A113869.
A144107 [From Gary W. Adamson, Sep 11 2008]
Sequence in context: A126390 A167894 * A158882 A192239 A192936 A000261
Adjacent sequences: A003316 A003317 A003318 * A003320 A003321 A003322
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
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
|
| |
|
|
