cp's OEIS Frontend

Number of ways n competitors can rank in a competition, allowing for the possibility of ties.

Also number of asymmetric generalized weak orders on n points.

Also called the ordered Bell numbers.

A weak order is a relation that is transitive and complete.

Called Fubini numbers by Comtet: counts formulas in Fubini theorem when switching the order of summation in multiple sums. - Olivier Gérard, Sep 30 2002 [Named after the Italian mathematician Guido Fubini (1879-1943). - Amiram Eldar, Jun 17 2021]

If the points are unlabeled then the answer is a(0) = 1, a(n) = 2^(n-1) (cf. A011782).

For n>0, a(n) is the number of elements in the Coxeter complex of type A_{n-1}. The corresponding sequence for type B is A080253 and there one can find a worked example as well as a geometric interpretation. - Tim Honeywill and Paul Boddington, Feb 10 2003

Also number of labeled (1+2)-free posets. - Detlef Pauly, May 25 2003

Also the number of chains of subsets starting with the empty set and ending with a set of n distinct objects. - Andrew Niedermaier, Feb 20 2004

From Michael Somos, Mar 04 2004: (Start)

Stirling transform of A007680(n) = [3,10,42,216,...] gives [3,13,75,541,...].

Stirling transform of a(n) = [1,3,13,75,...] is A083355(n) = [1,4,23,175,...].

Stirling transform of A000142(n) = [1,2,6,24,120,...] is a(n) = [1,3,13,75,...].

Stirling transform of A005359(n-1) = [1,0,2,0,24,0,...] is a(n-1) = [1,1,3,13,75,...].

Stirling transform of A005212(n-1) = [0,1,0,6,0,120,0,...] is a(n-1) = [0,1,3,13,75,...].

(End)

Unreduced denominators in convergent to log(2) = lim_{n->infinity} n*a(n-1)/a(n).

a(n) is congruent to a(n+(p-1)p^(h-1)) (mod p^h) for n >= h (see Barsky).

Stirling-Bernoulli transform of 1/(1-x^2). - Paul Barry, Apr 20 2005

This is the sequence of moments of the probability distribution of the number of tails before the first head in a sequence of fair coin tosses. The sequence of cumulants of the same probability distribution is A000629. That sequence is twice the result of deletion of the first term of this sequence. - Michael Hardy (hardy(AT)math.umn.edu), May 01 2005

With p(n) = the number of integer partitions of n, p(i) = the number of parts of the i-th partition of n, d(i) = the number of different parts of the i-th partition of n, p(j,i) = the j-th part of the i-th partition of n, m(i,j) = multiplicity of the j-th part of the i-th partition of n, one has: a(n) = Sum_{i=1..p(n)} (n!/(Product_{j=1..p(i)} p(i,j)!)) * (p(i)!/(Product_{j=1..d(i)} m(i,j)!)). - Thomas Wieder, May 18 2005

The number of chains among subsets of [n]. The summed term in the new formula is the number of such chains of length k. - Micha Hofri (hofri(AT)wpi.edu), Jul 01 2006

Occurs also as first column of a matrix-inversion occurring in a sum-of-like-powers problem. Consider the problem for any fixed natural number m>2 of finding solutions to the equation Sum_{k=1..n} k^m = (k+1)^m. Erdős conjectured that there are no solutions for n, m > 2. Let D be the matrix of differences of D[m,n] := Sum_{k=1..n} k^m - (k+1)^m. Then the generating functions for the rows of this matrix D constitute a set of polynomials in n (for varying n along columns) and the m-th polynomial defining the m-th row. Let GF_D be the matrix of the coefficients of this set of polynomials. Then the present sequence is the (unsigned) first column of GF_D^-1. - Gottfried Helms, Apr 01 2007

Assuming A = log(2), D is d/dx and f(x) = x/(exp(x)-1), we have a(n) = (n!/2*A^(n+1)) Sum_{k=0..n} (A^k/k!) D^n f(-A) which gives Wilf's asymptotic value when n tends to infinity. Equivalently, D^n f(-a) = 2*( A*a(n) - 2*a(n-1) ). - Martin Kochanski (mjk(AT)cardbox.com), May 10 2007

List partition transform (see A133314) of (1,-1,-1,-1,...). - Tom Copeland, Oct 24 2007

First column of A154921. - Mats Granvik, Jan 17 2009

