cp's OEIS Frontend

The mousetrap sequence (A002467) can be defined in a Fibonacci-like way as: a(0) = a(1) = 1; for n>1 a(n) = n*(a(n-1)+a(n-2)). The current sequence is thus the tribonacci equivalent of that.

n divides a(n) and a(n+2) for odd n. 2 divides a(n) for even n. - Alexander Adamchuk, Jan 11 2008

Euler (1809) not only gives the first ten or so terms of the sequence, he also proves both recurrences a(n) = (n-1)*(a(n-1) + a(n-2)) and a(n) = n*a(n-1) + (-1)^n.

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

a(n) is the number of desarrangements of length n. A desarrangement of length n is a permutation p of {1,2,...,n} for which the smallest of all the ascents of p (taken to be n if there are no ascents) is even. Example: a(3) = 2 because we have 213 and 312 (smallest ascents at i = 2). See the J. Désarménien link and the Bona reference (p. 118). - Emeric Deutsch, Dec 28 2007

a(n) is the number of deco polyominoes of height n and having in the last column an even number of cells. A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column. - Emeric Deutsch, Dec 28 2007

Attributed to Nicholas Bernoulli in connection with a probability problem that he presented. See Problem #15, p. 494, in "History of Mathematics" by David M. Burton, 6th edition. - Mohammad K. Azarian, Feb 25 2008

a(n) is the number of permutations p of {1,2,...,n} with p(1)!=1 and having no right-to-left minima in consecutive positions. Example a(3) = 2 because we have 231 and 321. - Emeric Deutsch, Mar 12 2008

a(n) is the number of permutations p of {1,2,...,n} with p(n)! = n and having no left to right maxima in consecutive positions. Example a(3) = 2 because we have 312 and 321. - Emeric Deutsch, Mar 12 2008

Number of wedged (n-1)-spheres in the homotopy type of the Boolean complex of the complete graph K_n. - Bridget Tenner, Jun 04 2008

The only prime number in the sequence is 2. - Howard Berman (howard_berman(AT)hotmail.com), Nov 08 2008

From Emeric Deutsch, Apr 02 2009: (Start)

a(n) is the number of permutations of {1,2,...,n} having exactly one small ascent. A small ascent in a permutation (p_1,p_2,...,p_n) is a position i such that p_{i+1} - p_i = 1. (Example: a(3) = 2 because we have 312 and 231; see the Charalambides reference, pp. 176-180.) [See also David, Kendall and Barton, p. 263. - N. J. A. Sloane, Apr 11 2014]

a(n) is the number of permutations of {1,2,...,n} having exactly one small descent. A small descent in a permutation (p_1,p_2,...,p_n) is a position i such that p_i - p_{i+1} = 1. (Example: a(3)=2 because we have 132 and 213.) (End)

For n > 2, a(n) + a(n-1) = A000255(n-1); where A000255 = (1, 1, 3, 11, 53, ...). - Gary W. Adamson, Apr 16 2009

Connection to A002469 (game of mousetrap with n cards): A002469(n) = (n-2)*A000255(n-1) + A000166(n). (Cf. triangle A159610.) - Gary W. Adamson, Apr 17 2009

From Emeric Deutsch, Jul 18 2009: (Start)

a(n) is the sum of the values of the largest fixed points of all non-derangements of length n-1. Example: a(4)=9 because the non-derangements of length 3 are 123, 132, 213, and 321, having largest fixed points 3, 1, 3, and 2, respectively.

a(n) is the number of non-derangements of length n+1 for which the difference between the largest and smallest fixed point is 2. Example: a(3) = 2 because we have 1'43'2 and 32'14'; a(4) = 9 because we have 1'23'54, 1'43'52, 1'53'24, 52'34'1, 52'14'3, 32'54'1, 213'45', 243'15', and 413'25' (the extreme fixed points are marked).

(End)

a(n), n >= 1, is also the number of unordered necklaces with n beads, labeled differently from 1 to n, where each necklace has >= 2 beads. This produces the M2 multinomial formula involving partitions without part 1 given below. Because M2(p) counts the permutations with cycle structure given by partition p, this formula gives the number of permutations without fixed points (no 1-cycles), i.e., the derangements, hence the subfactorials with their recurrence relation and inputs. Each necklace with no beads is assumed to contribute a factor 1 in the counting, hence 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 01 2010

