cp's OEIS Frontend

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

n-th row of the triangle = charpoly of an (n-1) X (n-1) matrix with (1,2,3,...) in the diagonal and the rest zeros. - Gary W. Adamson, Mar 19 2009

From Daniel Forgues, Jan 16 2016: (Start)

For n >= 1, the row sums [of either signed or absolute values] are

Sum_{k=1..n} T(n,k) = 0^(n-1),

Sum_{k=1..n} |T(n,k)| = T(n+1,1) = n!. (End)

The moment generating function of the probability density function p(x, m=q, n=1, mu=q) = q^q*x^(q-1)*E(x, q, 1)/(q-1)!, with q >= 1, is M(a, m=q, n=1, mu=q) = Sum_{k=0..q}(A000312(q) / A000142(q-1)) * A008276(q, k) * polylog(k, a) / a^q , see A163931 and A274181. - Johannes W. Meijer, Jun 17 2016

Triangle of coefficients of the polynomial x(x-1)(x-2)...(x-n+1), also denoted as falling factorial (x)n, expanded into decreasing powers of x. - _Ralf Stephan, Dec 11 2016

With offset 1, permanent of (0,1)-matrix of size n X (n+d) with d=2 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

Starting (1, 2, 7, 32, ...) = inverse binomial transform of A001710 starting (1, 3, 12, 60, 360, 2520, ...). - Gary W. Adamson, Dec 25 2008

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

a(n+1)=:b(n), n>=1, enumerates 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 two indistinguishable, ordered, fixed cords, each allowed to have any number of beads. Beadless necklaces as well as beadless cords contribute each a factor 1 in the counting, e.g., b(0):= 1*1 = 1. See A000255 for the description of a fixed cord with beads.

This produces for b(n) the exponential (aka binomial) convolution of the subfactorial sequence {A000166(n)} and {(n+1)!}={A000042(n+1)}. This follows from the general problem with only k indistinguishable, ordered, fixed cords which has e.g.f. 1/(1-x)^k, and the pure necklace problem (no necklaces with one bead allowed) with e.g.f. for the subfactorials. Therefore also the recurrence b(n) = (n+1)*b(n-1) + (n-1)*b(n-2) with b(-1)=0 and b(0)=1 holds.

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) is a function of the subfactorials..sf... A000166(n) a(n) = (n*sf(n+1) - (n+1)*sf(n))/(2*n*(n-1)*(n+1)),n>1, with offset 1. - Gary Detlefs, Nov 06 2010

For even k the sequence a(n) (mod k) is purely periodic with exact period a divisor of k, while for odd k the sequence a(n) (mod k) is purely periodic with exact period a divisor of 2*k. See A047974. - Peter Bala, Dec 04 2017

Or, number of permutations with no fixed points avoiding 213 and 132.

Number of derangements of {1,2,...,n} having ascending runs consisting of consecutive integers. Example: a(4)=6 because we have 234/1, 34/12, 34/2/1, 4/123, 4/3/12, 4/3/2/1, the ascending runs being as indicated. - Emeric Deutsch, Dec 08 2004

Let c be twice the sequence A002450 interlaced with itself (from the second term), i.e., c = 2*(0, 1, 1, 5, 5, 21, 21, 85, 85, 341, 341, ...). Let d be powers of 4 interlaced with the zero sequence: d = (1, 0, 4, 0, 16, 0, 64, 0, 256, 0, ...). Then a(n+1) = c(n) + d(n). - Creighton Dement, May 09 2005

Inverse binomial transform of A094705 (0, 1, 4, 15). - Paul Curtz, Jun 15 2008

Equals row sums of triangle A177993. - Gary W. Adamson, May 16 2010

a(n-1) is also the number of order preserving partial isometries (of an n-chain) of fix 1 (fix of alpha equals the number of fixed points of alpha). - Abdullahi Umar, Dec 28 2010

