

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)


216



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^(n1) (cf. A011782).
For n>0, a(n) is the number of elements in the Coxeter complex of type A_{n1}. 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(n1) = [1,0,2,0,24,0,...] is a(n1) = [1,1,3,13,75,...].
Stirling transform of A005212(n1) = [0,1,0,6,0,120,0,...] is a(n1) = [0,1,3,13,75,...].
(End)
Unreduced denominators in convergent to log(2) = Lim_{n>infinity} n*a(n1)/a(n).
a(n) is congruent to a(n+(p1)p^(h1)) (mod p^h) for n>=h (see Barsky).
StirlingBernoulli transform of 1/(1x^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 ith partition of n, d(i) = the number of different parts of the ith partition of n, p(j,i) = the jth part of the ith partition of n, m(i,j) = multiplicity of the jth part of the ith 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 matrixinversion occurring in a sumoflikepowers 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 mth polynomial defining the mth 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!/2A^(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(n1) ).  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,...,k1. 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_{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/(2exp(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/(2exp(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 planeincreasing 012 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 nonplaneincreasing 012 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 (UDs), (ii) no UUDDs, 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


REFERENCES

Connor Ahlbach, Jeremy Usatine and Nicholas Pippenger, Barred Preferential Arrangements, Electron. J. Combin., Volume 20, Issue 2 (2013), #P55.
JeanChristophe Aval, Adrien Boussicault, and Philippe Nadeau, Treelike 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. 196197.
N. L. Biggs et al., Graph Theory 17361936, Oxford, 1976, p. 44 (P(x)).
Kenneth S. Brown, Buildings, SpringerVerlag, 1988
A. Cayley, On the theory of the analytical forms called trees II, Phil. Mag. 18 (1859), 374378 = Math. Papers Vol. 4, pp. 112115.
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, SpringerVerlag.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 228.
N. G. de Bruijn, Enumerative combinatorial structures concerning structures, Nieuw Archief. voor Wisk., 11 (1963), 142161; 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.
F. Fauvet, L. Foissy, D. Manchon, The Hopf algebra of finite topologies and mould composition, arXiv preprint arXiv:1503.03820, 2015
A. S. Fraenkel and M. Mor, Combinatorial compression and partitioning of large dictionaries, Computer J., 26 (1983), 336343. See Tables 4 and 5.
P. J. Freyd, On the size of Heyting semilattices, preprint, 2002.
S. Getu et al., How to guess a generating function, SIAM J. Discrete Math., 5 (1992), 497499.
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. AddisonWesley, Reading, MA, 2nd Ed., 1994, exercise 7.44 (pp. 378, 571).
Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.
D. E. Knuth, The Art of Computer Programming. AddisonWesley, 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), 517532.
P. A. MacMahon, Yoketrains and multipartite compositions in connexion with the analytical forms called "trees", Proc. London Math. Soc. 22 (1891), 330346; reprinted in Coll. Papers I, pp. 600616.
M. Muresan, Generalized Fubini numbers. Stud. Cerc. Mat. 37 (1985), no. 1, pp. 7076.
P. Peart, Hankel determinants via Stieltjes matrices. Proceedings of the Thirtyfirst Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2000). Congr. Numer. 144 (2000), 153159.
Helmut Prodinger. Ordered Fibonacci partitions. Canad. Math. Bull. 26 (1983), no. 3, 312316. MR0703402 (84m:05012). [See F_n on page 312.  N. J. A. Sloane, Apr 07 2014]
S. Ramanujan, Notebooks, Tata Institute of Fundamental Research, Bombay 1957 Vol. 1, see page 19.
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, 147152.
H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 147.
AiMin Xu and ZhongDi Cen, Some identities involving exponential functions and Stirling numbers and applications, J. Comput. Appl. Math. 260 (2014), 201207.


LINKS

N. J. A. Sloane and Alois P. Heinz, Table of n, a(n) for n = 0..424 (first 101 terms from N. J. A. Sloane)
J.C. Aval, V. Féray, J.C. Novelli, J.Y. Thibon, Quasisymmetric 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. 559562.
Paul Barry, Eulerian polynomials as moments, via exponential Riordan arrays, arXiv preprint arXiv:1105.3043, 2011
D. Barsky, Analyse padique et suites classiques de nombres, Sem. Loth. Comb. B05b (1981) 121.
J. P. Barthelemy, An asymptotic equivalent for the number of total preorders on a finite set, Discrete Mathematics, 29(3):311313, 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. 2448.
P. Blasiak, K. A. Penson and A. I. Solomon, Dobinskitype relations and the lognormal 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 quasiordres sur un ensemble fini, Math. Sci. Humaines, No. 62 (1978), 6180.
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 arithmeticgeometric 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), 217231.
Tyler Clark and Tom Richmond, The Number of Convex Topologies on a Finite Totally Ordered Set, 2013, to appear in Involve;
Pierluigi Contucci, Emanuele Panizzi, Federico RicciTersenghi, and Alina Sîrbu, A new dimension for democracy: egalitarianism in the rank aggregation problem, arXiv:1406.7642, 2014.
D. Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions. arXiv:math/0501052v2 [math.CA]
V. Féray, Cyclic inclusionexclusion, arXiv preprint arXiv:1410.1772, 2014
P. Flajolet, S. Gerhold and B. Salvy, On the nonholonomic character of logarithms, powers and the nth prime function
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 109
F. Foucaud, R. Klasing, and P.J. Slater, Centroidal bases in graphs, arXiv preprint arXiv:1406.7490, 2014
W. Gatterbauer and D. Suciu, Approximate Lifted Inference with Probabilistic Databases, arXiv preprint arXiv:1412.1069, 2014
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 permutationinvariant orbits and terms, in Applicable Algebra in Engin., Comm. and Comp. (AAECC 8), Volume 8, Number 6, 1997, pp. 505509 (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: 1111 March 2013, Digital Object Identifier: 10.1109/SSST.2013.6524939.
O. A. Gross, Preferential arrangements, Amer. Math. Monthly, 69 (1962), 48.
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 [broken link]
Svante Janson, EulerFrobenius numbers and rounding, arXiv preprint arXiv:1305.3512, 2013
M. Jarocinski and B. Mackowiak, Online Appendix to "GrangerCausalPriority and Choice of Variables in Vector Autoregressions", 2013.
N. Khare, R. Lorentz, and C. Yan, Bivariate Goncarov Polynomials and Integer Sequences, Science China Mathematics, January 2014 Vol. 57 No. 1; doi: 10.1007/s1142500000000.
Dongseok Kim, Young Soo Kwon, and 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
D. E. Knuth, J. Riordan, and N. J. A. Sloane, Correspondence, 1970.
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.
Germain Kreweras, Une dualité élémentaire souvent utile dans les problèmes combinatoires<\a>, Mathématiques et Sciences Humaines 3 (1963): 3141.
A. Kumjian, D. Pask, A. Sims, and M. F. Whittaker, Topological spaces associated to higherrank graphs, arXiv preprint arXiv:1310.6100, 2013
E. Mendelson, Races with Ties, Math. Mag. 55 (1982), 170175.
I. Mezo, Periodicity of the last digits of some combinatorial sequences, arXiv preprint arXiv:1308.1637, 2013
I. Mezo and A. Baricz, On the generalization of the Lambert W function with applications in theoretical physics, arXiv preprint arXiv:1408.3999, 2014
M. Mor and A. S. Fraenkel, Cayley permutations, Discrete Math., 48 (1984), 101112.
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167176. [Annotated, scanned copy]
R. B. Nelsen and H. Schmidt, Jr., Chains in power sets, Math. Mag., 64 (1991), 2331.
Mathilde Noual and Sylvain Sene, Towards a theory of modelling with Boolean automata networksI. 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 (SanDiego, 2006)
J.C. Novelli and J.Y. Thibon, Hopf Algebras of mpermutations,(m+1)ary trees, and mparking functions, arXiv preprint arXiv:1403.5962, 2014
OEIS Wiki, Sorting numbers
K. A. Penson, P. Blasiak, G. Duchamp, A. Horzela and A. I. Solomon, Hierarchical Dobinskitype 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), 8389.
D. J. Velleman and G. S. Call, Permutations and combination locks, Math. Mag., 68 (1995), 243253.
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 partitioncounting sequences


FORMULA

a(n) = Sum_{k=1..n} k! StirlingS2(n, k) (whereas the Bell numbers A000110(n) = Sum_{k=1..n} StirlingS2(n, k)).
E.g.f.: 1/(2exp(x)).
a(n) = Sum_{k=1..n} binomial(n, k)*a(nk), a(0) = 1.
The e.g.f. y(x) satisfies y' = 2*y^2  y.
a(n) = A052856(n)  1, if n>0.
a(n) = A052882(n)/n, if n>0.
a(n) = A076726(n)/2.
a(n) is asymptotic to (1/2)*n!*log_2(e)^(n+1), where log_2(e) = 1.442695... [Barthelemy80, Wilf90].
For n >= 1, a(n) = (n!/2) * Sum_{k=infinity..infinity} of (log(2) + 2 Pi i k)^(n1).  Dean Hickerson
a(n) = ((x*d/dx)^n)(1/(2x)) evaluated at x=1.  Karol A. Penson, Sep 24 2001
For n>=1, a(n) = Sum_{k>=1} (k1)^n/2^k = A000629(n)/2.  Benoit Cloitre, Sep 08 2002
Value of the nth Eulerian polynomial (cf. A008292) at x=2.  Vladeta Jovovic, Sep 26 2003
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} (1)^k*k!*Stirling2(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
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 n1 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..n} A131689(n,k).  Philippe Deléham, Nov 03 2008
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^(nk),
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^(nk).
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)^(n1)*(n1)^m
via the formula
(5)... Sum_{k=1..n1} (1/2)^k*k^m = 2*P_m(0)  (1/2)^(n1)*P_m(n),
analogous to the evaluation of the sums 1^m + 2^m + ... + (n1)^m in terms of Bernoulli polynomials.
This last result can be generalized to
(6)... Sum_{k=1..n1} (1/2)^k*(k+x)^m = 2*P_m(x)(1/2)^(n1)*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..n1} (1/2)^k*((nk)*k)^m, m = 1,2,....
Then
(8)... S_m(n) = (1)^m *[2*Q_m(n)  (1/2)^(n1)*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^(mk).
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..n1} (1/2)^k*((nk)*k)^2
= 2*(3*n^2  26*n + 75)  (1/2)^(n1)*(3*n^2 + 26*n + 75).
(End)
G.f.: 1/(1x/(12x/(12x/(14x/(13x/(16x/(14x/(18x/(15x/(110x/(16x/(1... (continued fraction); coefficients of continued fraction are given by floor((n+2)/2)*(3(1)^n)/2 (A029578(n+2)).  Paul Barry, Mar 30 2010
G.f.: 1/(1x2x^2/(14x8x^2/(17x18x^2/(110x32x^2/(1../(1(3n+1)x2(n+1)^2x^2/(1... (continued fraction).  Paul Barry, Jun 17 2010
G.f.: A(x) = Sum_{n>=0} n!*x^n / Product_{k=1..n} (1k*x).  Paul D. Hanna, Jul 20 2011
a(n)=A074206(q_1*q_2*...*q_n), where {q_i} are distinct primes.  Vladimir Shevelev, Aug 05 2011
The adjusted e.g.f. A(x) := 1/(2exp(x))1, has inverse function A(x)^1 = Integral_{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^(n1)(f(x)) evaluated at x = 0. Compare with A050351.  Peter Bala, Aug 31 2011
G.f.: 1+x/(1x+2x(x1)/(1+3x(2x1)/(1+4x(3x1)/(1+5x(4x1)/(1+... or 1+x/(U(0)x), U(k)=1+(k+2)(kx+x1)/U(k+1); (continued fraction).  Sergei N. Gladkovskii, Oct 30 2011
a(n) = D^n(1/(1x)) evaluated at x = 0, where D is the operator (1+x)*d/dx. Cf. A052801.  Peter Bala, Nov 25 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, 1step).  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, 1step).  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
a(n) is always odd. For odd prime p and n >= 1, a((p1)*n) = 0 (mod p).  Peter Bala, Sep 18 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)/(1x), where T(k) = 1  2*x^2*(k+1)^2/( 2*x^2*(k+1)^2  (1x3*x*k)*(14*x3*x*k)/T(k+1) ); (continued fraction).  Sergei N. Gladkovskii, Oct 14 2013
a(n) = log(2)* Integral_{x>=0} floor(x)^n * 2^(x) dx.  Peter Bala, Feb 06 2015
For n > 0, a(n) = Re(polygamma(n, i log(2)/(2 Pi))/(2 Pi i)^(n+1))  n!/(2 log(2)^(n+1)).  Vladimir Reshetnikov, Oct 15 2015


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 012 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 nonplane increasing 012 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(nk), 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)^(ki)*binomial(k, i)*i^n, i=0..n), k=0..n): seq(a(n), n=0..18); # Zerinvary Lajos, Jun 03 2007
a := n > add(combinat:eulerian1(n, k)*2^k, k=0..n): # Peter Luschny, Jan 02 2015
a := n > (polylog(n, 1/2)+`if`(n=0, 1, 0))/2: seq(round(evalf(a(n), 32)), n=0..20); # Peter Luschny, Nov 03 2015


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 *)
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ 1 / (2  Exp@x), {x, 0, n}]]; (* Michael Somos, Jun 19 2015 *)
Table[Sum[k^n/2^(k+1), {k, 0, Infinity}], {n, 0, 20}] (* Vaclav Kotesovec, Jun 26 2015 *)


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[nk], k, 1, n)$ A000670(n):=a[n]$ makelist(A000670(n), n, 0, 30); /* Martin Ettl, Nov 05 2012 */
(PARI) Vec(serlaplace(1/(2exp('x+O('x^66))))) /* Joerg Arndt, Jul 10 2011 */
(PARI) {a(n)=polcoeff(sum(m=0, n, m!*x^m/prod(k=1, m, 1k*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, this sequence, A002050, A032109, A052856, A076726 are all moreorless the same sequence.  N. J. A. Sloane, Jul 04 2012
Binomial transform of A052841. Inverse binomial transform of A000629.
Asymptotic to A034172.
Cf. A002144, A002869, A004121, A004122, A007047, A007318, A048144, A053525, A080253, A080254, A011782, A154921, A162312, A163204, A242280, A261959.
Row r=1 of A094416. Row 0 of array in A226513. Row n=1 of A262809.
Main diagonal of A135313 and A261781.
Row sums of triangles A019538 and A208744.
A217389 and A239914 give partial sums.
Sequence in context: A007178 A173990 A034172 * A032036 A222427 A026072
Adjacent sequences: A000667 A000668 A000669 * A000671 A000672 A000673


KEYWORD

nonn,core,nice,easy,changed


AUTHOR

N. J. A. Sloane


STATUS

approved



