cp's OEIS Frontend

Total number of permutations of all subsets of an n-set.

Also the number of one-to-one sequences that can be formed from n distinct objects.

Old name "Total number of permutations of a set with n elements", or the same with the word "arrangements", both sound too much like A000142.

Related to number of operations of addition and multiplication to evaluate a determinant of order n by cofactor expansion - see A026243.

a(n) is also the number of paths (without loops) in the complete graph on n+2 vertices starting at one vertex v1 and ending at another v2. Example: when n=2 there are 5 paths in the complete graph with 4 vertices starting at the vertex 1 and ending at the vertex 2: (12),(132),(142),(1342),(1432) so a(2) = 5. - Avi Peretz (njk(AT)netvision.net.il), Feb 23 2001; comment corrected by Jonathan Coxhead, Mar 21 2003

Also row sums of Table A008279, which can be generated by taking the derivatives of x^k. For example, for y = 1*x^3, y' = 3x^2, y" = 6x, y'''= 6 so a(4) = 1 + 3 + 6 + 6 = 16. - Alford Arnold, Dec 15 1999

a(n) is the permanent of the n X n matrix with 2s on the diagonal and 1s elsewhere. - Yuval Dekel, Nov 01 2003

(A000166 + this_sequence)/2 = A009179, (A000166 - this_sequence)/2 = A009628.

Stirling transform of A006252(n-1) = [1,1,1,2,4,14,38,...] is a(n-1) = [1,2,5,16,65,...]. - Michael Somos, Mar 04 2004

Number of {12,12*,21*}- and {12,12*,2*1}-avoiding signed permutations in the hyperoctahedral group.

a(n) = b such that Integral_{x=0..1} x^n*exp(-x) dx = a-b*exp(-1). - Sébastien Dumortier, Mar 05 2005

a(n) is the number of permutations on [n+1] whose left-to-right record lows all occur at the start. Example: a(2) counts all permutations on [3] except 231 (the last entry is a record low but its predecessor is not). - David Callan, Jul 20 2005

a(n) is the number of permutations on [n+1] that avoid the (scattered) pattern 1-2-3|. The vertical bar means the "3" must occur at the end of the permutation. For example, 21354 is not counted by a(4): 234 is an offending subpermutation. - David Callan, Nov 02 2005

Number of deco polyominoes of height n+1 having no reentrant corners along the lower contour (i.e., no vertical step that is followed by a horizontal step). In other words, a(n)=A121579(n+1,0). A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column. Example: a(1)=2 because the only deco polyominoes of height 2 are the vertical and horizontal dominoes, having no reentrant corners along their lower contours. - Emeric Deutsch, Aug 16 2006

Unreduced numerators of partial sums of the Taylor series for e. - Jonathan Sondow, Aug 18 2006

a(n) is the number of permutations on [n+1] (written in one-line notation) for which the subsequence beginning at 1 is increasing. Example: a(2)=5 counts 123, 213, 231, 312, 321. - David Callan, Oct 06 2006

a(n) is the number of permutations (written in one-line notation) on the set [n + k], k >= 1, for which the subsequence beginning at 1,2,...,k is increasing. Example: n = 2, k = 2. a(2) = 5 counts 1234, 3124, 3412, 4123, 4312. - Peter Bala, Jul 29 2014

a(n) and (1,-2,3,-4,5,-6,7,...) form a reciprocal pair under the list partition transform and associated operations described in A133314. - Tom Copeland, Nov 01 2007

Consider the subsets of the set {1,2,3,...,n} formed by the first n integers. E.g., for n = 3 we have {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}. Let the variable sbst denote a subset. For each subset sbst we determine its number of parts, that is nprts(sbst). The sum over all possible subsets is written as Sum_{sbst=subsets}. Then a(n) = Sum_{sbst=subsets} nprts(sbst)!. E.g., for n = 3 we have 1!+1!+1!+1!+2!+2!+2!+3!=16. - Thomas Wieder, Jun 17 2006

Equals row sums of triangle A158359(unsigned). - Gary W. Adamson, Mar 17 2009

Equals eigensequence of triangle A158821. - Gary W. Adamson, Mar 30 2009

