cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

Original entry on oeis.org

1, 1, 1, 3, 13, 71, 461, 3447, 29093, 273343, 2829325, 31998903, 392743957, 5201061455, 73943424413, 1123596277863, 18176728317413, 311951144828863, 5661698774848621, 108355864447215063, 2181096921557783605, 46066653228356851631, 1018705098450570562877
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

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.
Also the left border of triangle A144107, 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 exponential-integral function. - Groux Roland, Jan 16 2009
Also (apparently), a(n+1) is the 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
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
Also, a(n) is the number of distinct leaf matrices of complete non-ambiguous trees of size n. - Daniel Chen, Oct 23 2022

Examples

			G.f. = 1 + x + x^2 + 3*x^3 + 13*x^4 + 71*x^5 + 461*x^6 + 3447*x^7 + 29093*x^8 + ...
From _Peter Luschny_, Aug 03 2022: (Start)
A permutation p in [n] (where n >= 0) is reducible if there exists an i in 1..n-1 such that for all j in the range 1..i and all k in the range i+1..n it is true that p(j) < p(k). (Note that a range a..b includes a and b.) If such an i exists we say that i splits the permutation at i.
Examples:
* () is not reducible since there is no index i which splits (). (=> a(0) = 1)
* (1) is not reducible since there is no index i which splits (1). (=> a(1) = 1)
* (1, 2) is reducible since index 1 splits (1, 2) as p(1) < p(2).
* (2, 1) is not reducible since at the only potential splitting point i = 1 we have p(1) > p(2). (=> a(2) = 1)
* For n = 3 we have (1, 2, 3), (1, 3, 2), and (2, 1, 3) are reducible and (2, 3, 1), (3, 1, 2), and (3, 2, 1) are irreducible. (End)

References

  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 25, Example 20.
  • E. W. Bowen, Letter to N. J. A. Sloane, Aug 27 1976.
  • 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.
  • H. P. Robinson, Letter to N. J. A. Sloane, Nov 19 1973.
  • 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. 1, Chap. 1, Ex. 128; Vol. 2, 1999, see Problem 5.13(b).

Links

Crossrefs

See A167894 for another version.
Bisections give A272656, A272657.
Row sums of A111184 and A089949.
Leading diagonal of A059438. A diagonal of A263484.
Cf. A051296, A084938, A074664, A113869, A144107.
Cf. A260503, A259472, A261214, A261239, A261253, A261254.
Cf. A090238, A000698, A356291 (reducible permutations).
Column k=0 of A370380 and A370381 (without pair of initial terms and with different offset).

Programs

  • Maple
    INVERTi([seq(n!,n=1..20)]);
A003319 := proc(n) option remember; n! - add((n-j)!*A003319(j), j=1..n-1) end;
[seq(A003319(n), n=0..50)]; # N. J. A. Sloane, Dec 28 2011
series(2 - 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, 0, 20}] (* Jean-François Alcover, Oct 11 2011, after given formula *)
CoefficientList[Assuming[Element[x,Reals],Series[2-E^(1/x)* x/ExpIntegralEi[1/x],{x,0,20}]],x] (* Vaclav Kotesovec, Mar 07 2014 *)
a[ n_] := If[ n < 2, 1, a[n] = (n - 2) a[n - 1] + Sum[ a[k] a[n - k], {k, n - 1}]]; (* Michael Somos, Feb 23 2015 *)
Table[SeriesCoefficient[1 + x/(1 + ContinuedFractionK[-Floor[(k + 2)/2]*x, 1, {k, 1, n}]), {x, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Sep 29 2017 *)
  • PARI
    {a(n) = my(A); if( n<1, 1, 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
    {if(n<1,1,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 */
  • Sage
    def A003319_list(len):
    R, C = [1], [1] + [0] * (len - 1)
    for n in range(1, len):
        for k in range(n, 0, -1):
            C[k] = C[k - 1] * k
        C[0] = -sum(C[k] for k in range(1, n + 1))
        R.append(-C[0])
    return R
print(A003319_list(21))  # Peter Luschny, Feb 19 2016

Formula

G.f.: 2 - 1/Sum_{k>=0} k!*x^k.
Also a(n) = n! - Sum_{k=1..n-1} k!*a(n-k) [Bowen, 1976].
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].
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 A089949. - Philippe Deléham, Dec 30 2003
a(n+1) = Sum_{k=0..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+x/(1-x/(1-2*x/(1-2*x/(1-3*x/(1-3*x/(1-4*x/(1-4*x/(1-...)))))))) (continued fraction). - Paul Barry, Oct 07 2008
a(n) = -Sum_{i=0..n} (-1)^i*A090238(n, i) for n > 0. - Peter Luschny, Mar 13 2009
From Gary W. Adamson, Jul 14 2011: (Start)
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, ...
... (End)
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).
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))). (End)
From Sergei N. Gladkovskii, Aug 03 2013: (Start)
Continued fractions:
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))).
G.f.: (x/2)*G(0), where G(k) = 1 + 1/(1 - x*(k+1)/(x*(k+1/2) + 1/G(k+1))).
G.f.: x*G(0), where G(k) = 1 - x*(k+1)/(x - 1/G(k+1)).
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)))).
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)))).
(End)
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
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
For n>0, a(n) = (A059439(n) - A259472(n))/2. - Vaclav Kotesovec, Aug 03 2015
From Peter Bala, May 23 2017: (Start)
G.f.: 1 + x/(1 + x - 2*x/(1 + 2*x - 3*x/(1 + 3*x - 4*x/(1 + 4*x - ...)))). Cf. A000698.
G.f.: 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)
Conjecture: a(n) = A370380(n-2, 0) = A370381(n-2, 0) for n > 1 with a(0) = a(1) = 1. - Mikhail Kurkov, Apr 26 2024

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
Edited and set a(0) = 1 by Peter Luschny, Aug 03 2022

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

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