cp's OEIS Frontend

The solution to Schröder's third problem.

Number of fixed-point-free involutions in symmetric group S_{2n} (cf. A000085).

a(n-2) is the number of full Steiner topologies on n points with n-2 Steiner points. [corrected by Lyle Ramshaw, Jul 20 2022]

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

Number of ways to choose n disjoint pairs of items from 2*n items. - Ron Zeno (rzeno(AT)hotmail.com), Feb 06 2002

Number of ways to choose n-1 disjoint pairs of items from 2*n-1 items (one item remains unpaired). - Bartosz Zoltak, Oct 16 2012

For n >= 1 a(n) is the number of permutations in the symmetric group S_(2n) whose cycle decomposition is a product of n disjoint transpositions. - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 21 2001

a(n) is the number of distinct products of n+1 variables with commutative, nonassociative multiplication. - Andrew Walters (awalters3(AT)yahoo.com), Jan 17 2004. For example, a(3)=15 because the product of the four variables w, x, y and z can be constructed in exactly 15 ways, assuming commutativity but not associativity: 1. w(x(yz)) 2. w(y(xz)) 3. w(z(xy)) 4. x(w(yz)) 5. x(y(wz)) 6. x(z(wy)) 7. y(w(xz)) 8. y(x(wz)) 9. y(z(wx)) 10. z(w(xy)) 11. z(x(wy)) 12. z(y(wx)) 13. (wx)(yz) 14. (wy)(xz) 15. (wz)(xy).

a(n) = E(X^(2n)), where X is a standard normal random variable (i.e., X is normal with mean = 0, variance = 1). So for instance a(3) = E(X^6) = 15, etc. See Abramowitz and Stegun or Hoel, Port and Stone. - Jerome Coleman, Apr 06 2004

Second Eulerian transform of 1,1,1,1,1,1,... The second Eulerian transform transforms a sequence s to a sequence t by the formula t(n) = Sum_{k=0..n} E(n,k)s(k), where E(n,k) is a second-order Eulerian number (A008517). - Ross La Haye, Feb 13 2005

Integral representation as n-th moment of a positive function on the positive axis: a(n) = Integral_{x=0..oo} x^n*exp(-x/2)/sqrt(2*Pi*x) dx, n >= 0. - Karol A. Penson, Oct 10 2005

a(n) is the number of binary total partitions of n+1 (each non-singleton block must be partitioned into exactly two blocks) or, equivalently, the number of unordered full binary trees with n+1 labeled leaves (Stanley, ex 5.2.6). - Mitch Harris, Aug 01 2006

a(n) is the Pfaffian of the skew-symmetric 2n X 2n matrix whose (i,j) entry is i for iDavid Callan, Sep 25 2006

a(n) is the number of increasing ordered rooted trees on n+1 vertices where "increasing" means the vertices are labeled 0,1,2,...,n so that each path from the root has increasing labels. Increasing unordered rooted trees are counted by the factorial numbers A000142. - David Callan, Oct 26 2006

Number of perfect multi Skolem-type sequences of order n. - Emeric Deutsch, Nov 24 2006

a(n) = total weight of all Dyck n-paths (A000108) when each path is weighted with the product of the heights of the terminal points of its upsteps. For example with n=3, the 5 Dyck 3-paths UUUDDD, UUDUDD, UUDDUD, UDUUDD, UDUDUD have weights 1*2*3=6, 1*2*2=4, 1*2*1=2, 1*1*2=2, 1*1*1=1 respectively and 6+4+2+2+1=15. Counting weights by height of last upstep yields A102625. - David Callan, Dec 29 2006

a(n) is the number of increasing ternary trees on n vertices. Increasing binary trees are counted by ordinary factorials (A000142) and increasing quaternary trees by triple factorials (A007559). - David Callan, Mar 30 2007

From Tom Copeland, Nov 13 2007, clarified in first and extended in second paragraph, Jun 12 2021: (Start)

