login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000670 Fubini numbers: number of preferential arrangements of n labeled elements; or number of weak orders on n labeled elements; or number of ordered partitions of n.
(Formerly M2952 N1191)
191
1, 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563, 1622632573, 28091567595, 526858348381, 10641342970443, 230283190977853, 5315654681981355, 130370767029135901, 3385534663256845323, 92801587319328411133, 2677687796244384203115 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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

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, 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->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, 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, 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. 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, 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 (griffm(AT)essex.ac.uk), 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(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. - 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) counts 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) counts 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

REFERENCES

Connor Ahlbach, Jeremy Usatine and Nicholas Pippenger, Barred Preferential Arrangements, Electron. J. Combin., Volume 20, Issue 2 (2013), #P55

Jean-Christophe Aval, Adrien Boussicault, Philippe Nadeau, Tree-like Tableaux, Electronic Journal of Combinatorics, 20(4), 2013, #P34.

Mohammad K. Azarian, Geometric Series, Problem 329, Mathematics and Computer Education, Vol. 30, No. 1, Winter 1996, p. 101.  Solution published in Vol. 31, No. 2, Spring 1997, pp. 196-197.

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.

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.

N. G. de Bruijn, Enumerative combinatorial structures concerning structures, Nieuw Archief. voor Wisk., 11 (1963), 142-161; see p. 150.

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

Ayhan Dil and Veli Kurt, Polynomials related to harmonic numbers and evaluation of harmonic number series I, INTEGERS, 12 (2012), #A38. - From N. J. A. Sloane, Feb 08 2013

F. Foucaud, R. Klasing, P.J. Slater, Centroidal bases in graphs, arXiv preprint arXiv:1406.7490, 2014

A. S. Fraenkel and M. Mor, Combinatorial compression and partitioning of large dictionaries, Computer J., 26 (1983), 336-343. See Tables 4 and 5.

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

Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.

N. Khare, R. Lorentz, C. Yan, Bivariate Goncarov Polynomials and Integer Sequences, SCIENCE CHINA Mathematics, January 2014 Vol. 57 No. 1: doi: 10.1007/s11425-000-0000-0; http://www.math.tamu.edu/~cyan/Files/BivariateGP.pdf

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, 1973, Section 5.3.1, Problem 3.

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.

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.

P. Peart,  Hankel determinants via Stieltjes matrices. Proceedings of the Thirty-first Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2000). Congr. Numer. 144 (2000), 153-159.

Prodinger, Helmut. Ordered Fibonacci partitions. Canad. Math. Bull. 26 (1983), no. 3, 312--316. MR0703402 (84m:05012).  [See F_n on page 312. - N. J. A. Sloane, Apr 07 2014]

Ulrike Sattler, Decidable classes of formal power series with nice closure properties, Diplomarbeit im Fach Informatik, Univ. Erlangen - Nuernberg, Jul 27 1994

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.

J. van der Elsen, Black and White Transformations, Shaker Publishing, Maastricht, 2005, p. 18.

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.

Xu, Ai-Min and Cen, Zhong-Di, Some identities involving exponential functions and Stirling numbers and applications, J. Comput. Appl. Math. 260 (2014), 201-207.

LINKS

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

J.-C. Aval, V. Féray, J.-C. Novelli, J.-Y. Thibon, Quasi-symmetric functions as polynomial functions on Young diagrams, arXiv preprint arXiv:1312.2727, 2013

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

Paul Barry, Eulerian polynomials as moments, via exponential Riordan arrays, arXiv preprint arXiv:1105.3043, 2011

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

J. P. Barthelemy, An asymptotic equivalent for the number of total preorders on a finite set, Discrete Mathematics, 29(3):311-313, 1980.

F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.

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.

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

W. Y. C. Chen, A. Y. L. Dai and R. D. P. Zhou, Ordered Partitions Avoiding a Permutation of Length 3, arXiv preprint arXiv:1304.3187, 2013.

Mircea I. Cirnu, Determinantal formulas for sum of generalized arithmetic-geometric series, Boletin de la Asociacion Matematica Venezolana, Vol. XVIII, No. 1 (2011), p. 13.

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

Tyler Clark and Tom Richmond, The Number of Convex Topologies on a Finite Totally Ordered Set, 2013, to appear in Involve;

D. Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions. arXiv:math/0501052v2 [math.CA]

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 Gérard, Re: Horse Race Puzzle.

S. Giraudo, Combinatorial operads from monoids, arXiv preprint arXiv:1306.6938, 2013

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

W. S. Gray and M. Thitsa, System Interconnections and Combinatorial Integer Sequences, in: System Theory (SSST), 2013 45th Southeastern Symposium on, Date of Conference: 11-11 March 2013, Digital Object Identifier: 10.1109/SSST.2013.6524939.

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

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

M. E. Hoffman, Updown categories: Generating functions and universal covers, arXiv preprint arXiv:1207.1705, 2012.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 41

Svante Janson, Euler-Frobenius numbers and rounding, arXiv preprint arXiv:1305.3512, 2013

M. Jarocinski, B. Mackowiak, Online Appendix to "Granger-Causal-Priority and Choice of Variables in Vector Autoregressions", 2013.

Dongseok Kim, Young Soo Kwon, Jaeun Lee, Enumerations of finite topologies associated with a finite graph, arXiv preprint arXiv:1206.0550, 2012. See Th. 4.3. - From N. J. A. Sloane, Nov 09 2012

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

A. S. Koksal, Y. Pu, S. Srivastava, R. Bodik, J. Fisher and N. Piterman, Synthesis of Biological Models from Mutation Experiments, 2012.

A. Kumjian, D. Pask, A. Sims, M. F. Whittaker, Topological spaces associated to higher-rank graphs, arXiv preprint arXiv:1310.6100, 2013

E. Mendelson, Races with Ties, Math. Mag. 55 (1982), 170-175.

I. Mezo, Periodicity of the last digits of some combinatorial sequences, arXiv preprint arXiv:1308.1637, 2013

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

R. B. Nelsen and H. Schmidt, Jr., Chains in power sets, Math. Mag., 64 (1991), 23-31.

Mathilde Noual and Sylvain Sene, Towards a theory of modelling with Boolean automata networks-I. Theorisation and observations, arXiv preprint arXiv:1111.2077, 2011

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

J.-C. Novelli, J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962, 2014

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

Robert A. Proctor, Let's Expand Rota's Twelvefold Way For Counting Partitions!, arXiv:math.CO/0606404, Jan 05, 2007

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.

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

F. V. Weinstein, Notes on Fibonacci partitions, arXiv:math/0307150 [math.NT] (see page 9).

Eric Weisstein's World of Mathematics, Combination Lock

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

FORMULA

G.f.: A(x) = Sum_{n>=0} n!*x^n / Product_{k=1..n} (1-k*x). - Paul D. Hanna, Jul 20 2011

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

a(n)=sum(k=1 to n, binomial(n, k)*a(n-k) ), a(0)=1.

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

From Paul Barry, Mar 30 2010: (Start)