From Emeric Deutsch, Sep 06 2010: (Start)

a(n) is the number of permutations of {1,2,...,n, n+1} starting with 1 and having no successions. A succession in a permutation (p_1,p_2,...,p_n) is a position i such that p_{i+1} - p_i = 1. Example: a(3)=2 because we have 1324 and 1432.

a(n) is the number of permutations of {1,2,...,n} that do not start with 1 and have no successions. A succession in a permutation (p_1,p_2,...,p_n) is a position i such that p_{i+1} - p_i = 1. Example: a(3)=2 because we have 213 and 321.

(End)

Increasing colored 1-2 trees with choice of two colors for the rightmost branch of nonleave except on the leftmost path, there is no vertex of outdegree one on the leftmost path. - Wenjin Woan, May 23 2011

a(n) is the number of zeros in n-th row of the triangle in A170942, n > 0. - Reinhard Zumkeller, Mar 29 2012

a(n) is the maximal number of totally mixed Nash equilibria in games of n players, each with 2 pure options. - Raimundas Vidunas, Jan 22 2014

Convolution of sequence A135799 with the sequence generated by 1+x^2/(2*x+1). - Thomas Baruchel, Jan 08 2016

The number of interior lattice points of the subpolytope of the n-dimensional permutohedron whose vertices correspond to permutations avoiding 132 and 312. - Robert Davis, Oct 05 2016

Consider n circles of different radii, where each circle is either put inside some bigger circle or contains a smaller circle inside it (no common points are allowed). Then a(n) gives the number of such combinations. - Anton Zakharov, Oct 12 2016

If we partition the permutations of [n+1] in A000240 according to their starting digit, we will get (n+1) equinumerous classes each of size a(n), i.e., A000240(n+1) = (n+1)*a(n), hence a(n) is the size of each class of permutations of [n+1] in A000240. For example, for n = 4 we have 45 = 5*9. - Enrique Navarrete, Jan 10 2017

Call d_n1 the permutations of [n] that have the substring n1 but no substring in {12,23,...,(n-1)n}. If we partition them according to their starting digit, we will get (n-1) equinumerous classes each of size A000166(n-2) (the class starting with the digit 1 is empty since we must have the substring n1). Hence d_n1 = (n-1)*A000166(n-2) and A000166(n-2) is the size of each nonempty class in d_n1. For example, d_71 = 6*44 = 264, so there are 264 permutations in d_71 distributed in 6 nonempty classes of size A000166(5) = 44. (To get permutations in d_n1 recursively from more basic ones see the link "Forbidden Patterns" below.) - Enrique Navarrete, Jan 15 2017

Also the number of maximum matchings and minimum edge covers in the n-crown graph. - Eric W. Weisstein, Jun 14 and Dec 24 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) for all n and k, which in turn is easily proved by induction making use of the recurrence a(n) = n*a(n-1) + (-1)^n. - Peter Bala, Nov 21 2017

a(n) is the number of distinct possible solutions for a directed, no self loop containing graph (not necessarily connected) that has n vertices, and each vertex has an in- and out-degree of exactly 1. - Patrik Holopainen, Sep 18 2018

a(n) is the dimension of the kernel of the random-to-top and random-to-random shuffling operators over a collection of n objects (in a vector space of size n!), as noticed by M. Wachs and V. Reiner. See the Reiner, Saliola and Welker reference below. - Nadia Lafreniere, Jul 18 2019

a(n) is the number of distinct permutations for a Secret Santa gift exchange with n participants. - Patrik Holopainen, Dec 30 2019

a(2*n+1) is even. More generally, a(m*n+1) is divisible by m*n, which follows from a(n+1) = n*(a(n) + a(n-1)) = n*A000255(n-1) for n >= 1. a(2*n) is odd; in fact, a(2*n) == 1 (mod 8). Other divisibility properties include a(6*n) == 1 (mod 24), a(9*n+4) == a(9*n+7) == 0 (mod 9), a(10*n) == 1 (mod 40), a(11*n+5) == 0 (mod 11) and a(13*n+8 ) == 0 (mod 13). - Peter Bala, Apr 05 2022