a(n) has the e.g.f. (1-2x)^(-1/2) = 1 + x + 3*x^2/2! + ..., whose reciprocal is (1-2x)^(1/2) = 1 - x - x^2/2! - 3*x^3/3! - ... = b(0) - b(1)*x - b(2)*x^2/2! - ... with b(0) = 1 and b(n+1) = -a(n) otherwise. By the formalism of A133314, Sum_{k=0..n} binomial(n,k)*b(k)*a(n-k) = 0^n where 0^0 := 1. In this sense, the sequence a(n) is essentially self-inverse. See A132382 for an extension of this result. See A094638 for interpretations.

This sequence aerated has the e.g.f. e^(t^2/2) = 1 + t^2/2! + 3*t^4/4! + ... = c(0) + c(1)*t + c(2)*t^2/2! + ... and the reciprocal e^(-t^2/2); therefore, Sum_{k=0..n} cos(Pi k/2)*binomial(n,k)*c(k)*c(n-k) = 0^n; i.e., the aerated sequence is essentially self-inverse. Consequently, Sum_{k=0..n} (-1)^k*binomial(2n,2k)*a(k)*a(n-k) = 0^n. (End)

From Ross Drewe, Mar 16 2008: (Start)

This is also the number of ways of arranging the elements of n distinct pairs, assuming the order of elements is significant but the pairs are not distinguishable, i.e., arrangements which are the same after permutations of the labels are equivalent.

If this sequence and A000680 are denoted by a(n) and b(n) respectively, then a(n) = b(n)/n! where n! = the number of ways of permuting the pair labels.

For example, there are 90 ways of arranging the elements of 3 pairs [1 1], [2 2], [3 3] when the pairs are distinguishable: A = { [112233], [112323], ..., [332211] }.

By applying the 6 relabeling permutations to A, we can partition A into 90/6 = 15 subsets: B = { {[112233], [113322], [221133], [223311], [331122], [332211]}, {[112323], [113232], [221313], [223131], [331212], [332121]}, ....}

Each subset or equivalence class in B represents a unique pattern of pair relationships. For example, subset B1 above represents {3 disjoint pairs} and subset B2 represents {1 disjoint pair + 2 interleaved pairs}, with the order being significant (contrast A132101). (End)

A139541(n) = a(n) * a(2*n). - Reinhard Zumkeller, Apr 25 2008

a(n+1) = Sum_{j=0..n} A074060(n,j) * 2^j. - Tom Copeland, Sep 01 2008

From Emeric Deutsch, Jun 05 2009: (Start)

a(n) is the number of adjacent transpositions in all fixed-point-free involutions of {1,2,...,2n}. Example: a(2)=3 because in 2143=(12)(34), 3412=(13)(24), and 4321=(14)(23) we have 2 + 0 + 1 adjacent transpositions.

a(n) = Sum_{k>=0} k*A079267(n,k).

(End)

Hankel transform is A137592. - Paul Barry, Sep 18 2009

(1, 3, 15, 105, ...) = INVERT transform of A000698 starting (1, 2, 10, 74, ...). - Gary W. Adamson, Oct 21 2009

a(n) = (-1)^(n+1)*H(2*n,0), where H(n,x) is the probabilists' Hermite polynomial. The generating function for the probabilists' Hermite polynomials is as follows: exp(x*t-t^2/2) = Sum_{i>=0} H(i,x)*t^i/i!. - Leonid Bedratyuk, Oct 31 2009

The Hankel transform of a(n+1) is A168467. - Paul Barry, Dec 04 2009

Partial products of odd numbers. - Juri-Stepan Gerasimov, Oct 17 2010

See A094638 for connections to differential operators. - Tom Copeland, Sep 20 2011

a(n) is the number of subsets of {1,...,n^2} that contain exactly k elements from {1,...,k^2} for k=1,...,n. For example, a(3)=15 since there are 15 subsets of {1,2,...,9} that satisfy the conditions, namely, {1,2,5}, {1,2,6}, {1,2,7}, {1,2,8}, {1,2,9}, {1,3,5}, {1,3,6}, {1,3,7}, {1,3,8}, {1,3,9}, {1,4,5}, {1,4,6}, {1,4,7}, {1,4,8}, and {1,4,9}. - Dennis P. Walsh, Dec 02 2011