For positive n, equals 1/BarnesG(n+1) times the determinant of the n X n matrix whose (i,j)-coefficient is the (i+j)th Bell number. - John M. Campbell, Oct 03 2011

a(n) is the number of n X n binary matrices with i) at most one 1 in each row and column and ii) the subset of rows that contain a 1 must also be the columns that contain a 1. Cf. A002720 where restriction ii is removed. - Geoffrey Critzer, Dec 20 2011

Number of restricted growth strings (RGS) [d(1),d(2),...,d(n)] such that d(k) <= k and d(k) <= 1 + (number of nonzero digits in prefix). The positions of nonzero digits determine the subset, and their values (decreased by 1) are the (left) inversion table (a rising factorial number) for the permutation, see example. - Joerg Arndt, Dec 09 2012

Number of a restricted growth strings (RGS) [d(0), d(1), d(2), ..., d(n)] where d(k) >= 0 and d(k) <= 1 + chg([d(0), d(1), d(2), ..., d(k-1)]) and chg(.) gives the number of changes of its argument. Replacing the function chg(.) by a function asc(.) that counts the ascents in the prefix gives A022493 (ascent sequences). - Joerg Arndt, May 10 2013

The sequence t(n) = number of i <= n such that floor(e*i!) is a square is mentioned in the abstract of Luca & Shparlinski. The values are t(n) = 0 for 0 <= n <= 2 and t(n) = 1 for at least 3 <= n <= 300. - R. J. Mathar, Jan 16 2014

a(n) = p(n,1) = q(n,1), where p and q are polynomials defined at A248664 and A248669. - Clark Kimberling, Oct 11 2014

a(n) is the number of ways at most n people can queue up at a (slow) ticket counter when one or more of the people may choose not to queue up. Note that there are C(n,k) sets of k people who quene up and k! ways to queue up. Since k can run from 0 to n, a(n) = Sum_{k=0..n} n!/(n-k)! = Sum_{k=0..n} n!/k!. For example, if n=3 and the people are A(dam), B(eth), and C(arl), a(3)=16 since there are 16 possible lineups: ABC, ACB, BAC, BCA, CAB, CBA, AB, BA, AC, CA, BC, CB, A, B, C, and empty queue. - Dennis P. Walsh, Oct 02 2015

As the row sums of A008279, Motzkin uses the abbreviated notation $n_<^\Sigma$ for a(n).

The piecewise polynomial function f defined by f(x) = a(n)*x^n/n! on each interval [ 1-1/a(n), 1-1/a(n+1) ) is continuous on [0,1) and lim_{x->1} f(x) = e. - Luc Rousseau, Oct 15 2019

a(n) is composite for 3 <= n <= 2015, but a(2016) is prime (or at least a strong pseudoprime): see Johansson link. - Robert Israel, Jul 27 2020 [a(2016) is prime, ECPP certificate generated with CM 0.4.3 and checked by factordb. - Jason H Parker, Jun 15 2025]

In general, sequences of the form a(0)=a, a(n) = n*a(n-1) + k, n>0, will have a closed form of n!*a + floor(n!*(e-1))*k. - Gary Detlefs, Oct 26 2020

From Peter Bala, Apr 03 2022: (Start)

a(2*n) is odd and a(2*n+1) is even. More generally, a(n+k) == a(n) (mod k) for all n and k. It follows that for each positive integer k, the sequence obtained by reducing a(n) modulo k is periodic, with the exact period dividing k. Various divisibility properties of the sequence follow from this; for example, a(5*n+2) == a(5*n+4) == 0 (mod 5), a(25*n+7) == a(25*n+19) == 0 (mod 25) and a(13*n+4) == a(13*n+10)== a(13*n+12) == 0 (mod 13). (End)

Number of possible ranking options on a typical ranked choice voting ballot with n candidates (allowing undervotes). - P. Christopher Staecker, May 05 2024

From Thomas Scheuerle, Dec 28 2024: (Start)

Number of decorated permutations of size n.

Number of Le-diagrams with bounding box semiperimeter n, for n > 0.

By counting over all k = 1..n and n > 0, the number of positroid cells for the totally nonnegative real Grassmannian Gr(k, n), equivalently the number of Grassmann necklaces of type (k, n). (End)