a(n+1) <= A218553(n) is also the Moore lower bound on the order of a (5,n)-cage. - Jason Kimberley, Oct 31 2011

For n > 0, a(n) is the location of the n-th new number to make a first appearance in A087230. E.g., the 17th number to make its first appearance in A087230 is 18 and this occurs at A087230(43690) and a(17)=43690. - K D Pegrume, Jan 26 2022

Position in A002487 of 2 adjacent terms of A000045. E.g., 3/5 at 10, 5/8 at 26, 8/13 at 42, ... - Ed Pegg Jr, Dec 27 2022

A010843, A000023, A000166, A000142, A000522, A010842, A053486, A053487 are successive binomial transforms with the e.g.f. exp(k*x)/(1-x) and recurrence b(n) = n*b(n-1)+k^n and are related to incomplete gamma functions at k. In this case k=-2, a(n) = n*a(n-1)+(-2)^n = Gamma(n+1,k)*exp(k) = Sum_{i=0..n} (-1)^(n-i)*binomial(n,i)*i^(n-i)*(i+k)^i. - Vladeta Jovovic, Aug 19 2002

a(n) is the permanent of the n X n matrix with -1's on the diagonal and 1's elsewhere. - Philippe Deléham, Dec 15 2003

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

Starting with offset 1 = lim_{k->infinity} M^k, where M = a tridiagonal matrix with (1,0,0,0,...) in the main diagonal, (1,3,5,7,...) in the subdiagonal and (2,4,6,8,...) in the subsubdiagonal. - Gary W. Adamson, Jan 13 2009

a(n) is also the number of (n-1)-dimensional facet derangements for the n-dimensional hypercube. - Elizabeth McMahon, Gary Gordon (mcmahone(AT)lafayette.edu), Jun 29 2009

a(n) is the number of ways to write down each n-permutation and underline some (possibly none or all) of the elements that are not fixed points. a(n) = Sum_{k=0..n} A008290(n,k)*2^(n-k). - Geoffrey Critzer, Dec 15 2012

Type B derangement numbers: the number of fixed point free permutations in the n-th hyperoctahedral group of signed permutations of {1,2,...,n}. See Chow 2006. See A000166 for type A derangement numbers. - Peter Bala, Jan 30 2015

Incomplete Gamma Function at 2, more precisely: a(n) = exp(2)*Gamma(1+n,2).

Let P(A) be the power set of an n-element set A. Then a(n) = the total number of ways to add 0 or more elements of A to each element x of P(A) where the elements to add are not elements of x and order of addition is important. - Ross La Haye, Nov 19 2007

a(n) is the number of ways to split the set {1,2,...,n} into two disjoint subsets S,T with S union T = {1,2,...,n} and linearly order S and then choose a subset of T. - Geoffrey Critzer, Mar 10 2009

Number of deranged matchings of 2n people with partners (of either sex) other than their spouse. 2n objects are initially paired in some way and then are re-paired so that no object is with its original partner (the dancing problem in the article).

Of interest in the "collision problem", where, given a 2-to-1 function f, we are asked for x, y such that f(x)=f(y).

2^n*n!*a(n) = (2n)! b(n) where b(n) are the probabilities that appear in Margolis (2001). One interpretation is in terms of matchings or 1-factors of the complete graph on 2n vertices. The number of these is (2n)!/2^{n}n!. The number of 1-factors being disjoint from (that is, having no edges in common with) a given 1-factor is then a(n); and then b(n) is the probability of picking such a disjoint one factor at random.

Also n!*a(n) = 2^n * c(n) where c(n) = A001499(n). If we define d(n,k) = k(n-1)(d(n-1,k) + d(n-2,k)), with d(0,k) = 1 and d(1,k) = 0, so d(n,1) are the derangement numbers A000166, then a(n) = d(n,2) (cf. A033030, A088991). On the other hand, taking d*(n,k) = d(n,k)/k^{n}, we have d*(n,k) = (n-1)(d*(n-1,k) + d*(n-2,k)/k), with d*(0,k) = 1 and d*(1,k) = 0 and it is easy to see from Bricard's recurrence for c(n) that c(n)/n! satisfies this for k = 2.