A slightly more transparent interpretation of a(n) is as the number of 'factor sequences' of N for the case in which N is a product of n distinct primes. A factor sequence of N of length k is of the form 1 = x(1), x(2), ..., x(k) = N, where {x(i)} is an increasing sequence such that x(i) divides x(i+1), i=1,2,...,k-1. For example, N=70 has the 13 factor sequences {1,70}, {1,2,70}, {1,5,70}, {1,7,70}, {1,10,70}, {1,14,70}, {1,35,70}, {1,2,10,70}, {1,2,14,70}, {1,5,10,70}, {1,5,35,70}, {1,7,14,70}, {1,7,35,70}. - Martin Griffiths, Mar 25 2009

Starting (1, 3, 13, 75, ...) = row sums of triangle A163204. - Gary W. Adamson, Jul 23 2009

Equals double inverse binomial transform of A007047: (1, 3, 11, 51, ...). - Gary W. Adamson, Aug 04 2009

If f(x) = Sum_{n>=0} c(n)*x^n converges for every x, then Sum_{n>=0} f(n*x)/2^(n+1) = Sum_{n>=0} c(n)*a(n)*x^n. Example: Sum_{n>=0} exp(n*x)/2^(n+1) = Sum_{n>=0} a(n)*x^n/n! = 1/(2-exp(x)) = e.g.f. - Miklos Kristof, Nov 02 2009

Hankel transform is A091804. - Paul Barry, Mar 30 2010

It appears that the prime numbers greater than 3 in this sequence (13, 541, 47293, ...) are of the form 4n+1. - Paul Muljadi, Jan 28 2011

The Fi1 and Fi2 triangle sums of A028246 are given by the terms of this sequence. For the definitions of these triangle sums, see A180662. - Johannes W. Meijer, Apr 20 2011

The modified generating function A(x) = 1/(2-exp(x))-1 = x + 3*x^2/2! + 13*x^3/3! + ... satisfies the autonomous differential equation A' = 1 + 3*A + 2*A^2 with initial condition A(0) = 0. Applying [Bergeron et al., Theorem 1] leads to two combinatorial interpretations for this sequence: (A) a(n) gives the number of plane-increasing 0-1-2 trees on n vertices, where vertices of outdegree 1 come in 3 colors and vertices of outdegree 2 come in 2 colors. (B) a(n) gives the number of non-plane-increasing 0-1-2 trees on n vertices, where vertices of outdegree 1 come in 3 colors and vertices of outdegree 2 come in 4 colors. Examples are given below. - Peter Bala, Aug 31 2011

