cp's OEIS Frontend

a(n) counts permutations of [1,...,n+1] having no substring [k,k+1]. - Len Smiley, Oct 13 2001

Also, for n > 0, determinant of the tridiagonal n X n matrix M such that M(i,i)=i and for i=1..n-1, M(i,i+1)=-1, M(i+1,i)=i. - Mario Catalani (mario.catalani(AT)unito.it), Feb 04 2003

Also, for n > 0, maximal permanent of a nonsingular n X n (0,1)-matrix, which is achieved by the matrix with just n-1 0's, all on main diagonal. [For proof, see next entry.] - W. Edwin Clark, Oct 28 2003

Proof from Richard Brualdi and W. Edwin Clark, Nov 15 2003: Let n >= 4. Take an n X n (0,1)-matrix A which is nonsingular. It has t >= n-1, 0's, otherwise there will be two rows of all 1's. Let B be the matrix obtained from A by replacing t-(n-1) of A's 0's with 1's. Let D be the matrix with all 1's except for 0's in the first n-1 positions on the diagonal. This matrix is easily seen to be non-singular. Now we have per(A) < = per(B) < = per (D), where the first inequality follows since replacing 0's by 1's cannot decrease the permanent and the second from Corollary 4.4 in the Brualdi et al. reference, which shows that per(D) is the maximum permanent of ANY n X n matrix with n -1 0's. Corollary 4.4 requires n >= 4. a(n) for n < 4 can be computed directly.

With offset 1, permanent of (0,1)-matrix of size n X (n+d) with d=1 and n zeros not on a line. This is a special case of Theorem 2.3 of Seok-Zun Song et al., Extremes of permanents of (0,1)-matrices, pp. 201-202. - Jaap Spies, Dec 12 2003

Number of fixed-point-free permutations of n+2 that begin with a 2; e.g., for 1234, we have 2143, 2341, 2413, so a(2)=3. Also number of permutations of 2..n+2 that have no agreements with 1..n+1. E.g., for 123 against permutations of 234, we have 234, 342 and 432. Compare A047920. - Jon Perry, Jan 23 2004. [This can be proved by the standard argument establishing that d(n+2) = (n+1)(d(n+1)+d(n)) for derangements A000166 (n+1 choices of where 1 goes, then either 1 is in a transposition, or in a cycle of length at least 3, etc.). - D. G. Rogers, Aug 28 2006]

Stirling transform of A006252(n+1)=[1,1,2,4,14,38,...] is a(n)=[1,3,11,53,309,...]. - Michael Somos, Mar 04 2004

a(n+1) is the sequence of numerators of the self-convergents to 1/(e-2); see A096654. - Clark Kimberling, Jul 01 2004

Euler's interpretation was "fixedpoint-free permutations beginning with 2" and he listed the terms up to 148329 (although he was blind at the time). - Don Knuth, Jan 25 2007

Equals lim_{k->infinity} A153869^k. - Gary W. Adamson, Jan 03 2009

Hankel transform is A059332. - Paul Barry, Apr 22 2009

This sequence appears in the analysis of Euler's divergent series 1 - 1! + 2! - 3! + 4! ... by Lacroix, see Hardy. For information about this and related divergent series see A163940. - Johannes W. Meijer, Oct 16 2009

a(n), n >= 1, enumerates also the ways to distribute n beads, labeled differently from 1 to n, over a set of (unordered) necklaces, excluding necklaces with exactly one bead, and one open cord allowed to have any number of beads. Each beadless necklace as well as the beadless cord contributes a factor 1 in the counting, e.g., a(0):=1*1=1. There are k! possibilities for the cord with k>=0 beads, which means that the two ends of the cord should be considered as fixed, in short: a fixed cord. This produces for a(n) the exponential (aka binomial) convolution of the sequences {n!=A000142(n)} and the subfactorials {A000166(n)}.

See the formula below. Alternatively, the e.g.f. for this problem is seen to be (exp(-x)/(1-x))*(1/(1-x)), namely the product of the e.g.f.s for the subfactorials (from the unordered necklace problem, without necklaces with exactly one bead) and the factorials (from the fixed cord problem). Therefore the recurrence with inputs holds also. a(0):=1. This comment derives from a family of recurrences found by Malin Sjodahl for a combinatorial problem for certain quark and gluon diagrams (Feb 27 2010). - Wolfdieter Lang, Jun 02 2010

a(n) = (n-1)a(n-1) + (n-2)a(n-2) gives the same sequence offset by a 1. - Jon Perry, Sep 20 2012

Also, number of reduced 2 X (n+2) Latin rectangles. - A.H.M. Smeets, Nov 03 2013

Second column of Euler's difference table (second diagonal in example of A068106). - Enrique Navarrete, Dec 13 2016