a(n^2) is odd. - Gregory L. Simay, Jun 23 2019

Also the number of compositions of n avoiding the patterns (1,2,1) and (2,1,2). - Gus Wiseman, Jul 07 2020

More than the usual number of terms are displayed in order to show the difference from some closely related sequences.

Also: a(1) = 0; a(n) = Min{x integer | x > a(n-1) and all digits to base 10 are distinct}.

This sequence is finite: a(8877691) = 9876543210 is the last term; a(8877690) = 9876543201. The largest gap between two consecutive terms before a(249999) = 2409653 is 104691, as a(175289) = 1098765, a(175290) = 1203456. - Reinhard Zumkeller, Jun 23 2001

Complement of A109303. - David Wasserman, May 21 2008

For the analogs in other bases b, search for "xenodromes." A001339(b-1) is the number of base b xenodromes for b >= 2. - Rick L. Shepherd, Feb 16 2013

A073531 gives the number of positive n-digit numbers in this sequence. Note that it does not count 0. - T. D. Noe, Jul 09 2013

Can be seen as irregular table whose n-th row holds the n-digit terms; length of row n is then A073531(n) = 9*9!/(10-n)! except for n = 1 where we have 10 terms, unless 0 is considered to belong to a row 0. - M. F. Hasler, Dec 10 2018

Eighteenth- and nineteenth-century combinatorialists call this the number of (nonnull) "variations" of n distinct objects, namely the number of permutations of nonempty subsets of {1,...,n}. Some early references to this sequence are Izquierdo (1659), Caramuel de Lobkowitz (1670), Prestet (1675) and Bernoulli (1713). - Don Knuth, Oct 16 2001, Aug 16 2004

Stirling transform of A006252(n-1) = [0,1,1,2,4,14,38,...] is a(n-1) = [0,1,4,15,64,...]. - Michael Somos, Mar 04 2004

In particular, for n >= 1 a(n) is the number of nonempty sequences with n or fewer terms, each a distinct element of {1,...,n}. - Rick L. Shepherd, Jun 08 2005

a(n) = VarScheme(1,n). See A128195 for the definition of VarScheme(k,n). - Peter Luschny, Feb 26 2007

if s(n) is a sequence of the form s(0)=x, s(n)= n(s(n-1)+k), then s(n)= n!*x + a(n)*k. - Gary Detlefs, Jun 06 2010

Exponential convolution of factorials (A000142) and nonnegative integers (A001477). - Vladimir Reshetnikov, Oct 07 2016

For n > 0, a(n) is the number of maps f: {1,...,n} -> {1,...,n} satisfying equal(x,y) <= equal(f(x),f(y)) for all x,y, where equal(x,y) is n if x and y are equal and min(x,y) if not. Here equal(x,y) is the equality predicate in the n-valued Gödel logic, see e. g. the Wikipedia chapter on many-valued logics. - Mamuka Jibladze, Mar 12 2025

This sequence shares divisibility properties with A000522; each of the primes in A072456 divide only a finite number of terms of this sequence. - T. D. Noe, Jul 07 2005

Sum of the lengths of the first runs in all permutations of [n]. Example: a(3)=10 because the lengths of the first runs in the permutation (123),(13)2,(3)12,(2)13,(23)1 and (3)21 are 3,2,1,1,2 and 1, respectively (first runs are enclosed between parentheses). Number of cells in the last columns of all deco polyominoes of height n. A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column. a(n) = Sum_{k=1..n} k*A092582(n,k). - Emeric Deutsch, Aug 16 2006

Starting with offset 1 = eigensequence of an infinite lower triangular matrix with (1, 2, 3, ...) as the right border, (1, 1, 1, ...) as the left border, and the rest zeros. - Gary W. Adamson, Apr 27 2009

Sums of rows of the triangle in A173333, n > 0. - Reinhard Zumkeller, Feb 19 2010

if s(n) is a sequence defined as s(0) = x, s(n) = n*s(n-1)+k, n > 0 then s(n) = n!*x + a(n)*k. - Gary Detlefs, Feb 20 2010