Starting with offset 1 = the eigensequence of A074909 (the beheaded Pascal's triangle), and row sums of triangle A208744. - Gary W. Adamson, Mar 05 2012

a(n) = number of words of length n on the alphabet of positive integers for which the letters appearing in the word form an initial segment of the positive integers. Example: a(2) = 3 counts 11, 12, 21. The map "record position of block containing i, 1<=i<=n" is a bijection from lists of sets on [n] to these words. (The lists of sets on [2] are 12, 1/2, 2/1.) - David Callan, Jun 24 2013

This sequence was the subject of one of the earliest uses of the database. Don Knuth, who had a computer printout of the database prior to the publication of the 1973 Handbook, wrote to N. J. A. Sloane on May 18, 1970, saying: "I have just had my first real 'success' using your index of sequences, finding a sequence treated by Cayley that turns out to be identical to another (a priori quite different) sequence that came up in connection with computer sorting." A000670 is discussed in Exercise 3 of Section 5.3.1 of The Art of Computer Programming, Vol. 3, 1973. - N. J. A. Sloane, Aug 21 2014

Ramanujan gives a method of finding a continued fraction of the solution x of an equation 1 = x + a2*x^2 + ... and uses log(2) as the solution of 1 = x + x^2/2 + x^3/6 + ... as an example giving the sequence of simplified convergents as 0/1, 1/1, 2/3, 9/13, 52/75, 375/541, ... of which the sequence of denominators is this sequence, while A052882 is the numerators. - Michael Somos, Jun 19 2015

For n>=1, a(n) is the number of Dyck paths (A000108) with (i) n+1 peaks (UD's), (ii) no UUDD's, and (iii) at least one valley vertex at every nonnegative height less than the height of the path. For example, a(2)=3 counts UDUDUD (of height 1 with 2 valley vertices at height 0), UDUUDUDD, UUDUDDUD. These paths correspond, under the "glove" or "accordion" bijection, to the ordered trees counted by Cayley in the 1859 reference, after a harmless pruning of the "long branches to a leaf" in Cayley's trees. (Cayley left the reader to infer the trees he was talking about from examples for small n and perhaps from his proof.) - David Callan, Jun 23 2015

From David L. Harden, Apr 09 2017: (Start)

Fix a set X and define two distance functions d,D on X to be metrically equivalent when d(x_1,y_1) <= d(x_2,y_2) iff D(x_1,y_1) <= D(x_2,y_2) for all x_1, y_1, x_2, y_2 in X.

Now suppose that we fix a function f from unordered pairs of distinct elements of X to {1,...,n}. Then choose positive real numbers d_1 <= ... <= d_n such that d(x,y) = d_{f(x,y)}; the set of all possible choices of the d_i's makes this an n-parameter family of distance functions on X. (The simplest example of such a family occurs when n is a triangular number: When that happens, write n = (k 2). Then the set of all distance functions on X, when |X| = k, is such a family.) The number of such distance functions, up to metric equivalence, is a(n).

It is easy to see that an equivalence class of distance functions gives rise to a well-defined weak order on {d_1, ..., d_n}. To see that any weak order is realizable, choose distances from the set of integers {n-1, ..., 2n-2} so that the triangle inequality is automatically satisfied. (End)

a(n) is the number of rooted labeled forests on n nodes that avoid the patterns 213, 312, and 321. - Kassie Archer, Aug 30 2018

From A.H.M. Smeets, Nov 17 2018: (Start)

Also the number of semantic different assignments to n variables (x_1, ..., x_n) including simultaneous assignments. From the example given by Joerg Arndt (Mar 18 2014), this is easily seen by replacing

"{i}" by "x_i := expression_i(x_1, ..., x_n)",

"{i, j}" by "x_i, x_j := expression_i(x_1, .., x_n), expression_j(x_1, ..., x_n)", i.e., simultaneous assignment to two different variables (i <> j),

similar for simultaneous assignments to more variables, and

"<" by ";", i.e., the sequential constructor. These examples are directly related to "Number of ways n competitors can rank in a competition, allowing for the possibility of ties." in the first comment.

From this also the number of different mean definitions as obtained by iteration of n different mean functions on n initial values. Examples:

the AGM(x1,x2) = AGM(x2,x1) is represented by {arithmetic mean, geometric mean}, i.e., simultaneous assignment in any iteration step;

Archimedes's scheme (for Pi) is represented by {geometric mean} < {harmonic mean}, i.e., sequential assignment in any iteration step;

the geometric mean of two values can also be observed by {arithmetic mean, harmonic mean};

the AGHM (as defined in A319215) is represented by {arithmetic mean, geometric mean, harmonic mean}, i.e., simultaneous assignment, but there are 12 other semantic different ways to assign the values in an AGHM scheme.

By applying power means (also called Holder means) this can be extended to any value of n. (End)

Total number of faces of all dimensions in the permutohedron of order n. For example, the permutohedron of order 3 (a hexagon) has 6 vertices + 6 edges + 1 2-face = 13 faces, and the permutohedron of order 4 (a truncated octahedron) has 24 vertices + 36 edges + 14 2-faces + 1 3-face = 75 faces. A001003 is the analogous sequence for the associahedron. - Noam Zeilberger, Dec 08 2019

Number of odd multinomial coefficients N!/(a_1!*a_2!*...*a_k!). Here each a_i is positive, and Sum_{i} a_i = N (so 2^{N-1} multinomial coefficients in all), where N is any positive integer whose binary expansion has n 1's. - Richard Stanley, Apr 05 2022 (edited Oct 19 2022)

From Peter Bala, Jul 08 2022: (Start)

Conjecture: Let k be a positive integer. The sequence obtained by reducing a(n) modulo k is eventually periodic with the period dividing phi(k) = A000010(k). For example, modulo 16 we obtain the sequence [1, 1, 3, 13, 11, 13, 11, 13, 11, 13, ...], with an apparent period of 2 beginning at a(4). Cf. A354242.

More generally, we conjecture that the same property holds for integer sequences having an e.g.f. of the form G(exp(x) - 1), where G(x) is an integral power series. (End)

a(n) is the number of ways to form a permutation of [n] and then choose a subset of its descent set. - Geoffrey Critzer, Apr 29 2023

This is the Akiyama-Tanigawa transform of A000079, the powers of two. - Shel Kaphan, May 02 2024

Newton calculated the first 16 terms of this sequence.

Area bounded by y = tan x, y = cot x, y = 0. - Clark Kimberling, Jun 26 2020

Choose four values independently and uniformly at random from the unit interval [0,1]. Sort them, and label them a,b,c,d from least to greatest (so that a b^2+c^2. - Akiva Weinberger, Dec 02 2024

Define the trihyperboloid to be the intersection of the three solid hyperboloids x^2+y^2-z^2<1, x^2-y^2+z^2<1, and -x^2+y^2+z^2<1. This fits perfectly within the cube [-1,1]^3. Then this is the ratio of the volume of the trihyperboloid to its bounding cube. - Akiva Weinberger, Dec 02 2024

Stirling transform of (-1)^n*a(n-1) = [0, 1, -1, 5, -14, 94, ...] is A000629(n-2) = [0, 1, 2, 6, 26, ...]. - Michael Somos, Mar 04 2004

Stirling transform of a(n) = [1, 1, 5, 14, 94, ...] is A052882(n) = [1, 2, 9, 52, 375, ...]. - Michael Somos, Mar 04 2004

a(n) is the number of n-permutations that have a cycle with length greater than n/2. - Geoffrey Critzer, May 28 2009

From Jens Voß, May 07 2010: (Start)

a(4n) is divisible by 6*n + 1 for all n >= 1; the quotient of a(4*n) and 6*n+1 is A177188(n).

a(4*n+3) is divisible by 6*n + 5 for all n >= 0; the quotient of a(4*n+3) and 6*n + 5 is A177174(n). (End)

Previous name: Matrix inverse of A154926.

A000670 appears in the first column. A052882 appears in the second column. A000027 and A045943 appear as diagonals. An alternative to calculating the matrix inverse of A154926 is to move the term in the lower right corner to a position in the same column and calculate the determinant instead, which yields the same answer.

Matrix inverse of (2*I - P), where P is Pascal's triangle and I the identity matrix. See A162312 for the matrix inverse of (2*P - I) and some general remarks about arrays of the form M(a) := (I - a*P)^-1 and their connection with weighted sums of powers of integers. The present array equals (1/2)*M(1/2). - Peter Bala, Jul 01 2009

From Mats Granvik, Aug 11 2009: (Start)

The values in this triangle can be seen as permanents of the Pascal triangle analogous to the method in the Redheffer matrix. The elements satisfy (T(n,k)/T(n,k-1))*k = (T(n-1,k)/T(n,k))*n which converges to log(2) as n->oo and k->0. More generally to calculate log(x) multiply the negative values in A154926 by 1/(x-1) and calculate the matrix inverse. Then (T(n,k)/T(n,k-1))*k and (T(n-1,k)/T(n,k))*n in the resulting triangle converge to log(x).

This method for calculating log(x) converges faster than the Taylor series when x is greater than 5 or so. See chapter on Taylor series in Spiegel for comparison. (End)

Exponential Riordan array [1/(2-exp(x)),x]. - Paul Barry, Apr 06 2011

T(n,k) is the number of ordered set partitions of {1,2,...,n} such that the first block contains k elements. For k=0 the first block contains arbitrarily many elements. - Geoffrey Critzer, Jul 22 2013

A natural (signed) refinement of these polynomials is given by the Appell sequence e.g.f. e^(xt)/ f(t) = exp[tP.(x)] with the formal Taylor series f(x) = 1 + x[1] x + x[2] x^2/2! + ... and with raising operator R = x - d[log(f(D)]/dD (cf. A263634). - Tom Copeland, Nov 06 2015

Around 1670, James Gregory discovered by inversion of 1 - 1/2 + 1/3 - 1/4 + 1/5 - ... = log(2) that 1 + 1/2 - 1/12 + 1/24 - 19/720 + (27/1440 = 3/160) - 863/60480 + ... = 1/log(2). See formula with A002206 and A002207. See also A141417 signed /A091137; case i = 0 in A165313. First row in array p. 36 of the reference. - Paul Curtz, Sep 12 2011

This constant 1/log(2) is also related to the asymptotic evaluation of the maximum number of subtraction steps required to compute gcd(m, n) by the binary Euclidean algorithm, m and n being odd and chosen at random. - Jean-François Alcover, Jun 23 2014, after Steven Finch

The number of connected labeled threshold graphs on n vertices. - Sam Spiro, Sep 22 2019

Also the number of 2-interval parking functions of size n. - Sam Spiro, Sep 24 2019

Row sums = A000670 starting (1, 3, 13, 75,...).

Right border = A052882 starting (1, 2, 9, 52, 375,...).

A000670 is the eigensequence of triangle A074909, deleting the first "1".

Triangle A074909 is the "beheaded" Pascal's triangle: (1; 1,2; 1,3,3;...).

A chain topology is a topology that can be totally ordered by inclusion.

Stirling transform of (-1)^n*a(n-1)=[0,1,-1,8,-18,...] is A052882(n-1)=[0,1,2,9,52,...].