If we partition the permutations of [n+2] in A000166 according to their starting digit, we will get (n+1) equinumerous classes each of size a(n) (the class starting with the digit 1 is empty since no derangement starts with 1). Hence, A000166(n+2)=(n+1)*a(n), so a(n) is the size of each nonempty class of permutations of [n+2] in A000166. For example, for n=3 we have 44=4*11 (see link). - Enrique Navarrete, Jan 11 2017

For n >= 1, the number of circular permutations (in cycle notation) on [n+2] that avoid substrings (j,j+2), 1 <= j <= n. For example, for n=2, the 3 circular permutations in S4 that avoid substrings {13,24} are (1234),(1423),(1432). Note that each of these circular permutations represent 4 permutations in one-line notation (see link 2017). - Enrique Navarrete, Feb 15 2017

The sequence a(n) taken modulo a positive integer k is periodic with exact period dividing k when k is even and dividing 2*k when k is odd. This follows from the congruence a(n+k) = (-1)^k*a(n) (mod k) holding for all n and k, which in turn is easily proved by induction making use of the given recurrences. - Peter Bala, Nov 21 2017

Number of permutations of [n] where the k-th fixed points are k-colored and all other points are unicolored. - Alois P. Heinz, Apr 28 2025

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

a(n) is the hook product of the shape (n, 1). - Emeric Deutsch, May 13 2004

From Jaume Oliver Lafont, Dec 01 2009: (Start)

(1+(x-1)*exp(x))/x = Sum_{k >= 1} x^k/a(k).

Setting x = 1 yields Sum_{k >= 1} 1/a(k) = 1. [Jolley eq 302] (End)

With regard to the comment by Jaume Oliver Lafont: P(n) = 1/a(n) is a probability distribution, with all values given as unit fractions. This distribution is connected to the Irwin-Hall distribution: Consider successively drawn random numbers, uniformly distributed in [0,1]. 1/a(n) is the probability for the sum of the random numbers exceeding 1 exactly with the (n+1)-th summand. P(n) has mean e-1 and variance 3e-e^2. From this we get e as the expected number of summands. - Manfred Boergens, May 20 2024

For n >= 2, a(n) is the size of the largest conjugacy class of the symmetric group on n + 1 letters. Equivalently, the maximum entry in each row of A036039. - Geoffrey Critzer, May 19 2013

In factorial base representation (A007623) the terms are written as: 10, 11, 110, 1100, 11000, 110000, ... From a(2) = 3 = "11" onward each term begins always with two 1's, followed by n-2 zeros. - Antti Karttunen, Sep 24 2016

e is approximately a(n)/A000255(n-1) for large n. - Dale Gerdemann, Jul 26 2019

a(n) is the number of permutations of [n+1] in which all the elements of [n] are cycle-mates, that is, 1,..,n are all in the same cycle. This result is readily shown after noting that the elements of [n] can be members of a n-cycle or an (n+1)-cycle. Hence a(n)=(n-1)!+n!. See an example below. - Dennis P. Walsh, May 24 2020

If the initial values are changed to a(0)=1 and a(1)=2, the resulting sequence (p(0),p(1),...)=(1,2,5,19,....) is essentially A089126. Writing A096655 as (q(0),q(1),...), the quotients p(n)/q(n) are the self-convergents to the number 1.719525... whose self-continued fraction is (1,1,2,3,5,...)=A000045. For definitions, see A096654. Now writing A096655 as (p(0),p(1),...) and A096656 as (q(0),q(1),...), the quotients p(n)/q(n) are the self-convergents to the number 1.389805... whose self-continued fraction is (1,2,3,5,...).

This is the sequence of denominators of self-convergents to the number 1.40861... (see A233590) whose self-continued fraction is (1,2,4,8,16,...). See A096657 for numerators and A096654 for definitions.

This is the sequence of denominators of self-convergents to the number 1.389805... whose self-continued fraction is (1,2,3,5,8,...) (Fibonacci numbers). See A096655 for numerators and A096654 for definitions.

This is the sequence of numerators of self-convergents to the number 1.40861... whose self-continued fraction is (1,2,4,8,16,...)=A000079. See A096658 for denominators and A096654 for definitions.

A relaxed compacted binary tree of size n is a directed acyclic graph consisting of a binary tree with n internal nodes, one leaf, and at most n pointers. It is constructed from a binary tree of size n, where the first leaf in a post-order traversal is kept and all other leaves are replaced by pointers. These links may point to any node that has already been visited by the post-order traversal. It is called simple if for nodes with two pointers both point to the same node. The right height is the maximal number of right-edges (or right children) on all paths from the root to any leaf after deleting all pointers. See the Wallner link.

a(n) is one of two "basis" sequences for sequences of the form a(0)=a, a(1)=b, a(n) = n*a(n-1) + (n-1)*a(n-2), the second basis sequence being A096654 (with 0 appended as a(0)). The sum of these sequences is listed as A000255. - Gary Detlefs, Dec 11 2018