A090238 -id:A090238 - cp's OEIS frontend

A084938 Triangle read by rows: T(n,k) = Sum_{j>=0} j!*T(n-j-1, k-1) for n >= 0, k >= 0.

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 6, 5, 3, 1, 0, 24, 16, 9, 4, 1, 0, 120, 64, 31, 14, 5, 1, 0, 720, 312, 126, 52, 20, 6, 1, 0, 5040, 1812, 606, 217, 80, 27, 7, 1, 0, 40320, 12288, 3428, 1040, 345, 116, 35, 8, 1, 0, 362880, 95616, 22572, 5768, 1661, 519, 161, 44, 9, 1

Offset: 0

Philippe Deléham, Jul 16 2003; corrections Dec 17 2008, Dec 20 2008, Feb 05 2009

Triangle T(n,k) is [0,1,1,2,2,3,3,4,4,...] DELTA [1,0,0,0,0,0,...] = A110654 DELTA A000007.
In general, the triangle [r_0,r_1,r_2,r_3,...] DELTA [s_0,s_1,s_2,s_3,...] has generating function 1/(1-(r_0*x+s_0*x*y)/(1-(r_1*x+s_1*x*y)/(1-(r_2*x+s_2*x*y)/(1-(r_3*x+s_3*x*y)/(1-...(continued fraction). See also the Formula section below.
T(n,k) = number of permutations on [n] that (i) contain a 132 pattern only as part of a 4132 pattern and (ii) start with n+1-k. For example, for n >= 1, T(n,1) = (n-1)! counts all (n-1)! permutations on [n] that start with n: either they avoid 132 altogether or the initial entry serves as the "4" in a 4132 pattern and T(4,3) = 3 counts 2134, 2314, 2341. - David Callan, Jul 20 2005
T(n,k) is the number of permutations on [n] that (i) contain a (scattered) 342 pattern only as part of a 1342 pattern and (ii) contain 1 in position k. For example, T(4,3) counts 3214, 4213, 4312. (It does not count, say, 2314 because 231 forms an offending 342 pattern.) - David Callan, Jul 20 2005
Riordan array (1,x*g(x)) where g(x) is the g.f. of the factorials (n!). - Paul Barry, Sep 25 2008
Modulo 2, this sequence becomes A106344.
T(n,k) is the number of permutations of {1,2,...,n} having k cycles such that the elements of each cycle of the permutation form an interval. - Ran Pan, Nov 11 2016
The convolution triangle of the factorial numbers. - Peter Luschny, Oct 09 2022

			From _Paul Barry_, Sep 25 2008: (Start)
Triangle [0,1,1,2,2,3,3,4,4,5,5,...] DELTA [1,0,0,0,0,...] begins
  1;
  0,      1;
  0,      1,     1;
  0,      2,     2,     1;
  0,      6,     5,     3,    1;
  0,     24,    16,     9,    4,    1;
  0,    120,    64,    31,   14,    5,   1;
  0,    720,   312,   126,   52,   20,   6,   1;
  0,   5040,  1812,   606,  217,   80,  27,   7,  1;
  0,  40320, 12288,  3428, 1040,  345, 116,  35,  8, 1;
  0, 362880, 95616, 22572, 5768, 1661, 519, 161, 44, 9, 1. (End)
From _Paul Barry_, May 14 2009: (Start)
The production matrix is
  0,   1;
  0,   1,  1;
  0,   1,  1, 1;
  0,   2,  1, 1, 1;
  0,   7,  2, 1, 1, 1;
  0,  34,  7, 2, 1, 1, 1;
  0, 206, 34, 7, 2, 1, 1, 1;
which is based on A075834. (End)

T. D. Noe, Rows n = 0..100 of triangle, flattened
Paul Barry, A Note on a One-Parameter Family of Catalan-Like Numbers, JIS 12 (2009) 09.5.4.
Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009), Article 09.7.6.
Paul Barry, On the inversion of Riordan arrays, arXiv:2101.06713 [math.CO], 2021.
Paul Barry and A. Hennessy, A Note on Narayana Triangles and Related Polynomials, Riordan Arrays, and MIMO Capacity Calculations, J. Int. Seq. 14 (2011), Article 11.3.8.
David Callan, A combinatorial interpretation of the eigensequence for composition, arXiv:math/0507169 [math.CO], 2005.
David Callan, A Combinatorial Interpretation of the Eigensequence for Composition, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.4.
H. Fuks and J. M. G. Soto, Exponential convergence to equilibrium in cellular automata asymptotically emulating identity, arXiv preprint arXiv:1306.1189 [nlin.CG], 2013.
Sergey Kitaev and Philip B. Zhang, Distributions of mesh patterns of short lengths, arXiv:1811.07679 [math.CO], 2018.
Peter Luschny, Transformations of integer sequences.
R. J. Mathar, Properties of Deleham's Delta Transformation: OEIS A084938

Cf. A003149, A051295 (row sums), A052186, A090238,
Cf. A287899.
Columns: A000007, A000142, A003149, A090595, A090319.
Diagonals: A000012, A001477, A000096, A092286, A090386, A090391, A090392, A090393, A090394.

function T(n,k) // T = A084938
  if k lt 0 or k gt n then return 0;
  elif n eq 0 or k eq n then return 1;
  elif k eq 0 then return 0;
  else return (&+[Factorial(j)*T(n-j-1,k-1): j in [0..n-1]]);
  end if; return T;
end function;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Nov 10 2022

DELTA := proc(r,s,n) local T,x,y,q,P,i,j,k,t1; T := array(0..n,0..n);
for i from 0 to n do q[i] := x*r[i+1]+y*s[i+1]; od: for k from 0 to n do P[0,k] := 1; od: for i from 0 to n do P[i,-1] := 0; od:
for i from 1 to n do for k from 0 to n do P[i,k] := sort(expand(P[i,k-1] + q[k]*P[i-1,k+1])); od: od:
for i from 0 to n do t1 := P[i,0]; for j from 0 to i do T[i,j] := coeff(coeff(t1,x,i-j),y,j); od: lprint( seq(T[i,j],j=0..i) ); od: end;
# To produce the current triangle: s3 := n->floor((n+1)/2); s4 := n->if n = 0 then 1 else 0; fi; r := [seq(s3(i),i= 0..40)]; s := [seq(s4(i),i=0..40)]; DELTA(r,s,20);
# Uses function PMatrix from A357368.
PMatrix(10, n -> factorial(n - 1)); # Peter Luschny, Oct 09 2022

a[0, 0] = 1; a[n_, k_] := a[n, k] = Sum[j! a[n - j - 1, k - 1], {j, 0, n - 1}]; Flatten[Table[a[i, j], {i, 0, 10}, {j, 0, i}]] (* T. D. Noe, Feb 22 2012 *)
DELTA[r_, s_, m_] := Module[{p, q, t, x, y}, q[k_] := x*r[[k+1]] + y*s[[k+1]]; p[0, ] = 1; p[, -1] = 0; p[n_ /; n >= 1, k_ /; k >= 0] := p[n, k] = p[n, k-1] + q[k]*p[n-1, k+1] // Expand; t[n_, k_] := Coefficient[p[n, 0], x^(n-k)*y^k]; t[0, 0] = p[0, 0]; Table[t[n, k], {n, 0, m}, {k, 0, n}]]; DELTA[Floor[Range[10]/2], Prepend[Table[0, {10}], 1], 10] (* Jean-François Alcover, Sep 12 2013, after Philippe Deléham *)

def delehamdelta(R, S) :
    L = min(len(R), len(S)) + 1
    ring = PolynomialRing(ZZ, 'x')
    x = ring.gen()
    A = [Rk + x*Sk for Rk, Sk in zip(R, S)]
    C = [ring(0)] + [ring(1) for i in range(L)]
    for k in (1..L) :
        for n in range(k-1,0,-1) :
            C[n] = C[n-1] + C[n+1]*A[n-1]
        yield list(C[1])
def A084938_triangle(n) :
    for row in delehamdelta([(i+1)//2 for i in (0..n)], [0^i for i in (0..n)]):
        print(row)
A084938_triangle(10) # Peter Luschny, Jan 28 2012

The operator DELTA takes two sequences r = (r_0, r_1, ...), s = (s_0, s_1, ...) and produces a triangle T(n, k), 0 <= k <= n, as follows:
Let q(k) = x*r_k + y*s_k for k >= 0; let P(n, k) (n >= 0, k >= -1) be defined recursively by P(0, k) = 1 for k >= 0; P(n, -1) = 0 for n >= 1; P(n, k) = P(n, k-1) + q(k)*P(n-1, k+1) for n >= 1, k >= 0. Then P(n, k) is a homogeneous polynomial in x and y of degree n and T(n, k) = coefficient of x^(n-k)*y^k in P(n, 0).
T(n, n) = 1.
T(k+1, k) = A001477(k).
T(k+2, k) = A000096(k).
T(n+1, 1) = A000142(n).
T(n+2, 2) = A003149(n).
T(n+3, 3) = A090595(n).
T(n+4, 4) = A090319(n).
T(m+n, m) = Sum_{k=0..n} A090238(n, k)*binomial(m, k).
G.f. for column k: Sum_{n>=0} T(k+n, k)*x^n = (Sum_{n>=0} n!*x^n )^k.
For k>0, T(n+k, k) = Sum_{a_1 + a_2 + .. + a_k = n} (a_1)!*(a_2)!*..*(a_k)!; a_i>=0, n>=0.
T(n,k) = Sum_{j>=0} A075834(j)*T(n-1,k+j-1).
T(2n,n) = A287899(n). - Alois P. Heinz, Jun 02 2017
From G. C. Greubel, Nov 10 2022: (Start)
Sum_{k=0..n} T(n, k) = A051295(n).
Sum_{k=0..n} (-1)^k*T(n, k) = [n=0] - A052186(n-1)*[n>0]. (End)

Name edited by Derek Orr, May 01 2015

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

N. J. A. Sloane

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

			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)

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

Seiichi Manyama, Table of n, a(n) for n = 0..449 (first 102 terms from T. D. Noe)
Marcelo Aguiar and Frank Sottile, Structure of the Malvenuto-Reutenauer Hopf algebra of permutations, arXiv:math/0203282 [math.CO], 2002-2005.
Marcelo Aguiar and Aaron Lauve, Convolution Powers of the Identity, 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. .
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 and 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.
Nicolas Andrews, Lucas Gagnon, Félix Gélinas, Eric Schlums, and Mike Zabrocki, When are Hopf algebras determined by integer sequences?, arXiv:2505.06941 [math.CO], 2025. See p. 10.
Joerg Arndt, Generating Random Permutations, PhD thesis, Australian National University, Canberra, Australia, (2010).
Joerg Arndt, Matters Computational (The Fxtbook), p. 281
Roland Bacher and Christophe Reutenauer, Number of right ideals and a q-analogue of indecomposable permutations, arXiv preprint arXiv:1511.00426 [math.CO], 2015.
Paul Barry, A note on number triangles that are almost their own production matrix, arXiv:1804.06801 [math.CO], 2018.
Julien Berestycki, Eric Brunet and Zhan Shi, How many evolutionary histories only increase fitness?, arXiv preprint arXiv:1304.0246 [math.PR], 2013.
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, A family of Bell transformations, arXiv:1803.07727 [math.CO], 2018.
E. W. Bowen and N. J. A. Sloane, Correspondence, 1976.
Glenn Bruda, Asymptotic expansions for the reciprocal Hardy-Littlewood logarithmic integrals, arXiv:2412.19866 [math.CO], 2024. See pages 1, 7.
David Callan, Counting Stabilized-Interval-Free Permutations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.1.8.
Peter Cameron's Blog, The symmetric group, 11, Posted 09/04/2011.
Mahir Bilen Can, Luke Nelson, and Kevin Treat, A Catalanization Map on the Symmetric Group, Enum. Comb. Appl. (2022) Vol. 2, No. 4, #S4PP7.
Daniel Chen and Sebastian Ohlig, Associated Permutations of Complete Non-Ambiguous Trees and Zubieta's Conjecture, arXiv:2210.11117 [math.CO], 2022.
Fan Chung and R. L. Graham, Primitive juggling sequences, Am. Math. Monthly 115 (3) (2008) 185-194.
L. Comtet, Sur les coefficients de l'inverse de la série formelle Sum n! t^n, Comptes Rend. Acad. Sci. Paris, A 275 (1972), 569-572.
L. Comtet, Series inversions, C. R. Acad. Sc. Paris, t. 275 (25 septembre 1972), 569-572. (Annotated scanned copy)
Xinle Dai, Jordan Long, and Karen Yeats, Subdivergence-free gluings of trees, arXiv:2106.07494 [math.CO], 2021.
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.
Stoyan Dimitrov, Sorting by shuffling methods and a queue, arXiv:2103.04332 [math.CO], 2021.
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, and J.-Y. Thibon, Noncommutative symmetric functions VI: Free quasi-symmetric functions and related algebras, arXiv:math/0105065 [math.CO], 2001.
G. A. Edgar, Transseries for beginners, arXiv:0801.4877 [math.RA], 2008-2009.
Richard Ehrenborg, Gábor Hetyei, and Margaret Readdy, Catalan-Spitzer permutations, arXiv:2310.06288 [math.CO], 2023. See p. 19.
Jesse Elliott, Asymptotic expansions of the prime counting function, arXiv:1809.06633 [math.NT], 2018.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 90.
A. L. L. Gao, S. Kitaev, and P. B. Zhang. On pattern avoiding indecomposable permutations, arXiv:1605.05490 [math.CO], 2016.
I. M. Gessel and R. P. Stanley Algebraic Enumeration (See pages 7-8 for generating function.)
R. K. Guy, Letter to N. J. A. Sloane, Mar 1974
P. Hegarty and A. Martinsson, On the existence of accessible paths in various models of fitness landscapes, arXiv preprint arXiv:1210.4798 [math.PR], 2012. - From _N. J. A. Sloane_, Jan 01 2013
V. Jelínek and P. Valtr, Splittings and Ramsey Properties of Permutation Classes, arXiv preprint arXiv:1307.0027 [math.CO], 2013.
B. R. Jones, On tree hook length formulas, Feynman rules and B-series, Master's thesis, Simon Fraser University, 2014.
A. King, Generating indecomposable permutations, Discrete Math., 306 (2006), 508-518.
Y. Koh and S. Ree, Connected permutation graphs, Discrete Math. 307 (2007), 2628-2635.
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 [physics.flu-dyn], 2012. - From _N. J. A. Sloane_, Dec 25 2012
Ajay Kumar and Chanchal Kumar, Monomial ideals induced by permutations avoiding patterns, 2018.
Chanchal Kumar and Amit Roy, Integer Sequences and Monomial Ideals, arXiv:2003.10098 [math.CO], 2020.
Steven Linton, James Propp, Tom Roby, and 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], 2011.
R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence, Aequat. Math., 80 (2010), 291-318. see p. 292.
Richard J. Martin and Michael J. Kearney, Integral representation of certain combinatorial recurrences, Combinatorica: 35:3 (2015), 309-315.
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 [math.CO]. Discrete Math. 310 (2010), no. 24, 3584-3606.
P. Ossona de Mendez and P. Rosenstiehl, Transitivity and connectivity of permutations, Combinatorica, 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).
Vincent Pilaud, Brick polytopes, lattice quotients, and Hopf algebras, arXiv:1505.07665 [math.CO], 2015.
S. Poirier and C. Reutenauer, Algèbres Hopf de tableaux, Ann. Sci. Math. Quebec 19 (95), no. 1, 79-90.
N. Reading Noncrossing partitions and the shard intersection order. J. Algebraic Combin. 33 (2011), no. 4. arXiv preprint arXiv:0909.3288, [math.CO], 2009.
Herman P. Robinson, Letter to N. J. A. Sloane, Nov 19 1973.
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, Space-efficient generation of nonisomorphic maps and hypermaps, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.3.
Marcel Wienöbst, Max Bannach, and Maciej Liśkiewicz, Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications, arXiv:2205.02654 [cs.LG], 2022.
Jun Yan, Results on pattern avoidance in parking functions, arXiv:2404.07958 [math.CO], 2024. See p. 7.

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

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

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

{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 */

{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 */

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

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

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

A357368 Triangle read by rows. Convolution triangle of the prime indicator sequence A089026.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 3, 4, 1, 0, 1, 10, 6, 1, 0, 5, 14, 21, 8, 1, 0, 1, 23, 47, 36, 10, 1, 0, 7, 28, 90, 108, 55, 12, 1, 0, 1, 49, 147, 258, 205, 78, 14, 1, 0, 1, 46, 249, 520, 595, 346, 105, 16, 1, 0, 1, 75, 360, 978, 1437, 1185, 539, 136, 18, 1

Offset: 0

Peter Luschny, Oct 03 2022

To clarify our terminology: We say T is the convolution triangle of a (or T is the partition transform of a), if a is a sequence of integers defined for n >= 1, and the transformation, as defined by the Maple function below, applied to a, returns T. In the generated lower triangular matrix T, i.e., in the convolution triangle of a, T(n, 1) = a(n) for n >= 1.
For instance, let a(n) = Bell(n), then we call A357583 the convolution triangle of the Bell numbers, but not A205574, which is also called the "Bell convolution triangle" in the comments but leads to a different triangle. Similarly, if a(n) = n!, then A090238 is the convolution triangle of the factorial numbers, not A084938. Third example: A128899 is the convolution triangle of the Catalan numbers in our setup, not A059365. More generally, we recommend that when computing the transform of a 0-based sequence to use only the terms for n >= 1 and not to shift the sequence.
Note that T is (0, 0)-based and the first column of a convolution triangle always is 1, 0, 0, 0, ... and the main diagonal is 1, 1, 1, 1, ... if a(1) = 1. The (1, 1)-based subtriangle of a genuine convolution triangle, i.e., a convolution triangle without column 0 and row 0, is often used in place of the convolution triangle but does not fit well into some applications of the convolution triangles.

			Triangle T(n, k) starts:
[0] 1;
[1] 0, 1;
[2] 0, 2,  1;
[3] 0, 3,  4,   1;
[4] 0, 1, 10,   6,   1;
[5] 0, 5, 14,  21,   8,   1;
[6] 0, 1, 23,  47,  36,  10,   1;
[7] 0, 7, 28,  90, 108,  55,  12,   1;
[8] 0, 1, 49, 147, 258, 205,  78,  14,  1;
[9] 0, 1, 46, 249, 520, 595, 346, 105, 16, 1;

Donald E. Knuth, Convolution polynomials, arXiv:math/9207221 [math.CA]; Mathematica J. 2.1 (1992), no. 4, 67-78.
Peter Luschny, The P-transform.
Cormac O'Sullivan, De Moivre and Bell polynomials, arXiv:2203.02868 [math.CO], 2022.

Cf. A089026, A340991, A357588.

PMatrix := proc(dim, a) local n, k, m, g, M, A;
   if n = 0 then return [1] fi;
   A := [seq(a(i), i = 1..dim-1)];
   M := Matrix(dim, shape=triangular[lower]); M[1, 1] := 1;
   for m from 2 to dim do
       M[m, m] := M[m - 1, m - 1] * A[1];
       for k from m-1 by -1 to 2 do
           M[m, k] := add(A[i]*M[m-i, k-1], i = 1..m-k+1)
od od; M end:
a := n -> if isprime(n) then n else 1 fi: PMatrix(10, a);
# Alternatively, as the coefficients of row polynomials:
P := proc(n, x, a) option remember; ifelse(n = 0, 1,
    x*add(a(n - k)*P(k, x, a), k = 0..n-1)) end:
Pcoeffs := proc(n, a) seq(coeff(P(n, x, a), x, k), k=0..n) end:
seq(Pcoeffs(n, a), n = 0..9);
# Alternatively, term by term:
T := proc(n, k, a) option remember; # Alois P. Heinz style
    `if`(k=0, `if`(n=0, 1, 0), `if`(k=1, `if`(n=0, 0, a(n)),
    (q->add(T(j, q, a)*T(n-j, k-q, a), j=0..n))(iquo(k, 2)))) end:
seq(seq(T(n, k, a), k=0..n), n=0..9);

PMatrix[dim_, a_] := Module[{n, k, m, g, M, A}, If[n == 0, Return[1]]; A = Array[a, dim-1]; M = Array[0&, {dim, dim}]; M[[1, 1]] = 1; For[m = 2, m <= dim, m++, M[[m, m]] = M[[m-1, m-1]]*A[[1]]; For[k = m-1, k >= 2, k--, M[[m, k]] = Sum[A[[i]]*M[[m-i, k-1]], {i, 1, m-k+1}]]]; M];
a[n_] :=  If[PrimeQ[n], n, 1];
nmax = 10;
PM = PMatrix[nmax+1, a];
T[n_, k_] := PM[[n+1, k+1]];
Table[T[n, k], {n, 0, nmax}, {k, 0, n}] // Flatten (* Jean-François Alcover, Oct 21 2022 *)

def ConvTriangle(dim: int, a) -> list[list[int]]:
    if callable(a): # Cache the input sequence.
        A = [a(i) for i in range(1, dim)]
    else:
        A = a
    print("In:", A)
    C = [[0 for k in range(m + 1)] for m in range(dim)]
    C[0][0] = 1
    for m in range(1, dim):
        C[m][m] = C[m - 1][m - 1] * A[0]
        for k in range(m - 1, 0, -1):
            C[m][k] = sum(A[i] * C[m - i - 1][k - 1] for i in range(m - k + 1))
    return C
from sympy import isprime, flatten
def a(n): return n if isprime(n) else 1
print(flatten(ConvTriangle(10, a)))

A051296 INVERT transform of factorial numbers.

Original entry on oeis.org

1, 1, 3, 11, 47, 231, 1303, 8431, 62391, 524495, 4960775, 52223775, 605595319, 7664578639, 105046841127, 1548880173119, 24434511267863, 410503693136559, 7315133279097607, 137787834979031839, 2734998201208351479, 57053644562104430735, 1247772806059088954855

Offset: 0

Leroy Quet

a(n) = Sum[ a1!a2!...ak! ] where (a1,a2,...,ak) ranges over all compositions of n. a(n) = number of trees on [0,n] rooted at 0, consisting entirely of filaments and such that the non-root labels on each filament, when arranged in order, form an interval of integers. A filament is a maximal path (directed away from the root) whose interior vertices all have outdegree 1 and which terminates at a leaf. For example with n=3, a(n) = 11 counts all n^(n-2) = 16 trees on [0,3] except the 3 trees {0->1, 1->2, 1->3}, {0->2, 2->1, 2->3}, {0->3, 3->1, 3->2} (they fail the all-filaments test) and the 2 trees {0->2, 0->3, 3->1}, {0->2, 0->1, 1->3} (they fail the interval-of-integers test). - David Callan, Oct 24 2004
a(n) is the number of lists of "unlabeled" permutations whose total length is n. "Unlabeled" means each permutation is on an initial segment of the positive integers (cf. A090238). Example: with dashes separating permutations, a(3) = 11 counts 123, 132, 213, 231, 312, 321, 1-12, 1-21, 12-1, 21-1, 1-1-1. - David Callan, Sep 20 2007
Number of compositions of n where there are k! sorts of part k. - Joerg Arndt, Aug 04 2014

			a(4) = 47 = 1*24 + 1*6 + 3*2 + 11*1.
a(4) = 47, the upper left term of M^4.

L. Comtet, Advanced Combinatorics, Reidel, 1974.

Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..440 (first 200 terms from Alois P. Heinz)
Jean-Paul Bultel, Ali Chouria, Jean-Gabriel Luque, and Olivier Mallet, Word symmetric functions and the Redfield-Polya theorem, hal-00793788, 2013.
Louis Comtet, Sur les coefficients de l'inverse de la série formelle Sum n! t^n, Comptes Rend. Acad. Sci. Paris, A 275 (1972), 569-572.
Richard Ehrenborg, Gábor Hetyei, and Margaret Readdy, Catalan-Spitzer permutations, arXiv:2310.06288 [math.CO], 2023. See p. 20.
Richard J. Martin, and Michael J. Kearney, Integral representation of certain combinatorial recurrences, Combinatorica: 35:3 (2015), 309-315.
Jun Yan, Results on pattern avoidance in parking functions, arXiv:2404.07958 [math.CO], 2024. See p. 7.

Cf. A051295, row sums of A090238.

Cf. A000142, A292778.

a:= proc(n) option remember; `if`(n<1, 1,
      add(a(n-i)*factorial(i), i=1..n))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jul 28 2015

CoefficientList[Series[Sum[Sum[k!*x^k, {k, 1, 20}]^n, {n, 0, 20}], {x, 0, 20}], x] (* Geoffrey Critzer, Mar 22 2009 *)

h = lambda x: 1/(1-x*hypergeometric((1, 2), (), x))
taylor(h(x),x,0,22).list() # Peter Luschny, Jul 28 2015

def A051296_list(len):
    R, C = [1], [1]+[0]*(len-1)
    for n in (1..len-1):
        for k in range(n, 0, -1):
            C[k] = C[k-1] * k
        C[0] = sum(C[k] for k in (1..n))
        R.append(C[0])
    return R
print(A051296_list(23)) # Peter Luschny, Feb 21 2016

G.f.: 1/(1-Sum_{n>=1} n!*x^n).
a(0) = 1; a(n) = Sum_{k=1..n} a(n-k)*k! for n>0.
a(n) = Sum_{k>=0} A090238(n, k). - Philippe Deléham, Feb 05 2004
From Gary W. Adamson, Sep 26 2011: (Start)
a(n) is the upper left term of M^n, M = an infinite square production matrix as follows:
1, 1, 0, 0, 0, 0, ...
2, 0, 2, 0, 0, 0, ...
3, 0, 0, 3, 0, 0, ...
4, 0, 0, 0, 4, 0, ...
5, 0, 0, 0, 0, 5, ...
... (End)
G.f.: 1 + x/(G(0) - 2*x) where G(k) = 1 + (k+1)*x - x*(k+2)/G(k+1); (recursively defined continued fraction). - Sergei N. Gladkovskii, Dec 26 2012
a(n) ~ n! * (1 + 2/n + 7/n^2 + 35/n^3 + 216/n^4 + 1575/n^5 + 13243/n^6 + 126508/n^7 + 1359437/n^8 + 16312915/n^9 + 217277446/n^10), for coefficients see A260530. - Vaclav Kotesovec, Jul 28 2015
From Peter Bala, May 26 2017: (Start)
G.f. as an S-fraction: A(x) = 1/(1 - x/(1 - 2*x/(1 - x/(1 - 3*x/(1 - 2*x/(1 - 4*x/(1 - 3*x/(1 - n*x/(1 - (n - 1)*x/(1 - ...)))))))))). Cf. S-fraction for the o.g.f. of A000142.
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)

Entry revised by David Callan, Sep 20 2007

cp's OEIS Frontend

A084938 Triangle read by rows: T(n,k) = Sum_{j>=0} j!*T(n-j-1, k-1) for n >= 0, k >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Sage

Formula

Extensions

A357368 Triangle read by rows. Convolution triangle of the prime indicator sequence A089026.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

A051296 INVERT transform of factorial numbers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Sage

Formula

Extensions

A090753 Coefficients of power series A(x) such that n-th term of A(x)^n = n!*n*x^(n-1), for n>0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

Formula

A059369 Triangle of numbers T(n,k) = T(n-1,k-1) + ((n+k-1)/k)*T(n-1,k), n >= 1, 1 <= k <= n, with T(n,1) = n!, T(n,n) = 1; read from right to left.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

A090753 Coefficients of power series A(x) such that n-th term of A(x)^n = n!nx^(n-1), for n>0.

A090386 Fifth diagonal (m=4) of triangle A084938; a(n) = A084938(n+4,n) = (n^4 + 18n^3 + 131n^2 + 426*n)/24.

A090391 a(n) = n(n^4 + 30n^3 + 395n^2 + 2910n + 11064)/120.

A090392 Seventh diagonal (m=6) of triangle A084938; a(n) = A084938(n+6,n) = (n^6 + 45n^5 + 925n^4 + 11475n^3 + 92314n^2 + 413640*n)/720.

A090393 Eighth diagonal (m=7) of triangle A084938; a(n) = A084938(n+7,n) = (n^7 + 63n^6 + 1855n^5 + 34125n^4 + 438424n^3 + 3980172n^2 + 20946960n)/5040.