Number of arrangements of proper subsets of n distinct objects, i.e., arrangements which are not permutations (where the empty set is considered a proper subset of any nonempty set); see example. - Daniel Forgues, Apr 23 2011

For n >= 0, A002627(n+1) is the sequence of sums of Pascal-like triangle with one side 1,1,..., and the other side A000522. - Vladimir Shevelev, Feb 06 2012

a(n) = q(n,1) for n >= 1, where the polynomials q are defined at A248669. - Clark Kimberling, Oct 11 2014

a(n) is the number of quasilinear weak orderings on {1,...,n}. - J. Devillet, Dec 22 2017

A "consecutive ascending pair" in a permutation p_1, p_2, ..., p_n is a pair p_i, p_{i+1} = p_i + 1.

From Emeric Deutsch, May 15 2010: (Start)

The same triangle, but with rows indexed differently, also arises as follows: U(n,k) = number of permutations of [n] having k blocks (1 <= k <= n), where a block of a permutation is a maximal sequence of consecutive integers which appear in consecutive positions. For example, the permutation 5412367 has 4 blocks: 5, 4, 123, and 67.

When seen as coefficients of polynomials with decreasing exponents: evaluations are A001339 (x=2), A081923 (x=3), A081924 (x=4), A087981 (x=-1).

The sum of the entries in row n is n!.

U(n,n) = A000255(n-1) = d(n-1) + d(n), U(n,n-1)=d(n), where d(j)=A000166(j) (derangement numbers). (End)

This is essentially the reversal of the exponential Riordan array [exp(-x)/(1-x)^2,x] (cf. A123513). - Paul Barry, Jun 17 2010

U(n-1, k-2) * n*(n-1)/k = number of permutations of [n] with k elements not fixed by the permutation. - Michael Somos, Aug 19 2018

Also the number of compositions of n matching the pattern (1,2,1) or (2,1,2).

The a-sequence for this Sheffer matrix is A027641(n)/A027642(n) (Bernoulli numbers) and the z-sequence is A130189(n)/ A130190(n). See the W. Lang link.

Take the lower triangular matrix in A049020 and invert it, then read by rows! - N. J. A. Sloane, Feb 07 2009

Exponential Riordan array [exp(x), log(1/(1-x))]. Equal to A007318*A132393. - Paul Barry, Apr 23 2009

A signed version of the triangle appears in [Gessel]. - Peter Bala, Aug 31 2012

T(n,k) is the number of permutations over all subsets of {1,2,...,n} (Cf. A000522) that have exactly k cycles. T(3,2) = 6: We permute the elements of the subsets {1,2}, {1,3}, {2,3}. Each has one permutation with 2 cycles. We permute the elements of {1,2,3} and there are three permutations that have 2 cycles. 3*1 + 1*3 = 6. - Geoffrey Critzer, Feb 24 2013

From Wolfdieter Lang, Jul 28 2017: (Start)

In Chihara's book the row polynomials (with rising powers) are the Charlier polynomials (-1)^n*C^(a)_n(-x), with a = -1, n >= 0. See p. 170, eq. (1.4).

In Ismail's book the present Charlier polynomials are denoted by C_n(-x;a=1) on p. 177, eq. (6.1.25). (End)

The triangle T(n,k) is a representative of the parametric family of triangles T(m,n,k), whose columns are the coefficients of the standard expansion of the function f(x) = (-log(1-x))^(k)*exp(-m*x)/k! for the case m=-1. See A381082. - Igor Victorovich Statsenko, Feb 14 2025

Let b(n) = LPT[ A001147 ] = -A001147(n-1) for n > 0 and 1 for n=0, where LPT represents the action of the list partition transform described in A133314.

Then T(n,k) = binomial(n,k) * b(n-k) .

Form the matrix of polynomials TB(n,k,t) = T(n,k) * t^(n-k) = binomial(n,k) * b(n-k) * t^(n-k) = binomial(n,k) * Pb(n-k,t),

beginning as

1;

-1, 1;

-1*t, -2, 1;

-3*t^2, -3*t, -3, 1;

-15*t^3, -12*t^2, -6*t, -4, 1;

-105*t^4, -75*t^3, -30*t^2, -10*t, -5, 1;

Let Pc(n,t) = LPT(Pb(.,t)).