Conjecture: a(n) with n > 2 is a perfect power only for n = 4 with a(4) = 3^2. This has been verified for n <= 1000. - Zhi-Wei Sun, Jan 09 2025

Also number of partitions of n with positive crank (n>=2), cf. A064391. - Vladeta Jovovic, Sep 30 2001

Number of smooth weakly unimodal compositions of n into positive parts such that the first and last part are 1 (smooth means that successive parts differ by at most one), see example. Dropping the requirement for unimodality gives A186085. - Joerg Arndt, Dec 09 2012

Number of weakly unimodal compositions of n where the maximal part m appears at least m times, see example. - Joerg Arndt, Jun 11 2013

Also weakly unimodal compositions of n with first part 1, maximal up-step 1, and no consecutive up-steps; see example. The smooth weakly unimodal compositions are recovered by shifting all rows above the bottom row to the left by one position with respect to the next lower row. - Joerg Arndt, Mar 30 2014

It would seem from Stanley that he regards a(0)=0 for this sequence and A001523. - Michael Somos, Feb 22 2015

From Gus Wiseman, Mar 30 2021: (Start)

Also the number of odd-length compositions of n with alternating parts strictly decreasing. These are finite odd-length sequences q of positive integers summing to n such that q(i) > q(i+2) for all possible i. The even-length version is A064428. For example, the a(1) = 1 through a(9) = 14 compositions are:

(1) (2) (3) (4) (5) (6) (7) (8) (9)

(211) (221) (231) (241) (251) (261)

(311) (312) (322) (332) (342)

(321) (331) (341) (351)

(411) (412) (413) (423)

(421) (422) (432)

(511) (431) (441)

(512) (513)

(521) (522)

(611) (531)

(612)

(621)

(711)

(32211)

(End)

In the Ferrers diagram of a partition x of n, count the dots in each diagonal parallel to the main diagonal (starting at the top-right, say). The result diag(x) is a smooth weakly unimodal composition of n into positive parts such that the first and last part are 1. For example, diag(5541) = 11233221. The function diag is many-to-one; the size of its codomain as a set is a(n). If diag(x) = diag(y), each hook of x can be slid by the same amount past the main diagonal to get y. For example, diag(5541) = diag(44331). - George Beck, Sep 26 2021

From Gus Wiseman, May 23 2022: (Start)

Conjecture: Also the number of integer partitions y of n with a fixed point y(i) = i. These partitions are ranked by A352827. The conjecture is stated at A238395, but Resta tells me he may not have had a proof. The a(1) = 1 through a(8) = 10 partitions are:

(1) (11) (111) (22) (32) (42) (52) (62)

(1111) (221) (222) (322) (422)

(11111) (321) (421) (521)

(2211) (2221) (2222)

(111111) (3211) (3221)

(22111) (4211)

(1111111) (22211)

(32111)

(221111)

(11111111)

Note that these are not the same partitions (compare A352827 to A352874), only the same count (apparently).

(End)

The above conjecture is true. See Section 4 of the Blecher-Knopfmacher paper in the Links section. - Jeremy Lovejoy, Sep 26 2022

For a partition p, let l(p) = largest part of p, w(p) = number of 1's in p, m(p) = number of parts of p larger than w(p). The crank of p is given by l(p) if w(p) = 0, otherwise m(p)-w(p).

From Gus Wiseman, Mar 30 2021 and May 21 2022: (Start)

Also the number of even-length compositions of n with alternating parts strictly decreasing, or properly 2-colored partitions (proper = no equal parts of the same color) with the same number of parts of each color, or ordered pairs of strict partitions of the same length with total n. The odd-length case is A001522, and there are a total of A000041 compositions with alternating parts strictly decreasing (see A342528 for a bijective proof). The a(2) = 1 through a(7) = 8 ordered pairs of strict partitions of the same length are:

(1)(1) (1)(2) (1)(3) (1)(4) (1)(5) (1)(6)

(2)(1) (2)(2) (2)(3) (2)(4) (2)(5)

(3)(1) (3)(2) (3)(3) (3)(4)

(4)(1) (4)(2) (4)(3)