G.f.: 1/(1-x/(1-2x/(1-2x/(1-4x/(1-3x/(1-6x/(1-4x/(1-8x/(1-5x/(1-10x/(1-6x/(1-... (continued fraction);

Coefficients of continued fraction are given by floor((n+2)/2)*(3-(-1)^n)/2 (A029578(n+2)). (End)

G.f.: 1/(1-x-2x^2/(1-4x-8x^2/(1-7x-18x^2/(1-10x-32x^2/(1../(1-(3n+1)x-2(n+1)^2x^2/(1-... (continued fraction). - Paul Barry, Jun 17 2010

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

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

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

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

Value of the n-th Eulerian polynomial (cf. A008292) at x=2. - Vladeta Jovovic, 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, Apr 20 2005

a(n) + a(n+1) = 2*A005649(n). - Philippe Deléham, May 16 2005 - Thomas Wieder, May 18 2005

Equals inverse binomial transform of A000629. - Gary W. Adamson, May 30 2005

First Eulerian transform of the powers of 2 [A000079]. See A000142 for definition of FET. - Ross La Haye, 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, 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, Oct 04 2007

a(n)=Sum_{k, 0<=k<=n} A131689(n,k). - Philippe Deléham, Nov 03 2008

The adjusted e.g.f. A(x) := 1/(2-exp(x))-1, has inverse function A(x)^-1 = int {t = 0..x} 1/((1+t)*(1+2*t)). Applying [Dominici, Theorem 4.1] to invert the integral yields a formula for a(n): Let f(x) = (1+x)*(1+2*x). Let D be the operator f(x)*d/dx. Then a(n) = D^(n-1)(f(x)) evaluated at x = 0. Compare with A050351. - Peter Bala, Aug 31 2011

From Peter Bala, 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 generalized 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)

a(n)=A074206(q_1*q_2*...*q_n), where {q_i} are distinct primes. - Vladimir Shevelev, Aug 05 2011

a(n) is always odd. For odd prime p and n >= 1, a((p-1)*n) = 0 (mod p). - Peter Bala, Sep 18 2013

a(n) = D^n(1/(1-x)) evaluated at x = 0, where D is the operator (1+x)*d/dx. Cf. A052801. Row sums of A019538. - Peter Bala, Nov 25 2011

a(0) = 1, a(n) = Sum(k=1..n)[C(n,k)*a(n-k)], where C(n,k) is a binomial coefficient. - Jack van der Elsen, Mar 27 2012

G.f.: 1+x/(1-x+2x(x-1)/(1+3x(2x-1)/(1+4x(3x-1)/(1+5x(4x-1)/(1+... or 1+x/(U(0)-x), U(k)=1+(k+2)(kx+x-1)/U(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 30 2011

E.g.f.: 1 + x/(G(0)-2*x) where G(k)= x + k + 1 - x*(k+1)/G(k+1); (continued fraction, Euler's 1st kind, 1-step). - Sergei N. Gladkovskii, Jul 11 2012

E.g.f. (2 - 2*x)*(1 - 2*x^3/(8*x^2 - 4*x + (x^2 - 4*x + 2)*G(0)))/(x^2 - 4*x + 2) where G(k)=  k^2 + k*(x+4) + 2*x + 3 - x*(k+1)*(k+3)^2 /G(k+1) ; (continued fraction, Euler's 1st kind, 1-step). - Sergei N. Gladkovskii, Oct 01 2012

G.f.: 1 + x/G(0) where G(k) = 1 - 3*x*(k+1) - 2*x^2*(k+1)*(k+2)/G(k+1); (continued fraction). - Sergei N. Gladkovskii, Jan 11 2013.

G.f.: 1/G(0) where G(k) = 1 - x*(k+1)/( 1 - 2*x*(k+1)/G(k+1) ); (continued fraction ). - Sergei N. Gladkovskii, Mar 23 2013

G.f.: 1 + x/Q(0), where Q(k) = 1 - 3*x*(2*k+1) - 2*x^2*(2*k+1)*(2*k+2)/( 1 - 3*x*(2*k+2) - 2*x^2*(2*k+2)*(2*k+3)/Q(k+1) ) ; (continued fraction). - Sergei N. Gladkovskii, Sep 23 2013

G.f.: T(0)/(1-x), where T(k) = 1 - 2*x^2*(k+1)^2/( 2*x^2*(k+1)^2 - (1-x-3*x*k)*(1-4*x-3*x*k)/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 14 2013

EXAMPLE

Let the points be labeled 1,2,3,...

a(2) = 3: 1<2, 2<1, 1=2.

a(3) = 13 from the 13 arrangements

1<2<3,

1<3<2,

2<1<3,

2<3<1,

3<1<2,

3<2<1,

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.

a(3) = 13. The 13 plane increasing 0-1-2 trees on 3 vertices, where vertices of outdegree 1 come in 3 colors and vertices of outdegree 2 come in 2 colors, are:

........................................................

........1 (x3 colors).....1(x2 colors)....1(x2 colors)..

........|................/.\............./.\............

........2 (x3 colors)...2...3...........3...2...........

........|...............................................

........3...............................................

......====..............====............====............

.Totals 9......+..........2....+..........2....=..13....

........................................................

a(4) = 75. The 75 non-plane increasing 0-1-2 trees on 4 vertices, where vertices of outdegree 1 come in 3 colors and vertices of outdegree 2 come in 4 colors, are:

...............................................................

.....1 (x3).....1(x4).......1(x4).....1(x4)........1(x3).......

.....|........./.\........./.\......./.\...........|...........

.....2 (x3)...2...3.(x3)..3...2(x3).4...2(x3)......2(x4).......

.....|.............\...........\.........\......../.\..........

.....3.(x3).........4...........4.........3......3...4.........

.....|.........................................................

.....4.........................................................

....====......=====........====......====.........====.........

Tots 27....+....12......+...12....+...12.......+...12...=...75.

From Joerg Arndt, Mar 18 2014: (Start)

The a(3) = 13 strings on the alphabet {1,2,3} containing all letters up to the maximal value appearing and the corresponding ordered set partitions are:

01:  [ 1 1 1 ]     { 1, 2, 3 }

02:  [ 1 1 2 ]     { 1, 2 } < { 3 }

03:  [ 1 2 1 ]     { 1, 3 } < { 2 }

04:  [ 2 1 1 ]     { 2, 3 } < { 1 }

05:  [ 1 2 2 ]     { 1 } < { 2, 3 }

06:  [ 2 1 2 ]     { 2 } < { 1, 3 }

07:  [ 2 2 1 ]     { 3 } < { 1, 2 }

08:  [ 1 2 3 ]     { 1 } < { 2 } < { 3 }

09:  [ 1 3 2 ]     { 1 } < { 3 } < { 2 }

00:  [ 2 1 3 ]     { 2 } < { 1 } < { 3 }

11:  [ 2 3 1 ]     { 3 } < { 1 } < { 2 }

12:  [ 3 1 2 ]     { 2 } < { 3 } < { 1 }

13:  [ 3 2 1 ]     { 3 } < { 2 } < { 1 }

(End)

MAPLE

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->add(add((-1)^(k-i)*binomial(k, i)*i^n, i=0..n), k=0..n): seq(a(n), n=0..18); # Zerinvary Lajos, Jun 03 2007

MATHEMATICA

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

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, Sep 13 2008 *)

t = 30; Range[0, t]! CoefficientList[Series[1/(2 - Exp[x]), {x, 0, t}], x] (* Vincenzo Librandi, Mar 16 2014 *)

PROG

(PARI) {a(n) = if( n<0, 0, n! * polcoeff( subst( 1/(1 - y), y, exp(x + x*O(x^n)) - 1), n))} /* Michael Somos, Mar 04, 2004 */

(Maxima) makelist(sum(stirling2(n, k)*k!, k, 0, n), n, 0, 12); /* Emanuele Munarini, Jul 07 2011 */

(Maxima) a[0]:1$ a[n]:=sum(binomial(n, k)*a[n-k], k, 1, n)$ A000670(n):=a[n]$ makelist(A000670(n), n, 0, 30); /* Martin Ettl, Nov 05 2012 */

(PARI) Vec(serlaplace(1/(2-exp('x+O('x^66))))) /* Joerg Arndt, Jul 10 2011 */

(PARI) {a(n)=polcoeff(sum(m=0, n, m!*x^m/prod(k=1, m, 1-k*x+x*O(x^n))), n)} /* Paul D. Hanna, Jul 20 2011 */

(Sage)

@CachedFunction

def A000670(n) : return 1 if n == 0 else add(A000670(k)*binomial(n, k) for k in range(n))

[A000670(n) for n in (0..20)] # Peter Luschny, Jul 14 2012

(Haskell)

a000670 n = a000670_list !! n

a000670_list = 1 : f [1] (map tail $ tail a007318_tabl) where

   f xs (bs:bss) = y : f (y : xs) bss where y = sum $ zipWith (*) xs bs

-- Reinhard Zumkeller, Jul 26 2014

CROSSREFS

See A240763 for a list of the actual preferential arrangements themselves.

A000629, A000670, A002050, A032109, A052856, A076726 are all more-or-less the same sequence. - N. J. A. Sloane, Jul 04 2012

Binomial transform of A052841.

Inverse binomial transform of A000629.

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

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

Cf. A080253, A080254, A011782, A154921, A162312, A163204, A007047, A002144.

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

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

Diagonal of A135313.

A000629(n) = 2*a(n) - 0^n.

Row sums of triangle A208744.

Row 0 of array in A226513.

A217389 and A239914 give partial sums.

Cf. A048144, A242280.

Cf. A007318.

Sequence in context: A007178 A173990 A034172 * A032036 A222427 A026072

Adjacent sequences:  A000667 A000668 A000669 * A000671 A000672 A000673

KEYWORD

nonn,core,nice,easy

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified November 20 17:58 EST 2014. Contains 249754 sequences.