A proof that the description in the first comment as "number of deranged matchings" implies the defining recursion relation: let (x_1, y_1), (x_2, y_2), ..., (x_n, y_n) be the given pairs. In a deranged matching x_1 will be paired with any of the 2(n-1) objects x_2, y_2, x_3, y_3, ..., x_n, y_n. It is sufficient to count only those deranged matchings in which x_1, is matched with x_2. They are of two kinds: (i) y_1 is not matched with y_2; their number is a(n-1); (ii) y_1 is matched with y_2; their number is a(n-2). - Emeric Deutsch, Jan 23 2009

Inverse binomial transform of the odd double factorials (A001147). - David Callan, Aug 25 2009

From Lewis Mammel (l_mammel(AT)att.net), Oct 07 2009: (Start)

The formula is given directly by the Principle of Inclusion and Exclusion.

The first term includes all pairings, the second term excludes all pairings containing each pair, the third term includes all pairings containing each pair of pairs, and so on.

Based on n-a -> n for large n, the ratio a(n)/(2n-1)!! -> exp(-1/2) ~= 0.60653.

We find a(n)/(2n-1)!! for n= 100, 200, 300, 400 ~= 0.6050124904, 0.6057720290, 0.6060250088, 0.6061514604. (End)

This is a subset of the set of pairings of the first 2n integers (A001147) in another way: forbidding pairs of the form (2k,2k+1) for all k as well as the pair (1,2n) (seeing the constraint as circular by opposition to the linear A165968). - Olivier Gérard, Feb 08 2011

a(n) is the n-th central moment of a central chi-squared distribution (with 1 degree of freedom), i.e., a(n) = E[ (Y- E[Y] )^n ] = E[ (X^2 - 1 )^n ] where Y is chi-squared, X is std normal, X~N(0,1), and the expectation operator is E[]. - David Fioramonti, May 11 2016

Exponential self-convolution of a(n)/2^n gives subfactorials (A000166). - Vladimir Reshetnikov, Oct 09 2016

For n > 1, also the number of maximum matchings in the n-cocktail party graph. - Eric W. Weisstein, Jun 15 2017

Number of polygonal tiles with n sides with two exits per side and n edges connecting pairs of exits, with no edges between exits on the same side (cf. A289191, A289269 for nonisomorphic tiles under rotational and rotational and reflectional symmetries). - Marko Riedel, Jun 28 2017

Number of ways n people can hold hands (every hand is holding another hand) where no one is holding their own hand. - Harry Richman, Aug 29 2023

With offset 1, permanent of (0,1)-matrix of size n X (n+d) with d=4 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

a(n+3)=:b(n), n>=1, enumerates 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 four indistinguishable, ordered, fixed cords, each allowed to have any number of beads. Beadless necklaces as well as a beadless cords contribute each a factor 1 in the counting, e.g., b(0):= 1*1 =1. See A000255 for the description of a fixed cord with beads.

This produces for b(n) the exponential (aka binomial) convolution of the subfactorial sequence {A000166(n)} and the sequence {A001715 (n+3)}. See the necklaces and cords problem comment in A000153. Therefore also the recurrence b(n) = (n+3)*b(n-1) + (n-1)*b(n-2) with b(-1)=0 and b(0)=1 holds. 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

Permanent of the binary matrix with an entry equal to 0 iff the entry is on the main diagonal or the main antidiagonal. - Simone Severini, Oct 14 2004

From Toby Gottfried, Dec 05 2008: (Start)

Suppose you have a group of married couples (plus perhaps one other person).

You wish to organize a gift exchange so that:

- each person gives and receives one gift.

- no one gives himself a gift.

- no one gives his/her spouse a gift.

Then the sequence gives the number of ways that this can be done. (End)