(5)(1) (5)(2)

(21)(21) (6)(1)

(21)(31)

(31)(21)

Conjecture: Also the number of integer partitions y of n without a fixed point y(i) = i, ranked by A352826. This is stated at A238394, but Resta tells me he may not have had a proof. The a(2) = 1 through a(7) = 8 partitions without a fixed point are:

(2) (3) (4) (5) (6) (7)

(21) (31) (41) (33) (43)

(211) (311) (51) (61)

(2111) (411) (331)

(3111) (511)

(21111) (4111)

(31111)

(211111)

The version for permutations is A000166, complement A002467.

The version for compositions is A238351.

This is column k = 0 of A352833.

A238352 counts reversed partitions by fixed points, rank statistic A352822.

A238394 counts reversed partitions without a fixed point, ranked by A352830.

A238395 counts reversed partitions with a fixed point, ranked by A352872. (End)

The above conjecture is true. See Section 4 of the Blecher-Knopfmacher paper in the Links section. - Jeremy Lovejoy, Sep 26 2022

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

Number of permutations of 1,2,...,k,n+1,n+2,...,2n-k that have no agreements with 1,...,n. For example, consider 1234 and 1256, then n=4 and k=2, so T(4,2)=14. Compare A000255 for the case k=1. - Jon Perry, Jan 23 2004

From Emeric Deutsch, Apr 21 2009: (Start)

T(n-1,k-1) is the number of non-derangements of {1,2,...,n} having smallest fixed point equal to k. Example: T(3,1)=4 because we have 4213, 4231, 3214, and 3241 (the permutations of {1,2,3,4} having smallest fixed equal to 2).

Row sums give the number of non-derangement permutations of {1,2,...,n} (A002467).

Mirror image of A068106.

Closely related to A134830, where each row has an extra term (see the Charalambides reference).

(End)

T(n,k) is the number of permutations of {1..n} that don't fix the points 1..k. - Robert FERREOL, Aug 04 2016

Triangle T(n,k) (n >= 1, 1 <= k <= n) giving number of ways of winning with (n-k+1)st card in the generalized "Game of Thirteen" with n cards.

From Emeric Deutsch, Apr 21 2009: (Start)

T(n-1,k-1) is the number of non-derangements of {1,2,...,n} having largest fixed point equal to k. Example: T(3,1)=3 because we have 1243, 4213, and 3241.

Mirror image of A047920.

(End)

a(n) is the number of stack polyominoes of area n with square core.

The core of stack is the set of all maximal columns.

The core is a square when the number of columns is equal to their height.

Equivalently, a(n) is the number of unimodal compositions of n, where the number of the parts of maximum value equal the maximum value itself. For instance, for n = 10, we have the following stacks:

(1,3,3,3), (3,3,3,1), (1,1,1,1,1,1,2,2), (1,1,1,1,1,2,2,1), (1,1,1,1,2,2,1,1), (1,1,1,2,2,1,1,1), (1,1,2,2,1,1,1,1), (1,2,2,1,1,1,1,1), (2,2,1,1,1,1,1,1).

From Gus Wiseman, Apr 06 2019 and May 21 2022: (Start)

Also the number of integer partitions of n with final part in their inner lining partition equal to 1, where the k-th part of the inner lining partition of a partition is the number of squares in its Young diagram that are k diagonal steps from the lower-right boundary. For example, the a(4) = 1 through a(10) = 9 partitions are:

(22) (32) (42) (52) (62) (72) (82)

(221) (321) (421) (521) (333) (433)

(2211) (3211) (4211) (621) (721)

(22111) (32111) (5211) (3331)

(221111) (42111) (6211)

(321111) (52111)

(2211111) (421111)

(3211111)

(22111111)

Also partitions that have a fixed point and a conjugate fixed point, ranked by A353317. The strict case is A352829. For example, the a(0) = 0 through a(9) = 7 partitions are:

() . . (21) (31) (41) (51) (61) (71)

(211) (311) (411) (511) (332)

(2111) (3111) (4111) (611)

(21111) (31111) (5111)

(211111) (41111)

(311111)

(2111111)

Also partitions of n + 1 without a fixed point or conjugate fixed point.

(End)