a(n) is the leading coefficient of the Bessel polynomial y_n(x) (cf. A001498). - Leonid Bedratyuk, Jun 01 2012

For n>0: a(n) is also the determinant of the symmetric n X n matrix M defined by M(i,j) = min(i,j)^2 for 1 <= i,j <= n. - Enrique Pérez Herrero, Jan 14 2013

a(n) is also the numerator of the mean value from 0 to Pi/2 of sin(x)^(2n). - Jean-François Alcover, Jun 13 2013

a(n) is the size of the Brauer monoid on 2n points (see A227545). - James Mitchell, Jul 28 2013

For n>1: a(n) is the numerator of M(n)/M(1) where the numbers M(i) have the property that M(n+1)/M(n) ~ n-1/2 (for example, large Kendell-Mann numbers, see A000140 or A181609, as n --> infinity). - Mikhail Gaichenkov, Jan 14 2014

a(n) = the number of upper-triangular matrix representations required for the symbolic representation of a first order central moment of the multivariate normal distribution of dimension 2(n-1), i.e., E[X_1*X_2...*X_(2n-2)|mu=0, Sigma]. See vignette for symmoments R package on CRAN and Phillips reference below. - Kem Phillips, Aug 10 2014

For n>1: a(n) is the number of Feynman diagrams of order 2n (number of internal vertices) for the vacuum polarization with one charged loop only, in quantum electrodynamics. - Robert Coquereaux, Sep 15 2014

Aerated with intervening zeros (1,0,1,0,3,...) = a(n) (cf. A123023), the e.g.f. is e^(t^2/2), so this is the base for the Appell sequence A099174 with e.g.f. e^(t^2/2) e^(x*t) = exp(P(.,x),t) = unsigned A066325(x,t), the probabilist's (or normalized) Hermite polynomials. P(n,x) = (a. + x)^n with (a.)^n = a_n and comprise the umbral compositional inverses for A066325(x,t) = exp(UP(.,x),t), i.e., UP(n,P(.,t)) = x^n = P(n,UP(.,t)), where UP(n,t) are the polynomials of A066325 and, e.g., (P(.,t))^n = P(n,t). - Tom Copeland, Nov 15 2014

a(n) = the number of relaxed compacted binary trees of right height at most one of size n. 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 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. 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. The number of unbounded relaxed compacted binary trees of size n is A082161(n). See the Genitrini et al. link. - Michael Wallner, Jun 20 2017

Also the number of distinct adjacency matrices in the n-ladder rung graph. - Eric W. Weisstein, Jul 22 2017

From Christopher J. Smyth, Jan 26 2018: (Start)

a(n) = the number of essentially different ways of writing a probability distribution taking n+1 values as a sum of products of binary probability distributions. See comment of Mitch Harris above. This is because each such way corresponds to a full binary tree with n+1 leaves, with the leaves labeled by the values. (This comment is due to Niko Brummer.)

Also the number of binary trees with root labeled by an (n+1)-set S, its n+1 leaves by the singleton subsets of S, and other nodes labeled by subsets T of S so that the two daughter nodes of the node labeled by T are labeled by the two parts of a 2-partition of T. This also follows from Mitch Harris' comment above, since the leaf labels determine the labels of the other vertices of the tree.

(End)