Then [TB(t)]^(-1) = TC(t) = [ binomial(n,k) * Pc(n-k,t) ] = LPT(TB),

whose first column is

Pc(0,t) = 1

Pc(1,t) = 1

Pc(2,t) = 2 + t

Pc(3,t) = 6 + 6*t + 3*t^2

Pc(4,t) = 24 + 36*t + 30*t^2 + 15*t^3

Pc(5,t) = 120 + 240*t + 270*t^2 + 210*t^3 + 105*t^4.

The coefficients of these polynomials are given by the reverse of A102625 with the highest order coefficients given by A001147 with an additional leading 1.

Note this is not the complete matrix TC. The complete matrix is formed by multiplying along the diagonal of the lower triangular Pascal matrix by these polynomials, embedding trees of coefficients in the matrix.

exp[Pb(.,t)*x] = 1 + [(1-2t*x)^(1/2) - 1] / (t-0) = [1 + a finite diff. of [(1-2t*x)^(1/2)] with step t] = e.g.f. of the first column of TB.

exp[Pc(.,t)*x] = 1 / { 1 + [(1-2t*x)^(1/2) - 1] / t } = 1 / exp[Pb(.,t)*x) = e.g.f. of the first column of TC.

TB(t) and TC(t), being inverse to each other, are the generators of an Abelian group.

TB(0) and TC(0) are generators for a subgroup representing the iterated Laguerre operator described in A132013 and A132014.

Let sb(t,m) and sc(t,m) be the associated sequences under the LPT to TB(t)^m = B(t,m) and TC(t)^m = C(t,m).

Let Esb(t,m) and Esc(t,m) be e.g.f.'s for sb(t,m) and sc(t,m), rB(t,m) and rC(t,m) be the row sums of B(t,m) and C(t,m) and aB(t,m) and aC(t,m) be the alternating row sums.

Then B(t,m) is the inverse of C(t,m), Esb(t,m) is the reciprocal of Esc(t,m) and sb(t,m) and sc(t,m) form a reciprocal pair under the LPT. Similar relations hold among the row sums and the alternating sign row sums and associated quantities.

All the group members have the form B(t,m) * C(u,p) = TB(t)^m * TC(u)^p = [ binomial(n,k) * s(n-k) ]

with associated e.g.f. Es(x) = exp[m * Pb(.,t) * x] * exp[p * Pc(.,u) * x] for the first column of the matrix, with terms s(n), so group multiplication is isomorphic to matrix multiplication and to multiplication of the e.g.f.'s for the associated sequences (see examples).

These results can be extended to other groups of integer-valued arrays by replacing the 2 by any natural number in the expression for exp[Pb(.,t)*x].

More generally,

[ G.f. for M = Product_{i=0..j} B[s(i),m(i)] * C[t(i),n(i)] ]

= exp(u*x) * Product_{i=0..j} { exp[m(i) * Pb(.,s(i)) * x] * exp[n(i) * Pc(.,t(i)) * x] }

= exp(u*x) * Product_{i=0..j} { 1 + [ (1 - 2*s(i)*x)^(1/2) - 1 ] / s(i) }^m(i) / { 1 + [ (1 - 2*t(i)*x)^(1/2) - 1 ] / t(i) }^n(i)

= exp(u*x) * H(x)

[ E.g.f. for M ] = I_o[2*(u*x)^(1/2)] * H(x).

M is an integer-valued matrix for m(i) and n(i) positive integers and s(i) and t(i) integers. To invert M, change B to C in Product for M.

H(x) is the e.g.f. for the first column of M and diagonally multiplying the Pascal matrix by the terms of this column generates M. See examples.

The G.f. for M, i.e., the e.g.f. for the row polynomials of M, implies that the row polynomials form an Appell sequence (see Wikipedia and Mathworld). - Tom Copeland, Dec 03 2013

Diagonals: A000012, A000217; A000012, A002104. - Philippe Deléham, Jun 12 2004

The sequence a(n) = Sum_{k = 0..n} T(n,k)*x^(n-k) is the binomial transform of the sequence b(n) = (n+x-1)! / (x-1)!. - Philippe Deléham, Jun 18 2004