cp's OEIS Frontend

a(n) is also the number of n X n symmetric permutation matrices.

a(n) is also the number of matchings (Hosoya index) in the complete graph K(n). - Ola Veshta (olaveshta(AT)my-deja.com), Mar 25 2001

a(n) is also the number of independent vertex sets and vertex covers in the n-triangular graph. - Eric W. Weisstein, May 22 2017

Equivalently, this is the number of graphs on n labeled nodes with degrees at most 1. - Don Knuth, Mar 31 2008

a(n) is also the sum of the degrees of the irreducible representations of the symmetric group S_n. - Avi Peretz (njk(AT)netvision.net.il), Apr 01 2001

a(n) is the number of partitions of a set of n distinguishable elements into sets of size 1 and 2. - Karol A. Penson, Apr 22 2003

Number of tableaux on the edges of the star graph of order n, S_n (sometimes T_n). - Roberto E. Martinez II, Jan 09 2002

The Hankel transform of this sequence is A000178 (superfactorials). Sequence is also binomial transform of the sequence 1, 0, 1, 0, 3, 0, 15, 0, 105, 0, 945, ... (A001147 with interpolated zeros). - Philippe Deléham, Jun 10 2005

Row sums of the exponential Riordan array (e^(x^2/2),x). - Paul Barry, Jan 12 2006

a(n) is the number of nonnegative lattice paths of upsteps U = (1,1) and downsteps D = (1,-1) that start at the origin and end on the vertical line x = n in which each downstep (if any) is marked with an integer between 1 and the height of its initial vertex above the x-axis. For example, with the required integer immediately preceding each downstep, a(3) = 4 counts UUU, UU1D, UU2D, U1DU. - David Callan, Mar 07 2006

Equals row sums of triangle A152736 starting with offset 1. - Gary W. Adamson, Dec 12 2008

Proof of the recurrence relation a(n) = a(n-1) + (n-1)*a(n-2): number of involutions of [n] containing n as a fixed point is a(n-1); number of involutions of [n] containing n in some cycle (j, n), where 1 <= j <= n-1, is (n-1) times the number of involutions of [n] containing the cycle (n-1 n) = (n-1)*a(n-2). - Emeric Deutsch, Jun 08 2009

Number of ballot sequences (or lattice permutations) of length n. A ballot sequence B is a string such that, for all prefixes P of B, h(i) >= h(j) for i < j, where h(x) is the number of times x appears in P. For example, the ballot sequences of length 4 are 1111, 1112, 1121, 1122, 1123, 1211, 1212, 1213, 1231, and 1234. The string 1221 does not appear in the list because in the 3-prefix 122 there are two 2's but only one 1. (Cf. p. 176 of Bruce E. Sagan: "The Symmetric Group"). - Joerg Arndt, Jun 28 2009

Number of standard Young tableaux of size n; the ballot sequences are obtained as a length-n vector v where v_k is the (number of the) row in which the number r occurs in the tableaux. - Joerg Arndt, Jul 29 2012

Number of factorial numbers of length n-1 with no adjacent nonzero digits. For example the 10 such numbers (in rising factorial radix) of length 3 are 000, 001, 002, 003, 010, 020, 100, 101, 102, and 103. - Joerg Arndt, Nov 11 2012

Also called restricted Stirling numbers of the second kind (see Mezo). - N. J. A. Sloane, Nov 27 2013

a(n) is the number of permutations of [n] that avoid the consecutive patterns 123 and 132. Proof. Write a self-inverse permutation in standard cycle form: smallest entry in each cycle in first position, first entries decreasing. For example, (6,7)(3,4)(2)(1,5) is in standard cycle form. Then erase parentheses. This is a bijection to the permutations that avoid consecutive 123 and 132 patterns. - David Callan, Aug 27 2014

Getu (1991) says these numbers are also known as "telephone numbers". - N. J. A. Sloane, Nov 23 2015

a(n) is the number of elements x in the symmetric group S_n such that x^2 = e where e is the identity. - Jianing Song, Aug 22 2018 [Edited on Jul 24 2025]

a(n) is the number of congruence orbits of upper-triangular n X n matrices on skew-symmetric matrices, or the number of Borel orbits in largest sect of the type DIII symmetric space SO_{2n}(C)/GL_n(C). Involutions can also be thought of as fixed-point-free partial involutions. See [Bingham and Ugurlu] link. - Aram Bingham, Feb 08 2020

From Thomas Anton, Apr 20 2020: (Start)

Apparently a(n) = b*c where b is odd iff a(n+b) (when a(n) is defined) is divisible by b.

Apparently a(n) = 2^(f(n mod 4)+floor(n/4))*q where f:{0,1,2,3}->{0,1,2} is given by f(0),f(1)=0, f(2)=1 and f(3)=2 and q is odd. (End)

From Iosif Pinelis, Mar 12 2021: (Start)

a(n) is the n-th initial moment of the normal distribution with mean 1 and variance 1. This follows because the moment generating function of that distribution is the e.g.f. of the sequence of the a(n)'s.

The recurrence a(n) = a(n-1) + (n-1)*a(n-2) also follows, by writing E(Z+1)^n=EZ(Z+1)^(n-1)+E(Z+1)^(n-1), where Z is a standard normal random variable, and then taking the first of the latter two integrals by parts. (End)

First differs from A212167 in lacking 1080, with prime indices {1,1,1,2,2,2,3}.

First differs from A335433 in lacking 72 (see example).

A squarefree semiprime (A006881) is a product of any two distinct prime numbers.

The following are equivalent characteristics for any positive integer n:

(1) the prime factors of n can be partitioned into distinct singletons and strict pairs, i.e., into a set of half-loops and edges;

(2) n can be factored into distinct primes or squarefree semiprimes;

(3) the prime signature of n is half-loop-graphical.

Entries are Bessel polynomial coefficients. Row sums are A000085. Diagonal sums are A122849. Inverse is A122850. Product of A007318 and A122848 gives A100862.

T(n,k) is the number of self-inverse permutations of {1,2,...,n} having exactly k cycles. - Geoffrey Critzer, May 08 2012

Bessel numbers of the second kind. For relations to the Hermite polynomials and the Catalan (A033184 and A009766) and Fibonacci (A011973, A098925, and A092865) matrices, see Yang and Qiao. - Tom Copeland, Dec 18 2013.

Also the inverse Bell transform of the double factorial of odd numbers Product_{k= 0..n-1} (2*k+1) (A001147). For the definition of the Bell transform see A264428 and for cross-references A265604. - Peter Luschny, Dec 31 2015

I call loops of degree one half-loops, so these are half-loop-graphs or graphs with half-loops. - Gus Wiseman, Dec 31 2020

The dual of a multiset partition has, for each vertex, one part consisting of the indices (or positions) of the parts containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,2}} is {{1},{1,2,2}}. This sequence counts non-isomorphic multiset partitions with no singletons whose dual also has no singletons.

It doesn't matter for this sequence whether we use loops such as {x,x} or half-loops such as {x}.

A squarefree semiprime (A006881) is a product of any two distinct prime numbers.

The following are equivalent characteristics for any positive integer n:

(1) the prime factors of n can be partitioned into distinct singletons or strict pairs, i.e., into a set of half-loops and edges;

(2) n can be factored into distinct primes or squarefree semiprimes.

It doesn't matter for this sequence whether we use loops such as {x,x} or half-loops such as {x}.