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 2 times 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

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.

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

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.

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

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

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

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(AT)math.ucdavis.edu)

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

Bell numbers (A000110) are Sum {n brace k}; these numbers are Sum k! {n brace k}.

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

a(n) = Sum from k=1 to n of k! StirlingS2(n, k)

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

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

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

E.g.f.: 1/(2-exp(x)). 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.

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, (-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

Recurrence : a(n+1) = 1 + sum { j=1, n, binomial(n+1, j)*a(j) } - Jon Perry (perry(AT)globalnet.co.uk), Apr 25 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

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)

(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).

Adjacent sequences: A000667 A000668 A000669 this_sequence A000671 A000672 A000673

Sequence in context: A074517 A007178 A034172 this_sequence A032036 A026072 A063646

easy,core,nonn,nice

njas