0,3

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, i.e. the number of ordered partitions of {1,..,n}.

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

Called Fubini numbers by Comtet: counts formulae in Fubini theorem when switching the order of summation in multiple sums. - Olivier Gerard, Sep 30, 2002

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 & Paul Boddington (tch(AT)maths.warwick.ac.uk), 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. - Andy Niedermaier (aniedermaier(AT)hmc.edu), Feb 20 2004

Stirling transform of A007680(n) = [3, 10, 42, 216, . . . ] gives [3,13,75,541,...]. - Michael Somos Mar 04 2004

Stirling transform of a(n)=[1,3,13,75,...] is A083355(n)=[1,4,23,175,...]. - Michael Somos Mar 04 2004

Stirling transform of A000142(n)=[1,2,6,24,120,...] is a(n)=[1,3,13,75,...]. - Michael Somos Mar 04 2004

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

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

Unreduced denominators in convergent to log(2) = lim[n->inf, na(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 (pbarry(AT)wit.ie), 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, sum_{i=1}^{p(n)} = sum over i and prod_{j=1}^{d(i)} = product over j one has: a(n) = sum_{i=1}^{p(n)} (n!/(prod_{j=1}^{p(i)}p(i,j)!)) * (p(i)!/(prod_{j=1}^{d(i)} m(i,j)!)) - Thomas Wieder (wieder.thomas(AT)t-online.de), 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 occuring 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. Erdos 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=ln2, D is d/dx and f(x)=x/(exp(x)-1), we have a(n) = (n!/2A^(n+1)) sum( k=0 to 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 (tcjpn(AT)msn.com), Oct 24 2007

First column of A154921. [From Mats Granvik (mats.granvik(AT)abo.fi), 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}. [From Martin Griffiths (griffm(AT)essex.ac.uk), Mar 25 2009]

Starting (1, 3, 13, 75,...) = row sums of triangle A163204 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Jul 23 2009]

Equals double inverse binomial transform of A007047: (1, 3, 11, 51,...). [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 04 2009]

Contribution from Miklos Kristof (kristmikl(AT)freemail.hu), Nov 02 2009: (Start)

If f(x)=sum(c(n)*x^n ,n=0..infinity) converges for every x, then

sum(f(n*x)/2^(n+1), n=0..infinity) = sum(c(n)*a(n)*x^n, n=0..infinity).

Example: sum(exp(n*x)/2^(n+1), n=0..infinity) = sum(a(n)*x^n/n!, n=0..infinity)= 1/(2-exp(x)) = E.g.f. (End)

Ralph W. Bailey, "The number of weak orderings of a finite set", Social Choice and Welfare, Vol. 15 (1998), pp. 559-562.

N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 44 (P(x)).

Kenneth S. Brown, Buildings, Springer-Verlag, 1988

A. Cayley, On the theory of the analytical forms called trees II, Phil. Mag. 18 (1859), 374-378 = Math. Papers Vol. 4, pp. 112-115.

J. L. Chandon, J. LeMaire and J. Pouget, Denombrement des quasi-ordres sur un ensemble fini, Math. Sci. Humaines, No. 62 (1978), 61-80.

A. Claesson and T. K. Petersen, Conway's napkin problem, Amer. Math. Monthly, 114 (No. 3, 2007), 217-231.

Pietro Codara, Ottavio M. D'Antona and Vincenzo Marra, Best Approximation of Ruspini Partitions in Goedel Logic, in Symbolic and Quantitative Approaches to Reasoning with Uncertainty, Lecture Notes in Computer Science, Volume 4724/2007, Springer-Verlag. [From N. J. A. Sloane, Jul 09 2009]

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 228.

J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 13, pp 4, Ellipses, Paris 2008.

P. J. Freyd, On the size of Heyting semi-lattices, preprint, 2002.

S. Getu et al., How to guess a generating function, SIAM J. Discrete Math., 5 (1992), 497-499.

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd Ed., 1994, exercise 7.44 (pp. 378, 571).

O. A. Gross, Preferential arrangements, Amer. Math. Monthly, 69 (1962), 4-8.

Hans Maassen and Thom Bezembinder, Generating random weak orders and the probability of a Condorcet winner, Social Choice and Welfare, 19,3 (2002), 517-532.

P. A. MacMahon, Yoke-trains and multipartite compositions in connexion with the analytical forms called "trees", Proc. London Math. Soc. 22 (1891), 330-346; reprinted in Coll. Papers I, pp. 600-616.

E. Mendelsohn, Races with ties, Math. Mag. 55 (1982), 170-175.

M. Mor and A. S. Fraenkel, Cayley permutations, Discrete Math., 48 (1984), 101-112.

T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176.

T. S. Motzkin, Sorting numbers ...: for a link to this paper see A000262.

M. Muresan, Generalized Fubini numbers. Stud. Cerc. Mat. 37 (1985), no. 1, pp. 70-76.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. P. Stanley, Enumerative Combinatorics, Wadsworth, Vol. 1, 1986; see Example 3.15.10, p. 146.

D. J. Velleman and G. S. Call, Permutations and combination locks, Math. Mag., 68 (1995), 243-253.

C. G. Wagner, Enumeration of generalized weak orders. Arch. Math. (Basel) 39 (1982), no. 2, 147-152.

H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 147.

N. J. A. Sloane, Table of n, a(n) for n = 0..100

D. Barsky, Analyse p-adique et suites classiques de nombres, Sem. Loth. Comb. B05b (1981) 1-21.

P. Blasiak, K. A. Penson and A. I. Solomon, Dobinski-type relations and the log-normal distribution.

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

P. Flajolet, S. Gerhold and B. Salvy, On the non-holonomic character of logarithms, powers and the n-th prime function

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 109

Olivier Gerard, Re: Horse Race Puzzle.

M. Goebel, On the number of special permutation-invariant orbits and terms, in Applicable Algebra in Engin., Comm. and Comp. (AAECC 8), Volume 8, Number 6, 1997, pp. 505-509 (Lect. Notes Comp. Sci.)

Gottfried Helms, Discussion of a problem concerning summing of like powers

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 41

M. J. Kochanski, How many orders are there?.

J.-C. Novelli and J.-Y. Thibon, Polynomial realizations of some trialgebras, Proc. Formal Power Series and Algebraic Combinatorics 2006 (San-Diego, 2006)

K. A. Penson, P. Blasiak, G. Duchamp, A. Horzela and A. I. Solomon, Hierarchical Dobinski-type relations via substitution and the moment problem

Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.

S. Ramanujan, Notebook entry

N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 83-89.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 175, Eq. 5.2.6, 5.2.7.

Index entries for "core" sequences

Index entries for related partition-counting sequences

a(n) = Sum_{ k=1 to n} k! StirlingS2(n, k) (whereas the Bell numbers A000110(n) = Sum_{ k=1 to n} StirlingS2(n, k)).

E.g.f.: 1/(2-exp(x)). Recurrence: a(n)=Sum_{k>0} binomial(n, k)*a(n-k), a(0)=1.

The e.g.f. y(x) satisfies y' = 2y^2 - y.

a(n) is asymptotic to (1/2)*n!*log_2(e)^(n+1), where log_2(e) = 1.442695... [Wilf]

For n >= 1, a(n) = (n!/2) * Sum from k=-infinity to infinity of (log(2) + 2 pi i k)^(-n-1) - from Dean Hickerson (dean.hickerson(AT)yahoo.com)

a(n) = ((x*d/dx)^n)(1/(2-x)) evaluated at x=1. - Karol A. Penson (penson(AT)lptl.jussieu.fr), Sep 24 2001

For n>=1, a(n) = sum(k>=1, (k-1)^n/2^k) = A000629(n)/2. - Benoit Cloitre (benoit7848c(AT)orange.fr), Sep 08 2002

Value of the n-th Eulerian polynomial (cf. A008292) at x=2. - Vladeta Jovovic (vladeta(AT)eunet.rs), Sep 26 2003

a(n) = A076726(n)/2.

a(n)=sum{k=0..n, (-1)^k*k!*S2(n+1, k+1)(1+(-1)^k)/2}; - Paul Barry (pbarry(AT)wit.ie), Apr 20 2005

a(n) + a(n+1) = 2*A005649(n) . - Philippe DELEHAM, May 16 2005 - Thomas Wieder (wieder.thomas(AT)t-online.de), May 18 2005

Equals inverse binomial transform of A000629. - Gary W. Adamson (qntmpkt(AT)yahoo.com), May 30 2005

First Eulerian transform of the powers of 2 [A000079]. See A000142 for definition of FET. - Ross La Haye (rlahaye(AT)new.rr.com), Feb 14 2005

a(n) = sum^{k=0}^n k!*( Stirling2(n+2,k+2) - Stirling2(n+1, k+2) ). - Micha Hofri (hofri(AT)wpi.edu), Jul 01 2006

Recurrence: 2a(n)=(a+1)^n where superscripts are converted to subscripts after binomial expansion - reminiscent of Bernoulli numbers' B_n=(B+1)^n - Martin Kochanski (mjk(AT)cardbox.com), May 10 2007

a(n) = (-1)^n * n!*Laguerre(n,P((.),2)), umbrally, where P(j,t) are the polynomials in A131758. - Tom Copeland (tcjpn(AT)msn.com), Sep 27 2007

Formula in terms of the hypergeometric function, in Maple notation: a(n)=hypergeom([2,2...2],[1,1...1],1/2)/4, n=1,2..., where in the hypergeometric function there are n upper parameters all equal to 2 and n-1 lower parameters all equal to 1 and the argument is equal to 1/2. Example: a(4)=evalf(hypergeom([2,2,2,2],[1,1,1],1/2)/4)=75 - Karol A. Penson (penson(AT)lptl.jussieu.fr), Oct 04 2007

a(n)=Sum_{k, 0<=k<=n} A131689(n,k). [From Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Nov 03 2008]

Contribution from Peter Bala (pbala(AT)talktalk.net), Jul 01 2009: (Start)

ANALOGY WITH THE BERNOULLI NUMBERS.

We enlarge upon the above comment of M. Kochanski.

The Bernoulli polynomials B_n(x), n = 0,1,..., are given by the formula

(1)... B_n(x) := sum {k = 0..n} binomial(n,k)*B(k)*x^(n-k),

where B(n) denotes the sequence of Bernoulli numbers B(0) = 1,

B(1) = -1/2, B(2) = 1/6, B(3) = 0, ....

By analogy, we associate with the present sequence an Appell sequence

of polynomials {P_n(x)}n>=0 defined by

(2)... P_n(x) := sum {k = 0..n} binomial(n,k)*a(k)*x^(n-k).

These polynomials have similar properties to the Bernoulli polynomials.

The first few values are P_0(x) = 1, P_1(x) = x + 1,

P_2(x) = x^2 + 2*x + 3, P_3(x) = x^3 + 3*x^2 + 9*x + 13 and

P_4(x) = x^4 + 4*x^3 + 18*x^2 + 52*x + 75. See A154921 for the

triangle of coefficients of these polynomials.

The e.g.f. for this polynomial sequence is

(3)... exp(x*t)/(2 - exp(t)) = 1 + (x + 1)*t + (x^2 + 2*x + 3)*t^2/2!

+ ....

The polynomials satisfy the difference equation

(4)... 2*P_n(x - 1) - P_n(x) = (x - 1)^n,

and so may be used to evaluate the weighted sums of powers of integers

(1/2)*1^m + (1/2)^2*2^m + (1/2)^3*3^m + ... + (1/2)^(n-1)*(n-1)^m

via the formula

(5)... sum {k = 1..n-1} (1/2)^k*k^m = 2*P_m(0) - (1/2)^(n-1)*P_m(n),

analogous to the evaluation of the sums 1^m + 2^m + ... + (n-1)^m in

terms of Bernoulli polynomials.

This last result can be generalised to

(6)... sum {k=1..n-1} (1/2)^k*(k+x)^m = 2*P_m(x)-(1/2)^(n-1)*P_m(x+n).

For more properties of the polynomials P_n(x) refer to A154921.

For further information on weighted sums of powers of integers and

the associated polynomial sequences see A162312.

The present sequence also occurs in the evaluation of another sum of

powers of integers. Define

(7)... S_m(n) := sum {k = 1..n-1} (1/2)^k*((n-k)*k)^m, m = 1,2,....

Then

(8)... S_m(n) = (-1)^m *[2*Q_m(-n) - (1/2)^(n-1)*Q_m(n)],

where Q_m(x) are polynomials in x given by

(9)... Q_m(x) = sum {k = 0..m} a(m+k)*binomial(m,k)*x^(m-k).

The first few values are Q_1(x) = x + 3, Q_2(x) = 3*x^2 + 26*x + 75

and Q_3(x) = 13*x^3 + 225*x^2 + 1623*x + 4683.

For example, m = 2 gives

(10)... S_2(n) := sum {k = 1..n-1} (1/2)^k*((n-k)*k)^2

= 2*(3*n^2 - 26*n + 75) - (1/2)^(n-1)*(3*n^2 + 26*n + 75).

(End)

Let the points be labeled 1,2,3,... a(2) = 3: 1<2, 2<1, 1=2; a(3) = 13: 1<2<3, 1<3<2, ... (6 such), 1=2<3, 1=3<2, 2=3<1, 1<2=3, 2<1=3, 3<1=2, 1=2=3.

Three competitors can finish in 13 ways: 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,1,2; 3,2,1; 1,1,3; 2,2,1; 1,3,1; 2,1,2; 3,1,1; 1,2,2; 1,1,1.

A000670 := proc(n) option remember; local k; if n <=1 then 1 else add(binomial(n, k)*A000670(n-k), k=1..n); fi; end;

with(combstruct); SeqSetL := [S, {S=Sequence(U), U=Set(Z, card >= 1)}, labeled]; seq(count(SeqSetL, size=j), j=1..12);

with(combinat):a:=n->sum(sum((-1)^(k-i)*binomial(k, i)*i^n, i=0..n), k=0..n): seq(a(n), n=0..18); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 03 2007

Table[ PolyLog[ -z, 1/2 ] /2, {z, 1, 11} ] (from Wouter Meeussen)

Clear[a, n, m, k] a[0] = 1; a[n_] := a[n] = Sum[Binomial[n, k]*a[n - k], {k, 1, n}]; Table[a[n], {n, 0, 30}] - Roger L. Bagula and Gary W. Adamson (rlbagulatftn(AT)yahoo.com), Sep 13 2008

(PARI) a(n)=if(n<0, 0, n!*polcoeff(subst(1/(1-y), y, exp(x+x*O(x^n))-1), n))

Binomial transform of A052841.

Inverse binomial transform of A000629 - Joe Keane (jgk(AT)jgk.org).

Asymptotic to A034172. Cf. A053525, A002869, A004121, A004122.

For n>0, a(n)=A052882(n)/n.

Cf. A080253, A080254, A011782.

A052856(n)=1+a(n), if n>0.

First row of array A094416 (generalized ordered Bell numbers).

Diagonal of A135313. [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 19 2008]

A154921, A162312. [From Peter Bala (pbala(AT)talktalk.net), Jul 01 2009]

A163204 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Jul 23 2009]

A007047 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 04 2009]

Sequence in context: A074517 A007178 A034172 this_sequence A032036 A026072 A063646

Adjacent sequences: A000667 A000668 A000669 this_sequence A000671 A000672 A000673

easy,core,nonn,nice,new

N. J. A. Sloane (njas(AT)research.att.com).