|
%I M2952 N1191 #783 Apr 21 2024 21:06:48
%S 1,1,3,13,75,541,4683,47293,545835,7087261,102247563,1622632573,
%T 28091567595,526858348381,10641342970443,230283190977853,
%U 5315654681981355,130370767029135901,3385534663256845323,92801587319328411133,2677687796244384203115
%N 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].
%C Number of ways n competitors can rank in a competition, allowing for the possibility of ties.
%C Also number of asymmetric generalized weak orders on n points.
%C Also called the ordered Bell numbers.
%C A weak order is a relation that is transitive and complete.
%C 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]
%C If the points are unlabeled then the answer is a(0) = 1, a(n) = 2^(n-1) (cf. A011782).
%C 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
%C Also number of labeled (1+2)-free posets. - Detlef Pauly, May 25 2003
%C 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
%C From _Michael Somos_, Mar 04 2004: (Start)
%C Stirling transform of A007680(n) = [3,10,42,216,...] gives [3,13,75,541,...].
%C Stirling transform of a(n) = [1,3,13,75,...] is A083355(n) = [1,4,23,175,...].
%C Stirling transform of A000142(n) = [1,2,6,24,120,...] is a(n) = [1,3,13,75,...].
%C Stirling transform of A005359(n-1) = [1,0,2,0,24,0,...] is a(n-1) = [1,1,3,13,75,...].
%C Stirling transform of A005212(n-1) = [0,1,0,6,0,120,0,...] is a(n-1) = [0,1,3,13,75,...].
%C (End)
%C Unreduced denominators in convergent to log(2) = lim_{n->infinity} n*a(n-1)/a(n).
%C a(n) is congruent to a(n+(p-1)p^(h-1)) (mod p^h) for n >= h (see Barsky).
%C Stirling-Bernoulli transform of 1/(1-x^2). - _Paul Barry_, Apr 20 2005
%C 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
%C 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
%C 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
%C 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
%C 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
%C List partition transform (see A133314) of (1,-1,-1,-1,...). - _Tom Copeland_, Oct 24 2007
%C First column of A154921. - _Mats Granvik_, Jan 17 2009
%C 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
%C Starting (1, 3, 13, 75, ...) = row sums of triangle A163204. - _Gary W. Adamson_, Jul 23 2009
%C Equals double inverse binomial transform of A007047: (1, 3, 11, 51, ...). - _Gary W. Adamson_, Aug 04 2009
%C 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
%C Hankel transform is A091804. - _Paul Barry_, Mar 30 2010
%C 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
%C 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
%C 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
%C 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
%C 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
%C 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
%C 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
%C 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
%C From _David L. Harden_, Apr 09 2017: (Start)
%C 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.
%C 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).
%C 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)
%C 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
%C From _A.H.M. Smeets_, Nov 17 2018: (Start)
%C 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 easely seen by replacing
%C "{i}" by "x_i := expression_i(x_1, ..., x_n)",
%C "{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),
%C similar for simultaneous assignments to more variables, and
%C "<" 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.
%C From this also the number of different mean definitions as obtained by iteration of n different mean functions on n initial values. Examples:
%C the AGM(x1,x2) = AGM(x2,x1) is represented by {arithmetic mean, geometric mean}, i.e., simultaneous assignment in any iteration step;
%C Archimedes's scheme (for Pi) is represented by {geometric mean} < {harmonic mean}, i.e., sequential assignment in any iteration step;
%C the geometric mean of two values can also be observed by {arithmetic mean, harmonic mean};
%C 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.
%C By applying power means (also called Holder means) this can be extended to any value of n. (End)
%C 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
%C 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)
%C From _Peter Bala_, Jul 08 2022: (Start)
%C 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.
%C 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)
%C 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
%D 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.
%D Norman Biggs, E. Keith Lloyd and Robin J. Wilson, Graph Theory 1736-1936, Oxford, 1976, p. 44 (P(x)).
%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 183 (see R_n).
%D Kenneth S. Brown, Buildings, Springer-Verlag, 1988.
%D Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 228.
%D Jean-Marie De Koninck, Ces nombres qui nous fascinent, Entry 13, pp 4, Ellipses, Paris 2008.
%D P. J. Freyd, On the size of Heyting semi-lattices, preprint, 2002.
%D Ian P. Goulden and David M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.
%D Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd Ed., 1994, exercise 7.44 (pp. 378, 571).
%D Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.
%D Donald E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, 1973, Section 5.3.1, Problem 3.
%D M. Muresan, Generalized Fubini numbers, Stud. Cerc. Mat., Vol. 37, No. 1 (1985), pp. 70-76.
%D Paul 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.
%D S. Ramanujan, Notebooks, Tata Institute of Fundamental Research, Bombay 1957 Vol. 1, see page 19.
%D Ulrike Sattler, Decidable classes of formal power series with nice closure properties, Diplomarbeit im Fach Informatik, Univ. Erlangen - Nuernberg, Jul 27 1994.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D Richard P. Stanley, Enumerative Combinatorics, Wadsworth, Vol. 1, 1986; see Example 3.15.10, p. 146.
%D Jack van der Elsen, Black and White Transformations, Shaker Publishing, Maastricht, 2005, p. 18.
%H Alois P. Heinz, <a href="/A000670/b000670.txt">Table of n, a(n) for n = 0..424</a> (first 101 terms from N. J. A. Sloane)
%H Connor Ahlbach, Jeremy Usatine, and Nicholas Pippenger, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i2p55">Barred Preferential Arrangements</a>, Electron. J. Combin., Volume 20, Issue 2 (2013), #P55.
%H Jean-Christophe Aval, Valentin Féray, Jean-Christophe Novelli, and Jean-Yves Thibon, <a href="http://arxiv.org/abs/1312.2727">Quasi-symmetric functions as polynomial functions on Young diagrams</a>, arXiv preprint arXiv:1312.2727 [math.CO], 2013.
%H Jean-Christophe Aval, Adrien Boussicault, and Philippe Nadeau, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i4p34">Tree-like Tableaux</a>, Electronic Journal of Combinatorics, Vol. 20, No. 4 (2013), #P34.
%H Ralph W. Bailey, <a href="http://dx.doi.org/10.1007/s003550050123">The number of weak orderings of a finite set</a>, Social Choice and Welfare, Vol. 15 (1998), pp. 559-562.
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Barry4/barry122.html">Exponential Riordan Arrays and Permutation Enumeration</a>, J. Int. Seq., Vol. 13 (2010), Article 10.9.1, Example 12.
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Barry7/barry172.html">Eulerian polynomials as moments, via exponential Riordan arrays</a>, J. Int. Seq., Vol. 14 (2011), Article 11.9.5; <a href="http://arxiv.org/abs/1105.3043">arXiv preprint</a>, arXiv:1105.3043 [math.CO], 2011.
%H Paul Barry, <a href="https://arxiv.org/abs/1802.03443">On a transformation of Riordan moment sequences</a>, arXiv:1802.03443 [math.CO], 2018.
%H Paul Barry, <a href="https://arxiv.org/abs/1803.10297">Generalized Eulerian Triangles and Some Special Production Matrices</a>, arXiv:1803.10297 [math.CO], 2018.
%H Daniel Barsky, <a href="http://www.mat.univie.ac.at/~slc/opapers/s05barsky.html">Analyse p-adique et suites classiques de nombres</a>, Sem. Loth. Comb. B05b (1981), pp. 1-21.
%H J. P. Barthelemy, <a href="http://dx.doi.org/10.1016/0012-365X(80)90159-4">An asymptotic equivalent for the number of total preorders on a finite set</a>, Discrete Mathematics, Vol. 29, No. 3 (1980), pp. 311-313.
%H Beáta Bényi and José L. Ramírez, <a href="https://arxiv.org/abs/1804.03949">Some Applications of S-restricted Set Partitions</a>, arXiv:1804.03949 [math.CO], 2018.
%H François Bergeron, Philippe Flajolet, and Bruno Salvy, <a href="https://doi.org/10.1007/3-540-55251-0_2">Varieties of increasing trees</a>, in J. C. Raoult (ed.), CAAP '92, Colloquium on Trees in Algebra and Programming, CAAP 1992, Lecture Notes in Computer Science, Vol. 581, Springer, Berlin, Heidelberg, 1992, pp. 24-48; <a href="http://algo.inria.fr/flajolet/Publications/BeFlSa92.pdf">alternative link</a>.
%H Nantel Bergeron, Laura Colmenarejo, Shu Xiao Li, John Machacek, Robin Sulzgruber, Mike Zabrocki, Adriano Garsia, Marino Romero, Don Qui, and Nolan Wallach, <a href="http://garsia.math.yorku.ca/~zabrocki/summary.pdf">Super Harmonics and a representation theoretic model for the Delta conjecture</a>, A summary of the open problem sessions of Jan 24, 2019, Representation Theory Connections to (q,t)-Combinatorics (19w5131), Banff, BC, Canada.
%H Sara C. Billey, M. Konvalinka, T. K. Petersen, W. Slofstra, and B. E. Tenner, <a href="http://www.math.washington.edu/~billey/papers/DoubleCosets.pdf">Parabolic double cosets in Coxeter groups</a>, Discrete Mathematics and Theoretical Computer Science, Submitted, 2016.
%H P. Blasiak, K. A. Penson, and A. I. Solomon, <a href="https://arxiv.org/abs/quant-ph/0303030">Dobinski-type relations and the log-normal distribution</a>, arXiv:quant-ph/0303030, 2003.
%H Olivier Bodini, Antoine Genitrini, and Mehdi Naima, <a href="https://arxiv.org/abs/1808.08376">Ranked Schröder Trees</a>, arXiv:1808.08376 [cs.DS], 2018.
%H Olivier Bodini, Antoine Genitrini, Cécile Mailler, and Mehdi Naima, <a href="https://hal.archives-ouvertes.fr/hal-02865198">Strict monotonic trees arising from evolutionary processes: combinatorial and probabilistic study</a>, hal-02865198 [math.CO] / [math.PR] / [cs.DS] / [cs.DM], 2020.
%H S. Alex Bradt, Jennifer Elder, Pamela E. Harris, Gordon Rojas Kirby, Eva Reutercrona, Yuxuan (Susan) Wang, and Juliet Whidden, <a href="https://arxiv.org/abs/2401.06937">Unit interval parking functions and the r-Fubini numbers</a>, arXiv:2401.06937 [math.CO], 2024. See page 2.
%H Florian Bridoux, Caroline Gaze-Maillot, Kévin Perrot, and Sylvain Sené, <a href="https://arxiv.org/abs/2001.07391">Complexity of limit-cycle problems in Boolean networks</a>, arXiv:2001.07391 [cs.DM], 2020.
%H A. Cayley, <a href="https://doi.org/10.1080/14786445908642782">On the theory of the analytical forms called trees II</a>, Phil. Mag., Vol. 18 (1859), pp. 374-378 = Math. Papers Vol. 4, pp. 112-115.
%H Peter J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seq., Vol. 3 (2000), Article 00.1.5.
%H J. L. Chandon, J. LeMaire, and J. Pouget, <a href="http://www.numdam.org/item?id=MSH_1978__62__61_0">Dénombrement des quasi-ordres sur un ensemble fini</a>, Math. Sci. Humaines, Vol. 62 (1978), pp. 61-80.
%H Grégory Chatel, Vincent Pilaud, and Viviane Pons, <a href="https://arxiv.org/abs/1701.07995">The weak order on integer posets</a>, arXiv:1701.07995 [math.CO], 2017.
%H Chao-Ping Chen, <a href="https://doi.org/10.1016/j.jnt.2016.08.010">Sharp inequalities and asymptotic series related to Somos' quadratic recurrence constant</a>, Journal of Number Theory, Vol. 172 (March 2017), pp. 145-159.
%H William Y. C. Chen, Alvin Y. L. Dai, and Robin D. P. Zhou, <a href="http://arxiv.org/abs/1304.3187">Ordered Partitions Avoiding a Permutation of Length 3</a>, arXiv preprint arXiv:1304.3187 [math.CO], 2013.
%H Ali Chouria, Vlad-Florin Drǎgoi, and Jean-Gabriel Luque, <a href="https://arxiv.org/abs/2004.04203">On recursively defined combinatorial classes and labelled trees</a>, arXiv:2004.04203 [math.CO], 2020.
%H Mircea I. Cirnu, <a href="http://www.emis.de/journals/BAMV/conten/vol18/BAMV_XVIII-1_p015-028.pdf">Determinantal formulas for sum of generalized arithmetic-geometric series</a>, Boletin de la Asociacion Matematica Venezolana, Vol. XVIII, No. 1 (2011), p. 13.
%H Anders Claesson and T. Kyle Petersen, <a href="http://www.jstor.org/stable/27642167">Conway's napkin problem</a>, Amer. Math. Monthly, Vol. 114, No. 3 (2007), pp. 217-231.
%H Tyler Clark and Tom Richmond, <a href="http://people.wku.edu/tom.richmond/Papers/CountConvexTopsFTOsets.pdf">The Number of Convex Topologies on a Finite Totally Ordered Set</a>, 2013, to appear in Involve;
%H Pietro Codara, Ottavio M. D'Antona and Vincenzo Marra, <a href="https://doi.org/10.1007/978-3-540-75256-1_17">Best Approximation of Ruspini Partitions in Goedel Logic</a>, in Symbolic and Quantitative Approaches to Reasoning with Uncertainty, Lecture Notes in Computer Science, Vol. 4724 (2007), pp. 161-172.
%H Pierluigi Contucci, Emanuele Panizzi, Federico Ricci-Tersenghi, and Alina Sîrbu, <a href="http://arxiv.org/abs/1406.7642">A new dimension for democracy: egalitarianism in the rank aggregation problem</a>, arXiv:1406.7642 [physics.soc-ph], 2014.
%H H. B. Curry, <a href="https://www.jstor.org/stable/2370728">An Analysis of Logical Substitution</a>, American Journal of Mathematics, Vol. 51, No. 3 (1929), pp. 363-84; see page 369.
%H N. G. de Bruijn, <a href="https://pure.tue.nl/ws/files/2434588/597529.pdf">Enumerative combinatorial structures concerning structures</a>, Nieuw Archief. voor Wisk., Vol. 11 (1963), pp. 142-161; see p. 150.
%H Ayhan Dil and Veli Kurt, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Dil/dil5.html">Investigating Geometric and Exponential Polynomials with Euler-Seidel Matrices</a>, J. Int. Seq., Vol. 14 (2011), Article 11.4.6.
%H Ayhan Dil and Veli Kurt, <a href="https://www.emis.de/journals/INTEGERS/papers/m38/m38.Abstract.html">Polynomials related to harmonic numbers and evaluation of harmonic number series I</a>, INTEGERS, Vol. 12 (2012), #A38.
%H Diego Dominici, <a href="http://arxiv.org/abs/math/0501052">Nested derivatives: A simple method for computing series expansions of inverse functions</a>, arXiv:math/0501052v2 [math.CA], 2005.
%H Frédéric Fauvet, Loïc Foissy, and Dominique Manchon, <a href="http://arxiv.org/abs/1503.03820">The Hopf algebra of finite topologies and mould composition</a>, arXiv preprint arXiv:1503.03820, 2015
%H Valentin Féray, <a href="http://arxiv.org/abs/1410.1772">Cyclic inclusion-exclusion</a>, arXiv preprint arXiv:1410.1772 [math.CO], 2014.
%H Philippe Flajolet, Stefan Gerhold, and Bruno Salvy, <a href="http://arxiv.org/abs/math/0501379">On the non-holonomic character of logarithms, powers and the n-th prime function</a>, arXiv:math/0501379 [math.CO], 2005.
%H Philippe Flajolet and Robert Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 109.
%H Aviezri S. Fraenkel and Moshe Mor, <a href="https://doi.org/10.1093/comjnl/26.4.336">Combinatorial compression and partitioning of large dictionaries</a>, Computer J., Vol. 26 (1983), pp. 336-343. See Tables 4 and 5.
%H Harvey M. Friedman, <a href="https://doi.org/10.1007/978-3-319-96274-0_12">Concrete Mathematical Incompleteness: Basic Emulation Theory</a>, Hilary Putnam on Logic and Mathematics, Outstanding Contributions to Logic, Vol. 9, Springer, Cham, 2018, pp. 179-234.
%H Florent Foucaud, Ralf Klasing and Peter J. Slater, <a href="http://arxiv.org/abs/1406.7490">Centroidal bases in graphs</a>, arXiv preprint arXiv:1406.7490 [math.CO], 2014.
%H Wolfgang Gatterbauer and Dan Suciu, <a href="http://arxiv.org/abs/1412.1069">Approximate Lifted Inference with Probabilistic Databases</a>, arXiv preprint arXiv:1412.1069 [cs.DB], 2014.
%H Wolfgang Gatterbauer and Dan Suciu, <a href="https://doi.org/10.1007/s00778-016-0434-5">Dissociation and propagation for approximate lifted inference with standard relational database management systems</a>, The VLDB Journal, Vol. 26, No. 1 (February 2017), pp 5-30; DOI 10.1007/s00778-016-0434-5.
%H Joël Gay and Vincent Pilaud, <a href="https://arxiv.org/abs/1804.06572">The weak order on Weyl posets</a>, arXiv:1804.06572 [math.CO], 2018.
%H Christian Geist and Ulle Endriss, <a href="https://arxiv.org/abs/1401.3866">Automated search for impossibility theorems in social choice theory: ranking sets of objects</a>, arXiv:1401.3866 [cs.AI], 2014; J. Artif. Intell. Res. (JAIR), Vol. 40 (2011), pp. 143-174.
%H Olivier Gérard, <a href="http://forums.wolfram.com/mathgroup/archive/1997/Oct/msg00231.html">Re: Horse Race Puzzle</a>.
%H Seyoum Getu, Louis W. Shapiro, Wen-jin Woan, and Leon C. Woodson, <a href="https://dx.doi.org/10.1137/0405040">How to guess a generating function</a>, SIAM J. Discrete Math., Vol. 5, No. 4 (1992), pp. 497-499.
%H Robert Gill, <a href="https://doi.org/10.1016/S0012-365X(97)00187-8">The number of elements in a generalized partition semilattice</a>, Discrete mathematics, Vol. 186, No. 1-3 (1998), pp. 125-134. See Example 1.
%H Samuele Giraudo, <a href="http://arxiv.org/abs/1306.6938">Combinatorial operads from monoids</a>, arXiv preprint arXiv:1306.6938 [math.CO], 2013.
%H Manfred Göbel, <a href="https://doi.org/10.1007/s002000050088">On the number of special permutation-invariant orbits and terms</a>, in Applicable Algebra in Engin., Comm. and Comp. (AAECC 8), Vol. 8, No. 6 (1997), pp. 505-509.
%H W. Steven Gray and Makhin Thitsa, <a href="http://dx.doi.org/10.1109/SSST.2013.6524939">System Interconnections and Combinatorial Integer Sequences</a>, in: System Theory (SSST), 2013 45th Southeastern Symposium on, Date of Conference: 11-11 March 2013.
%H Martin Griffiths and István Mező, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Griffiths/griffiths11.html">A generalization of Stirling Numbers of the Second Kind via a special multiset</a>, JIS, Vol. 13 (2010), Article 10.2.5.
%H O. A. Gross, <a href="http://www.jstor.org/stable/2312725">Preferential arrangements</a>, Amer. Math. Monthly, Vol. 69, No. 1 (1962), pp. 4-8.
%H Gottfried Helms, <a href="http://go.helms-net.de/math/divers/ZerosOfGpFunctions.htm">Discussion of a problem concerning summing of like powers</a>, 2007.
%H Michael E. Hoffman, <a href="http://arxiv.org/abs/1207.1705">Updown categories: Generating functions and universal covers</a>, arXiv preprint arXiv:1207.1705 [math.CO], 2012.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=41">Encyclopedia of Combinatorial Structures 41</a>.
%H Marsden Jacques and Dennis Wong, <a href="https://doi.org/10.1007/978-3-030-39219-2_29">Greedy Universal Cycle Constructions for Weak Orders</a>, Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020): Algorithms and Discrete Applied Mathematics, pp. 363-370.
%H Jacques Marsden, Dennis Wong, and Kyounga Woo. <a href="https://doi.org/10.1016/j.disc.2020.111992">Generating Gray codes for weak orders in constant amortized time</a>, Discrete Mathematics, Vo. 343, No. 10 (2020), 111992.
%H Svante Janson, <a href="http://arxiv.org/abs/1305.3512">Euler-Frobenius numbers and rounding</a>, arXiv preprint arXiv:1305.3512 [math.PR], 2013.
%H Marek Jarociński and Bartosz Maćkowiak, <a href="http://www2.wiwi.hu-berlin.de/institute/bartosz/VariableChoiceOA.pdf">Online Appendix to "Granger-Causal-Priority and Choice of Variables in Vector Autoregressions"</a>, 2013.
%H Vít Jelínek, Ida Kantor, Jan Kynčl, and Martin Tancer, <a href="https://arxiv.org/abs/1809.05774">On the growth of the Möbius function of permutations</a>, arXiv:1809.05774 [math.CO], 2018.
%H Niraj Khare, Rudolph Lorentz, and Catherine Huafei Yan, <a href="https://doi.org/10.1007/s11425-014-4827-x">Bivariate Gončarov polynomials and integer sequences</a>, Science China Mathematics, Vol. 57, No. 1 (2014), pp. 1561-1578; <a href="https://www.math.tamu.edu/~cyan/Files/BivariateGP.pdf">alternative link</a>.
%H Dongseok Kim, Young Soo Kwon, and Jaeun Lee, <a href="http://arxiv.org/abs/1206.0550">Enumerations of finite topologies associated with a finite graph</a>, arXiv preprint arXiv:1206.0550 [math.CO], 2012. See Th. 4.3. - From _N. J. A. Sloane_, Nov 09 2012
%H Donald E. Knuth, John Riordan, and N. J. A. Sloane, <a href="/A000670/a000670.pdf">Correspondence, 1970</a>.
%H Martin J. Kochanski, <a href="http://www.nugae.com/mathematics/bin/ordering.pdf">How many orders are there?</a>
%H Ali Sinan Koksal, Yewen Pu, Saurabh Srivastava, Rastislav Bodik, Jasmin Fisher, and Nir Piterman, <a href="https://doi.org/10.1145/2429069.2429125">Synthesis of biological models from mutation experiments</a>, Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 2013, pp. 469-482.
%H Takao Komatsu and José L. Ramírez, <a href="https://arxiv.org/abs/1802.06188">Some determinants involving incomplete Fubini numbers</a>, arXiv:1802.06188 [math.NT], 2018.
%H Germain Kreweras, <a href="http://archive.numdam.org/ARCHIVE/MSH/MSH_1963__3_/MSH_1963__3__31_0/MSH_1963__3__31_0.pdf">Une dualité élémentaire souvent utile dans les problèmes combinatoires</a>, Mathématiques et Sciences Humaines 3 (1963): 31-41.
%H Alex Kumjian, David Pask, Aidan Sims, and Michael F. Whittaker, <a href="http://arxiv.org/abs/1310.6100">Topological spaces associated to higher-rank graphs</a>, arXiv preprint arXiv:1310.6100 [math.OA], 2013.
%H Hans Maassen and Thom Bezembinder, <a href="https://doi.org/10.1007/s003550100129">Generating random weak orders and the probability of a Condorcet winner</a>, Social Choice and Welfare, Vol. 19, No. 3 (2002), pp. 517-532.
%H P. A. MacMahon, <a href="https://doi.org/10.1112/plms/s1-22.1.330">Yoke-chains and multipartite compositions in connexion with the analytical forms called "trees</a>, Proc. London Math. Soc., Vol. 22 (1891), pp. 330-346; reprinted in Coll. Papers I, pp. 600-616.
%H Victor Meally, <a href="/A002868/a002868.pdf">Comparison of several sequences given in Motzkin's paper "Sorting numbers for cylinders...", letter to N. J. A. Sloane, N. D.</a>
%H Elliott Mendelson, <a href="http://www.jstor.org/stable/2690085">Races with Ties</a>, Math. Mag., Vol. 55, No. 3 (1982), pp. 170-175.
%H István Mező, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Mezo/mezo19.html">Periodicity of the last digits of some combinatorial sequences</a>, J. Int. Seq., Vol. 17 (2014), Article 14.1.1; <a href="http://arxiv.org/abs/1308.1637">arXiv preprint</a>, arXiv:1308.1637 [math.CO], 2013.
%H István Mező and Árpád Baricz, <a href="http://arxiv.org/abs/1408.3999">On the generalization of the Lambert W function with applications in theoretical physics</a>, arXiv preprint arXiv:1408.3999 [math.CA], 2014.
%H Moshe Mor and Aviezri S. Fraenkel, <a href="http://dx.doi.org/10.1016/0012-365X(84)90136-5">Cayley permutations</a>, Discrete Math., Vol. 48, No. 1 (1984), pp. 101-112.
%H T. S. Motzkin, <a href="/A000262/a000262.pdf">Sorting numbers for cylinders and other classification numbers</a>, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]
%H Todd Mullen, <a href="https://dalspace.library.dal.ca/bitstream/handle/10222/78458/Mullen-Todd-PhD-MATH-April-2020.pdf">On Variants of Diffusion</a>, Dalhousie University (Halifax, NS Canada, 2020).
%H Norihiro Nakashima and Shuhei Tsujie, <a href="https://arxiv.org/abs/1904.09748">Enumeration of Flats of the Extended Catalan and Shi Arrangements with Species</a>, arXiv:1904.09748 [math.CO], 2019.
%H Roger B. Nelsen and Harvey Schmidt, Jr., <a href="http://www.jstor.org/stable/2690450">Chains in power sets</a>, Math. Mag., Vol. 64, No. 1 (1991), pp. 23-31.
%H S. Nkonkobe and V. Murali, <a href="http://arxiv.org/abs/1503.06173">On Some Identities of Barred Preferential Arrangements</a>, arXiv preprint arXiv:1503.06173 [math.CO], 2015.
%H S. Nkonkobe and V. Murali. <a href="https://doi.org/10.1016/j.disc.2016.11.010">A study of a family of generating functions of Nelsen-Schmidt type and some identities on restricted barred preferential arrangements</a>, Discrete Mathematics, Vol. 340 (2017), pp. 1122-1128.
%H Mathilde Noual and Sylvain Sene, <a href="http://arxiv.org/abs/1111.2077">Towards a theory of modelling with Boolean automata networks-I. Theorisation and observations</a>, arXiv preprint arXiv:1111.2077 [cs.DM], 2011.
%H J.-C. Novelli and J.-Y. Thibon, <a href="https://arxiv.org/abs/math/0605061">Polynomial realizations of some trialgebras</a>, Proc. Formal Power Series and Algebraic Combinatorics 2006 (San-Diego, 2006); arXiv:math/0605061 [math.CO], 2006.
%H J.-C. Novelli and J.-Y. Thibon, <a href="http://arxiv.org/abs/1403.5962">Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions</a>, arXiv preprint arXiv:1403.5962 [math.CO], 2014.
%H J.-C. Novelli, J.-Y. Thibon, and L. K. Williams, <a href="http://dx.doi.org/10.1016/j.aim.2010.01.006">Combinatorial Hopf algebras, noncommutative Hall-Littlewood functions, and permutation tableaux</a>, Adv. Math., Vol. 224, No. 4 (2010), pp. 1311-1348.
%H Arthur Nunge, <a href="https://arxiv.org/abs/1805.01797">Eulerian polynomials on segmented permutations</a>, arXiv:1805.01797 [math.CO], 2018.
%H OEIS Wiki, <a href="http://oeis.org/wiki/Sorting_numbers">Sorting numbers</a>.
%H Karolina Okrasa and Paweł Rzążewski, <a href="https://arxiv.org/abs/1804.10470">Intersecting edge distinguishing colorings of hypergraphs</a>, arXiv:1804.10470 [cs.DM], 2018.
%H K. A. Penson, P. Blasiak, G. Duchamp, A. Horzela, and A. I. Solomon, <a href="http://arXiv.org/abs/quant-ph/0312202">Hierarchical Dobinski-type relations via substitution and the moment problem</a>, arXiv:quant-ph/0312202, 2003.
%H Tilman Piesk, <a href="/A000670/a000670.png">Tree of weak orderings in concertina cube</a>. Illustration of a(3) = 13, used with permission. See also the <a href="https://commons.wikimedia.org/wiki/File%3ATree_of_weak_orderings_in_concertina_cube%2C_plain.png">original of this figure</a> on Wikimedia Commons.
%H Vincent Pilaud and Viviane Pons, <a href="http://arxiv.org/abs/1606.09643">Permutrees</a>, arXiv preprint arXiv:1606.09643 [math.CO], 2016-2017.
%H Claudio de J. Pita Ruiz V., <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Pita/pita19.html">Some Number Arrays Related to Pascal and Lucas Triangles</a>, J. Int. Seq., Vol. 16 (2013), Article 13.5.7.
%H Robert A. Proctor, <a href="http://arxiv.org/abs/math/0606404">Let's Expand Rota's Twelvefold Way For Counting Partitions!</a>, arXiv:math/0606404 [math.CO], 2006-2007.
%H Helmut Prodinger, <a href="http://dx.doi.org/10.4153/CMB-1983-050-4">Ordered Fibonacci partitions</a>, Canad. Math. Bull. 26 (1983), no. 3, 312--316. MR0703402 (84m:05012). [See F_n on page 312.
%H Yash Puri and Thomas Ward, <a href="https://www.emis.de/journals/JIS/VOL4/WARD/short.html">Arithmetic and growth of periodic orbits</a>, J. Integer Seq., Vol. 4 (2001), Article 01.2.1.
%H S. Ramanujan, <a href="http://www.imsc.res.in/~rao/ramanujan/NoteBooks/NoteBook2/chapterII/page10.htm">Notebook entry</a>.
%H Joe Sawada and Dennis Wong, <a href="http://www.cis.uoguelph.ca/~sawada/papers/weak.pdf">An Efficient Universal Cycle Construction for Weak Orders</a>, University of Guelph, School of Computer Science (2019), presented at the 30th Coast Combinatorics Conference at University of Hawaii, Manoa.
%H Joe Sawada and Dennis Wong. <a href="https://doi.org/10.1016/j.disc.2020.112022">Efficient universal cycle constructions for weak orders</a>, Discrete Mathematics 343.10 (2020): 112022. [Note that this is a different item from that mentioned in the link with a similar title. One is a paper, the other is a talk.]
%H N. J. A. Sloane and Thomas Wieder, <a href="https://arxiv.org/abs/math/0307064">The Number of Hierarchical Orderings</a>, arXiv:math/0307064 [math.CO], 2003; Order, Vol. 21 (2004), pp. 83-89.
%H Jacob Sprittulla, <a href="https://arxiv.org/abs/2109.12705">The ordered Bell numbers as weighted sums of odd or even Stirling numbers of the second kind</a>, arXiv:2109.12705 [math.CO], 2021.
%H Daniel J. Velleman and Gregory S. Call, <a href="http://www.jstor.org/stable/2690567">Permutations and combination locks</a>, Math. Mag., Vol. 68, No. 4 (1995), pp. 243-253.
%H Carl G. Wagner, <a href="/A004121/a004121_1.pdf">Enumeration of generalized weak orders</a>, Preprint, 1980. [Annotated scanned copy] <a href="https://www.math.utk.edu/~wagner/papers/weak.pdf">Arch. Math., Vol. 39 (1982), pp. 147-152</a>.
%H Carl G. Wagner and N. J. A. Sloane, <a href="/A004121/a004121.pdf">Correspondence, 1980</a>.
%H F. V. Weinstein, <a href="http://arXiv.org/abs/math.NT/0307150">Notes on Fibonacci partitions</a>, arXiv:math/0307150 [math.NT], 2003-2015 (see page 9).
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CombinationLock.html">Combination Lock</a>.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Ordered_Bell_number">Ordered Bell number</a>.
%H Herbert S. Wilf, <a href="http://www.math.upenn.edu/~wilf/DownldGF.html">Generatingfunctionology</a>, 2nd edn., Academic Press, NY, 1994, p. 175, Eq. 5.2.6, 5.2.7.
%H Andrew T. Wilson, <a href="https://doi.org/10.1016/j.jcta.2017.08.009">Torus link homology and the nabla operator</a>, Journal of Combinatorial Theory, Series A, Vol. 154 (2018), pp. 129-144; <a href="https://arxiv.org/abs/1606.00764">arXiv preprint</a>, arXiv:1606.00764 [math.CO], 2016.
%H Ai-Min Xu and Zhong-Di Cen, <a href="https://doi.org/10.1016/j.cam.2013.09.077">Some identities involving exponential functions and Stirling numbers and applications</a>, J. Comput. Appl. Math., Vol. 260 (2014), pp. 201-207.
%H Yan X Zhang, <a href="http://arxiv.org/abs/1508.00318">Four Variations on Graded Posets</a>, arXiv preprint arXiv:1508.00318 [math.CO], 2015.
%H Yi Zhu and Evgueni T. Filipov, <a href="https://doi.org/10.1098/rspa.2019.0366">An efficient numerical approach for simulating contact in origami assemblages</a>, Proc. R. Soc. A, Vol. 475 (2019), 20190366.
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H <a href="/index/Par#partN">Index entries for related partition-counting sequences</a>
%F a(n) = Sum_{k=0..n} k! * StirlingS2(n,k) (whereas the Bell numbers A000110(n) = Sum_{k=0..n} StirlingS2(n,k)).
%F E.g.f.: 1/(2-exp(x)).
%F a(n) = Sum_{k=1..n} binomial(n, k)*a(n-k), a(0) = 1.
%F The e.g.f. y(x) satisfies y' = 2*y^2 - y.
%F a(n) = A052856(n) - 1, if n>0.
%F a(n) = A052882(n)/n, if n>0.
%F a(n) = A076726(n)/2.
%F a(n) is asymptotic to (1/2)*n!*log_2(e)^(n+1), where log_2(e) = 1.442695... [Barthelemy80, Wilf90].
%F For n >= 1, a(n) = (n!/2) * Sum_{k=-infinity..infinity} of (log(2) + 2 Pi i k)^(-n-1). - _Dean Hickerson_
%F a(n) = ((x*d/dx)^n)(1/(2-x)) evaluated at x=1. - _Karol A. Penson_, Sep 24 2001
%F For n>=1, a(n) = Sum_{k>=1} (k-1)^n/2^k = A000629(n)/2. - _Benoit Cloitre_, Sep 08 2002
%F Value of the n-th Eulerian polynomial (cf. A008292) at x=2. - _Vladeta Jovovic_, Sep 26 2003
%F First Eulerian transform of the powers of 2 [A000079]. See A000142 for definition of FET. - _Ross La Haye_, Feb 14 2005
%F a(n) = Sum_{k=0..n} (-1)^k*k!*Stirling2(n+1, k+1)*(1+(-1)^k)/2. - _Paul Barry_, Apr 20 2005
%F a(n) + a(n+1) = 2*A005649(n). - _Philippe Deléham_, May 16 2005 - _Thomas Wieder_, May 18 2005
%F Equals inverse binomial transform of A000629. - _Gary W. Adamson_, May 30 2005
%F 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
%F Recurrence: 2*a(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
%F a(n) = (-1)^n * n! * Laguerre(n,P((.),2)), umbrally, where P(j,t) are the polynomials in A131758. - _Tom Copeland_, Sep 27 2007
%F 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
%F a(n) = Sum_{k=0..n} A131689(n,k). - _Philippe Deléham_, Nov 03 2008
%F From _Peter Bala_, Jul 01 2009: (Start)
%F Analogy with the Bernoulli numbers.
%F We enlarge upon the above comment of M. Kochanski.
%F The Bernoulli polynomials B_n(x), n = 0,1,..., are given by the formula
%F (1)... B_n(x) := Sum_{k=0..n} binomial(n,k)*B(k)*x^(n-k),
%F where B(n) denotes the sequence of Bernoulli numbers B(0) = 1,
%F B(1) = -1/2, B(2) = 1/6, B(3) = 0, ....
%F By analogy, we associate with the present sequence an Appell sequence of polynomials {P_n(x)} n >= 0 defined by
%F (2)... P_n(x) := Sum_{k=0..n} binomial(n,k)*a(k)*x^(n-k).
%F These polynomials have similar properties to the Bernoulli polynomials.
%F The first few values are P_0(x) = 1, P_1(x) = x + 1,
%F P_2(x) = x^2 + 2*x + 3, P_3(x) = x^3 + 3*x^2 + 9*x + 13 and
%F P_4(x) = x^4 + 4*x^3 + 18*x^2 + 52*x + 75. See A154921 for the triangle of coefficients of these polynomials.
%F The e.g.f. for this polynomial sequence is
%F (3)... exp(x*t)/(2 - exp(t)) = 1 + (x + 1)*t + (x^2 + 2*x + 3)*t^2/2! + ....
%F The polynomials satisfy the difference equation
%F (4)... 2*P_n(x - 1) - P_n(x) = (x - 1)^n,
%F and so may be used to evaluate the weighted sums of powers of integers
%F (1/2)*1^m + (1/2)^2*2^m + (1/2)^3*3^m + ... + (1/2)^(n-1)*(n-1)^m
%F via the formula
%F (5)... Sum_{k=1..n-1} (1/2)^k*k^m = 2*P_m(0) - (1/2)^(n-1)*P_m(n),
%F analogous to the evaluation of the sums 1^m + 2^m + ... + (n-1)^m in terms of Bernoulli polynomials.
%F This last result can be generalized to
%F (6)... Sum_{k=1..n-1} (1/2)^k*(k+x)^m = 2*P_m(x)-(1/2)^(n-1)*P_m(x+n).
%F For more properties of the polynomials P_n(x), refer to A154921.
%F For further information on weighted sums of powers of integers and the associated polynomial sequences, see A162312.
%F The present sequence also occurs in the evaluation of another sum of powers of integers. Define
%F (7)... S_m(n) := Sum_{k=1..n-1} (1/2)^k*((n-k)*k)^m, m = 1,2,....
%F Then
%F (8)... S_m(n) = (-1)^m *[2*Q_m(-n) - (1/2)^(n-1)*Q_m(n)],
%F where Q_m(x) are polynomials in x given by
%F (9)... Q_m(x) = Sum_{k=0..m} a(m+k)*binomial(m,k)*x^(m-k).
%F The first few values are Q_1(x) = x + 3, Q_2(x) = 3*x^2 + 26*x + 75
%F and Q_3(x) = 13*x^3 + 225*x^2 + 1623*x + 4683.
%F For example, m = 2 gives
%F (10)... S_2(n) := Sum_{k=1..n-1} (1/2)^k*((n-k)*k)^2
%F = 2*(3*n^2 - 26*n + 75) - (1/2)^(n-1)*(3*n^2 + 26*n + 75).
%F (End)
%F G.f.: 1/(1-x/(1-2*x/(1-2*x/(1-4*x/(1-3*x/(1-6*x/(1-4*x/(1-8*x/(1-5*x/(1-10*x/(1-6*x/(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
%F G.f.: 1/(1-x-2*x^2/(1-4*x-8*x^2/(1-7*x-18*x^2/(1-10*x-32*x^2/(1../(1-(3*n+1)*x-2*(n+1)^2*x^2/(1-... (continued fraction). - _Paul Barry_, Jun 17 2010
%F G.f.: A(x) = Sum_{n>=0} n!*x^n / Product_{k=1..n} (1-k*x). - _Paul D. Hanna_, Jul 20 2011
%F a(n) = A074206(q_1*q_2*...*q_n), where {q_i} are distinct primes. - _Vladimir Shevelev_, Aug 05 2011
%F The adjusted e.g.f. A(x) := 1/(2-exp(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^(n-1)(f(x)) evaluated at x = 0. Compare with A050351. - _Peter Bala_, Aug 31 2011
%F G.f.: 1+x/(1-x+2*x*(x-1)/(1+3*x*(2*x-1)/(1+4*x*(3*x-1)/(1+5*x*(4*x-1)/(1+... or 1+x/(U(0)-x), U(k) = 1+(k+2)*(k*x+x-1)/U(k+1); (continued fraction). - _Sergei N. Gladkovskii_, Oct 30 2011
%F a(n) = D^n*(1/(1-x)) evaluated at x = 0, where D is the operator (1+x)*d/dx. Cf. A052801. - _Peter Bala_, Nov 25 2011
%F E.g.f.: 1 + x/(G(0)-2*x) where G(k) = x + k + 1 - x*(k+1)/G(k+1); (continued fraction). - _Sergei N. Gladkovskii_, Jul 11 2012
%F 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). - _Sergei N. Gladkovskii_, Oct 01 2012
%F 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
%F 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
%F a(n) is always odd. For odd prime p and n >= 1, a((p-1)*n) = 0 (mod p). - _Peter Bala_, Sep 18 2013
%F 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
%F 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
%F a(n) = log(2)* Integral_{x>=0} floor(x)^n * 2^(-x) dx. - _Peter Bala_, Feb 06 2015
%F 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
%F a(n) = Sum_{k=1..n} (k*b2(k-1)*(k)!*Stirling2(n, k)), n>0, a(0)=1, where b2(n) is the n-th Bernoulli number of the second kind. - _Vladimir Kruchinin_, Nov 21 2016
%F a(n) = Sum_{k=0..2^(n-1)-1} A284005(k), n>0, a(0)=1. - _Mikhail Kurkov_, Jul 08 2018 [verification needed]
%F a(n) = A074206(k) for squarefree k with n prime factors. In particular a(n) = A074206(A002110(n)). - _Amiram Eldar_, May 13 2019
%F For n > 0, a(n) = -(-1)^n / 2 * PHI(2, -n, 0), where PHI(z, s, a) is the Lerch zeta function. - _Federico Provvedi_, Sep 05 2020
%F a(n) = Sum_{s in S_n} Product_{i=1..n} binomial(i,s(i)-1), where s ranges over the set S_n of permutations of [n]. - _Jose A. Rodriguez_, Feb 02 2021
%F Sum_{n>=0} 1/a(n) = 2.425674839121428857970063350500499393706641093287018840857857170864211946122664... - _Vaclav Kotesovec_, Jun 17 2021
%F From _Jacob Sprittulla_, Oct 05 2021: (Start)
%F The following identities hold for sums over Stirling numbers of the second kind with even or odd second argument:
%F a(n) = 2 * Sum_{k=0..floor(n/2)} ((2k)! * Stirling2(n,2*k) ) - (-1)^n = 2*A052841-(-1)^n
%F a(n) = 2 * Sum_{k=0..floor(n/2)} ((2k+1)!* Stirling2(n,2*k+1))+ (-1)^n = 2*A089677+(-1)^n
%F a(n) = Sum_{k=1..floor((n+1)/2)} ((2k-1)!* Stirling2(n+1,2*k))
%F a(n) = Sum_{k=0..floor((n+1)/2)} ((2k)! * Stirling2(n+1,2*k+1)). (End)
%e Let the points be labeled 1,2,3,...
%e a(2) = 3: 1<2, 2<1, 1=2.
%e 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.
%e 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.
%e 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:
%e ........................................................
%e ........1 (x3 colors).....1(x2 colors)....1(x2 colors)..
%e ........|................/.\............./.\............
%e ........2 (x3 colors)...2...3...........3...2...........
%e ........|...............................................
%e ........3...............................................
%e ......====..............====............====............
%e .Totals 9......+..........2....+..........2....=..13....
%e ........................................................
%e 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:
%e ...............................................................
%e .....1 (x3).....1(x4).......1(x4).....1(x4)........1(x3).......
%e .....|........./.\........./.\......./.\...........|...........
%e .....2 (x3)...2...3.(x3)..3...2(x3).4...2(x3)......2(x4).......
%e .....|.............\...........\.........\......../.\..........
%e .....3.(x3).........4...........4.........3......3...4.........
%e .....|.........................................................
%e .....4.........................................................
%e ....====......=====........====......====.........====.........
%e Tots 27....+....12......+...12....+...12.......+...12...=...75.
%e From _Joerg Arndt_, Mar 18 2014: (Start)
%e 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:
%e 01: [ 1 1 1 ] { 1, 2, 3 }
%e 02: [ 1 1 2 ] { 1, 2 } < { 3 }
%e 03: [ 1 2 1 ] { 1, 3 } < { 2 }
%e 04: [ 2 1 1 ] { 2, 3 } < { 1 }
%e 05: [ 1 2 2 ] { 1 } < { 2, 3 }
%e 06: [ 2 1 2 ] { 2 } < { 1, 3 }
%e 07: [ 2 2 1 ] { 3 } < { 1, 2 }
%e 08: [ 1 2 3 ] { 1 } < { 2 } < { 3 }
%e 09: [ 1 3 2 ] { 1 } < { 3 } < { 2 }
%e 00: [ 2 1 3 ] { 2 } < { 1 } < { 3 }
%e 11: [ 2 3 1 ] { 3 } < { 1 } < { 2 }
%e 12: [ 3 1 2 ] { 2 } < { 3 } < { 1 }
%e 13: [ 3 2 1 ] { 3 } < { 2 } < { 1 }
%e (End)
%p 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;
%p with(combstruct); SeqSetL := [S, {S=Sequence(U), U=Set(Z,card >= 1)},labeled]; seq(count(SeqSetL,size=j),j=1..12);
%p 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
%p a := n -> add(combinat:-eulerian1(n,k)*2^k,k=0..n): # _Peter Luschny_, Jan 02 2015
%p 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
%p # next Maple program:
%p b:= proc(n, k) option remember;
%p `if`(n=0, k!, k*b(n-1, k)+b(n-1, k+1))
%p end:
%p a:= n-> b(n, 0):
%p seq(a(n), n=0..20); # _Alois P. Heinz_, Aug 04 2021
%t Table[(PolyLog[-z, 1/2] + KroneckerDelta[z])/2, {z, 0, 20}] (* _Wouter Meeussen_ *)
%t 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 t = 30; Range[0, t]! CoefficientList[Series[1/(2 - Exp[x]), {x, 0, t}], x] (* _Vincenzo Librandi_, Mar 16 2014 *)
%t a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ 1 / (2 - Exp@x), {x, 0, n}]]; (* _Michael Somos_, Jun 19 2015 *)
%t Table[Sum[k^n/2^(k+1),{k,0,Infinity}],{n,0,20}] (* _Vaclav Kotesovec_, Jun 26 2015 *)
%t Table[HurwitzLerchPhi[1/2, -n, 0]/2, {n, 0, 20}] (* _Jean-François Alcover_, Jan 31 2016 *)
%t Fubini[n_, r_] := Sum[k!*Sum[(-1)^(i+k+r)*((i+r)^(n-r)/(i!*(k-i-r)!)), {i, 0, k-r}], {k, r, n}]; Fubini[0, 1] = 1; Table[Fubini[n, 1], {n, 0, 20}] (* _Jean-François Alcover_, Mar 31 2016 *)
%t Eulerian1[0, 0] = 1; Eulerian1[n_, k_] := Sum[(-1)^j (k-j+1)^n Binomial[n+1, j], {j, 0, k+1}]; Table[Sum[Eulerian1[n, k] 2^k, {k, 0, n}], {n, 0, 20}] (* _Jean-François Alcover_, Jul 13 2019, after _Peter Luschny_ *)
%t Prepend[Table[-(-1)^k HurwitzLerchPhi[2, -k, 0]/2, {k, 1, 50}], 1] (* _Federico Provvedi_,Sep 05 2020 *)
%t Table[Sum[k!*StirlingS2[n,k], {k, 0, n}], {n, 0, 20}] (* _Vaclav Kotesovec_, Nov 22 2020 *)
%o (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 */
%o (PARI) Vec(serlaplace(1/(2-exp('x+O('x^66))))) /* _Joerg Arndt_, Jul 10 2011 */
%o (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 */
%o (PARI) {a(n) = if( n<1, n==0, sum(k=1, n, binomial(n, k) * a(n-k)))}; /* _Michael Somos_, Jul 16 2017 */
%o (Maxima) makelist(sum(stirling2(n,k)*k!,k,0,n),n,0,12); /* _Emanuele Munarini_, Jul 07 2011 */
%o (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 */
%o (Sage)
%o @CachedFunction
%o def A000670(n) : return 1 if n == 0 else add(A000670(k)*binomial(n,k) for k in range(n))
%o [A000670(n) for n in (0..20)] # _Peter Luschny_, Jul 14 2012
%o (Haskell)
%o a000670 n = a000670_list !! n
%o a000670_list = 1 : f [1] (map tail $ tail a007318_tabl) where
%o f xs (bs:bss) = y : f (y : xs) bss where y = sum $ zipWith (*) xs bs
%o -- _Reinhard Zumkeller_, Jul 26 2014
%o (Python)
%o from math import factorial
%o from sympy.functions.combinatorial.numbers import stirling
%o def A000670(n): return sum(factorial(k)*stirling(n,k) for k in range(n+1)) # _Chai Wah Wu_, Nov 08 2022
%Y See A240763 for a list of the actual preferential arrangements themselves.
%Y A000629, this sequence, A002050, A032109, A052856, A076726 are all more-or-less the same sequence. - _N. J. A. Sloane_, Jul 04 2012
%Y Binomial transform of A052841. Inverse binomial transform of A000629.
%Y Asymptotic to A034172.
%Y Cf. A002144, A002869, A004121, A004122, A007047, A007318, A048144, A053525, A080253, A080254, A011782, A154921, A162312, A163204, A242280, A261959, A290376, A074206.
%Y Row r=1 of A094416. Row 0 of array in A226513. Row n=1 of A262809.
%Y Main diagonal of: A135313, A261781, A276890, A327245, A327583, A327584.
%Y Row sums of triangles A019538, A131689, A208744 and A276891.
%Y A217389 and A239914 give partial sums.
%Y Column k=1 of A326322.
%K nonn,core,nice,easy,changed
%O 0,3
%A _N. J. A. Sloane_
|