a(n) is the n-th moment of the chi-squared distribution with one degree of freedom (equivalent to Coleman's Apr 06 2004 comment). - Bryan R. Gillespie, Mar 07 2021

Let b(n) = 0 for n odd and b(2k) = a(k); i.e., let the sequence b(n) be an aerated version of this entry. After expanding the differential operator (x + D)^n and normal ordering the resulting terms, the integer coefficient of the term x^k D^m is n! b(n-k-m) / [(n-k-m)! k! m!] with 0 <= k,m <= n and (k+m) <= n. E.g., (x+D)^2 = x^2 + 2xD + D^2 + 1 with D = d/dx. The result generalizes to the raising (R) and lowering (L) operators of any Sheffer polynomial sequence by replacing x by R and D by L and follows from the disentangling relation e^{t(L+R)} = e^{t^2/2} e^{tR} e^{tL}. Consequently, these are also the coefficients of the reordered 2^n permutations of the binary symbols L and R under the condition LR = RL + 1. E.g., (L+R)^2 = LL + LR + RL + RR = LL + 2RL + RR + 1. (Cf. A344678.) - Tom Copeland, May 25 2021

From Tom Copeland, Jun 14 2021: (Start)

Lando and Zvonkin present several scenarios in which the double factorials occur in their role of enumerating perfect matchings (pairings) and as the nonzero moments of the Gaussian e^(x^2/2).

Speyer and Sturmfels (p. 6) state that the number of facets of the abstract simplicial complex known as the tropical Grassmannian G'''(2,n), the space of phylogenetic T_n trees (see A134991), or Whitehouse complex is a shifted double factorial.

These are also the unsigned coefficients of the x[2]^m terms in the partition polynomials of A134685 for compositional inversion of e.g.f.s, a refinement of A134991.

a(n)*2^n = A001813(n) and A001813(n)/(n+1)! = A000108(n), the Catalan numbers, the unsigned coefficients of the x[2]^m terms in the partition polynomials A133437 for compositional inversion of o.g.f.s, a refinement of A033282, A126216, and A086810. Then the double factorials inherit a multitude of analytic and combinatoric interpretations from those of the Catalan numbers, associahedra, and the noncrossing partitions of A134264 with the Catalan numbers as unsigned-row sums. (End)

Connections among the Catalan numbers A000108, the odd double factorials, values of the Riemann zeta function and its derivative for integer arguments, and series expansions of the reduced action for the simple harmonic oscillator and the arc length of the spiral of Archimedes are given in the MathOverflow post on the Riemann zeta function. - Tom Copeland, Oct 02 2021

b(n) = a(n) / (n! 2^n) = Sum_{k = 0..n} (-1)^n binomial(n,k) (-1)^k a(k) / (k! 2^k) = (1-b.)^n, umbrally; i.e., the normalized double factorial a(n) is self-inverse under the binomial transform. This can be proved by applying the Euler binomial transformation for o.g.f.s Sum_{n >= 0} (1-b.)^n x^n = (1/(1-x)) Sum_{n >= 0} b_n (x / (x-1))^n to the o.g.f. (1-x)^{-1/2} = Sum_{n >= 0} b_n x^n. Other proofs are suggested by the discussion in Watson on pages 104-5 of transformations of the Bessel functions of the first kind with b(n) = (-1)^n binomial(-1/2,n) = binomial(n-1/2,n) = (2n)! / (n! 2^n)^2. - Tom Copeland, Dec 10 2022

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 the number of partitions of n-1, n >= 2, such that the least part occurs exactly once. See A096373, A097091, A097092, A097093. - Robert G. Wilson v, Jul 24 2004 [Corrected by Wolfdieter Lang, Feb 18 2009]

Number of partitions of n+1 where the number of parts is itself a part. Take a partition of n (with k parts) which does not contain 1, remove 1 from each part and add a new part of size k+1. - Franklin T. Adams-Watters, May 01 2006

Number of partitions where the largest part occurs at least twice. - Joerg Arndt, Apr 17 2011

Row sums of triangle A147768. - Gary W. Adamson, Nov 11 2008

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

a(n) is the number of sets of n disjoint pairs of 2n things, called a pairing, disjoint with a given pairing (A053871), that are unique under permutations preserving the given pairing.

Can be seen immediately from a graphical representation which must decompose into even numbered cycles of 4 or more things, as connected by pairs alternating between the pairings. Each thing is in a single cycle, so this is a partition of 2n into even parts greater than 2, equivalent to a partition of n into parts greater than 1. (End)

Convolution product (1, 1, 2, 2, 4, 4, ...) * (1, 2, 3, ...) = A058682 starting (1, 3, 7, 13, 23, 37, ...); with row sums of triangle A171239 = A058682. - Gary W. Adamson, Dec 05 2009

Also the number of 2-regular multigraphs with loops forbidden. - Jason Kimberley, Jan 05 2011

Number of appearances of the multiplicity n, n-1, ..., n-k in all partitions of n, for k < n/2. (Only populated by multiplicities of large numbers of 1's.) - William Keith, Nov 20 2011

Also the number of equivalence classes of n X n binary matrices with exactly 2 1's in each row and column, up to permutations of rows and columns (cf. A133687). - N. J. A. Sloane, Sep 16 2013

The q-Catalan numbers ((1-q)/(1-q^(n+1)))[2n,n]q, where [2n,n]_q are the central q-binomial coefficients, match this sequence in their initial segment of length n. - _William J. Keith, Nov 14 2013

Starting at a(2) this sequence gives the number of vertices on a nim tree created in the game of edge removal for a path P_{n} where n is the number of vertices on the path. This is the number of nonisomorphic graphs that can result from the path when the game of edge removal is played. - Lyndsey Wong, Jul 09 2016

The number of different ways to climb a staircase taking at least two stairs at a time. - Mohammad K. Azarian, Nov 20 2016

Let 1,0,1,1,1,... (offset 0) count unlabeled, connected, loopless 1-regular digraphs. This here is the Euler transform of that sequence, counting unlabeled loopless 1-regular digraphs. A145574 is the associated multiset transformation. A000166 are the labeled loopless 1-regular digraphs. - R. J. Mathar, Mar 25 2019

For n > 1, also the number of partitions with no part greater than the number of ones. - George Beck, May 09 2019 [See A187219 which is the correct sequence for this interpretation for n >= 1. - Spencer Miller, Jan 30 2023]

From Gus Wiseman, May 19 2019: (Start)

Conjecture: Also the number of integer partitions of n - 1 that have a consecutive subsequence summing to each positive integer from 1 to n - 1. For example, (32211) is such a partition because we have consecutive subsequences:

1: (1)

2: (2)

3: (3) or (21)

4: (22) or (211)

5: (32) or (221)

6: (2211)

7: (322)

8: (3221)

9: (32211)

(End)

There is a sufficient and necessary condition to characterize the partitions defined by Gus Wiseman. It is that the largest part must be less than or equal to the number of ones plus one. Hence, the number of partitions of n with no part greater than the number of ones is the same as the number of partitions of n-1 that have a consecutive subsequence summing to each integer from 1 to n-1. Gus Wiseman's conjecture can be proved bijectively. - Andrew Yezhou Wang, Dec 14 2019

From Peter Bala, Dec 01 2024: (Start)

Let P(2, n) denote the set of partitions of n into parts k > 1. Then A000041(n) = - Sum_{parts k in all partitions in P(2, n+2)} mu(k). For example, with n = 5, there are 4 partitions of n + 2 = 7 into parts greater than 1, namely, 7, 5 + 2, 4 + 3, 3 + 2 + 2, and mu(7) + (mu(5) + mu(2)) + (mu(4 ) + mu(3)) + (mu(3) + mu(2) + mu(2)) = -7 = - A000041(5). (End)

Or, number of labeled 2-regular relations of order n.

Also number of ways to arrange 2n rooks on an n X n chessboard, with no more than 2 rooks in each row and column (no 3 in a line). - Vaclav Kotesovec, Aug 03 2013

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

Table starts

.1.....0..........0................0.....................0....................0

.1.....2..........1................2.....................1....................2

.1.....8.........56..............332..................2350................16108

.1....60.......3201...........184740..............11375145............730983420

.1...544.....307016........196389904..........137409486772......102117302729744

.1..6040...43200625.....368696849320......3537141103745065.36724170744914466520

.1.79008.8403205056.1122409297218768.173357342638694530002

Binomial transform of A001147.

T is an example of the group of matrices outlined in the table in A132382--the associated matrix for aC(1,1). The e.g.f. for the row polynomials is exp(x*t) * exp(-x) * (1-2*x)^(-1/2). T(n,k) = Binomial(n,k)* s(n-k) where s = A053871 with an e.g.f. of exp(-x) * (1-2*x)^(-1/2) which is the reciprocal of the e.g.f. of A055142. The row polynomials form an Appell sequence. Tom Copeland, Sep 10 2008

A231846 provides a refinement of this array. - Tom Copeland, Oct 12 2016