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 [Named after the Italian mathematician Guido Fubini (1879-1943). - Amiram Eldar, Jun 17 2021]
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 and 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->infinity} n*a(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, 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 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
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
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, 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/(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) 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
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 (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
From David L. Harden, Apr 09 2017: (Start)
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.
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).
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)
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
From A.H.M. Smeets, Nov 17 2018: (Start)
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 easily seen by replacing
"{i}" by "x_i := expression_i(x_1, ..., x_n)",
"{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),
similar for simultaneous assignments to more variables, and
"<" 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.
From this also the number of different mean definitions as obtained by iteration of n different mean functions on n initial values. Examples:
the AGM(x1,x2) = AGM(x2,x1) is represented by {arithmetic mean, geometric mean}, i.e., simultaneous assignment in any iteration step;
Archimedes's scheme (for Pi) is represented by {geometric mean} < {harmonic mean}, i.e., sequential assignment in any iteration step;
the geometric mean of two values can also be observed by {arithmetic mean, harmonic mean};
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.
By applying power means (also called Holder means) this can be extended to any value of n. (End)
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
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)
From Peter Bala, Jul 08 2022: (Start)
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.
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)
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
This is the Akiyama-Tanigawa transform of A000079, the powers of two. - Shel Kaphan, May 02 2024
REFERENCES
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.
Norman Biggs, E. Keith Lloyd and Robin J. Wilson, Graph Theory 1736-1936, Oxford, 1976, p. 44 (P(x)).
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 183 (see R_n).
Kenneth S. Brown, Buildings, Springer-Verlag, 1988.
Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 228.
Jean-Marie De Koninck, Ces nombres qui nous fascinent, Entry 13, pp 4, Ellipses, Paris 2008.
P. J. Freyd, On the size of Heyting semi-lattices, preprint, 2002.
Ian P. Goulden and David M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.
Ronald L. Graham, Donald E. Knuth, and Oren 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.
Donald E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, 1973, Section 5.3.1, Problem 3.
M. Muresan, Generalized Fubini numbers, Stud. Cerc. Mat., Vol. 37, No. 1 (1985), pp. 70-76.
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.
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).
Richard P. Stanley, Enumerative Combinatorics, Wadsworth, Vol. 1, 1986; see Example 3.15.10, p. 146.
Jack van der Elsen, Black and White Transformations, Shaker Publishing, Maastricht, 2005, p. 18.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..424 (first 101 terms from N. J. A. Sloane)
Connor Ahlbach, Jeremy Usatine, and Nicholas Pippenger, Barred Preferential Arrangements, Electron. J. Combin., Volume 20, Issue 2 (2013), #P55.
Jean-Christophe Aval, Valentin Féray, Jean-Christophe Novelli, and Jean-Yves Thibon, Quasi-symmetric functions as polynomial functions on Young diagrams, arXiv preprint arXiv:1312.2727 [math.CO], 2013.
Jean-Christophe Aval, Adrien Boussicault, and Philippe Nadeau, Tree-like Tableaux, Electronic Journal of Combinatorics, Vol. 20, No. 4 (2013), #P34.
Ralph W. Bailey, The number of weak orderings of a finite set, Social Choice and Welfare, Vol. 15 (1998), pp. 559-562.
Paul Barry, Exponential Riordan Arrays and Permutation Enumeration, J. Int. Seq., Vol. 13 (2010), Article 10.9.1, Example 12.
Paul Barry, Eulerian polynomials as moments, via exponential Riordan arrays, J. Int. Seq., Vol. 14 (2011), Article 11.9.5; arXiv preprint, arXiv:1105.3043 [math.CO], 2011.
Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018.
Paul Barry, Generalized Eulerian Triangles and Some Special Production Matrices, arXiv:1803.10297 [math.CO], 2018.
Daniel Barsky, Analyse p-adique et suites classiques de nombres, Sem. Loth. Comb. B05b (1981), pp. 1-21.
J. P. Barthelemy, An asymptotic equivalent for the number of total preorders on a finite set, Discrete Mathematics, Vol. 29, No. 3 (1980), pp. 311-313.
Beáta Bényi and José L. Ramírez, Some Applications of S-restricted Set Partitions, arXiv:1804.03949 [math.CO], 2018.
François Bergeron, Philippe Flajolet, and Bruno Salvy, Varieties of increasing trees, 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; alternative link.
Nantel Bergeron, Laura Colmenarejo, Shu Xiao Li, John Machacek, Robin Sulzgruber, Mike Zabrocki, Adriano Garsia, Marino Romero, Don Qui, and Nolan Wallach, Super Harmonics and a representation theoretic model for the Delta conjecture, A summary of the open problem sessions of Jan 24, 2019, Representation Theory Connections to (q,t)-Combinatorics (19w5131), Banff, BC, Canada.
Sara Billey and Matjaž Konvalinka, Generalized rank functions and quilts of alternating sign matrices, arXiv:2412.03236 [math.CO], 2024. See p. 5.
Sara C. Billey, Matjaž Konvalinka, T. Kyle Petersen, William Slofstra, Bridget E. Tenner, Parabolic double cosets in Coxeter groups, Discrete Mathematics and Theoretical Computer Science, Submitted, 2016.
P. Blasiak, K. A. Penson, and A. I. Solomon, Dobinski-type relations and the log-normal distribution, arXiv:quant-ph/0303030, 2003.
Olivier Bodini, Antoine Genitrini, and Mehdi Naima, Ranked Schröder Trees, arXiv:1808.08376 [cs.DS], 2018.
Olivier Bodini, Antoine Genitrini, Cécile Mailler, and Mehdi Naima, Strict monotonic trees arising from evolutionary processes: combinatorial and probabilistic study, hal-02865198 [math.CO] / [math.PR] / [cs.DS] / [cs.DM], 2020.
S. Alex Bradt, Jennifer Elder, Pamela E. Harris, Gordon Rojas Kirby, Eva Reutercrona, Yuxuan (Susan) Wang, and Juliet Whidden, Unit interval parking functions and the r-Fubini numbers, arXiv:2401.06937 [math.CO], 2024. See page 2.
Florian Bridoux, Caroline Gaze-Maillot, Kévin Perrot, and Sylvain Sené, Complexity of limit-cycle problems in Boolean networks, arXiv:2001.07391 [cs.DM], 2020.
A. Cayley, On the theory of the analytical forms called trees II, Phil. Mag., Vol. 18 (1859), pp. 374-378 = Math. Papers Vol. 4, pp. 112-115.
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seq., Vol. 3 (2000), Article 00.1.5.
J. L. Chandon, J. LeMaire, and J. Pouget, Dénombrement des quasi-ordres sur un ensemble fini, Math. Sci. Humaines, Vol. 62 (1978), pp. 61-80.
Grégory Chatel, Vincent Pilaud, and Viviane Pons, The weak order on integer posets, arXiv:1701.07995 [math.CO], 2017.
Chao-Ping Chen, Sharp inequalities and asymptotic series related to Somos' quadratic recurrence constant, Journal of Number Theory, Vol. 172 (March 2017), pp. 145-159.
William Y. C. Chen, Alvin Y. L. Dai, and Robin D. P. Zhou, Ordered Partitions Avoiding a Permutation of Length 3, arXiv preprint arXiv:1304.3187 [math.CO], 2013.
Ali Chouria, Vlad-Florin Drǎgoi, and Jean-Gabriel Luque, On recursively defined combinatorial classes and labelled trees, arXiv:2004.04203 [math.CO], 2020.
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.
Anders Claesson and T. Kyle Petersen, Conway's napkin problem, Amer. Math. Monthly, Vol. 114, No. 3 (2007), pp. 217-231.
Tyler Clark and Tom Richmond, The Number of Convex Topologies on a Finite Totally Ordered Set, 2013, to appear in Involve;
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, Vol. 4724 (2007), pp. 161-172.
Pierluigi Contucci, Emanuele Panizzi, Federico Ricci-Tersenghi, and Alina Sîrbu, A new dimension for democracy: egalitarianism in the rank aggregation problem, arXiv:1406.7642 [physics.soc-ph], 2014.
H. B. Curry, An Analysis of Logical Substitution, American Journal of Mathematics, Vol. 51, No. 3 (1929), pp. 363-84; see page 369.
N. G. de Bruijn, Enumerative combinatorial structures concerning structures, Nieuw Archief. voor Wisk., Vol. 11 (1963), pp. 142-161; see p. 150.
Ayhan Dil and Veli Kurt, Investigating Geometric and Exponential Polynomials with Euler-Seidel Matrices, J. Int. Seq., Vol. 14 (2011), Article 11.4.6.
Ayhan Dil and Veli Kurt, Polynomials related to harmonic numbers and evaluation of harmonic number series I, INTEGERS, Vol. 12 (2012), #A38.
Diego Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions, arXiv:math/0501052v2 [math.CA], 2005.
Frédéric Fauvet, Loïc Foissy, and Dominique Manchon, The Hopf algebra of finite topologies and mould composition, arXiv preprint arXiv:1503.03820, 2015
Valentin Féray, Cyclic inclusion-exclusion, arXiv preprint arXiv:1410.1772 [math.CO], 2014.
Philippe Flajolet, Stefan Gerhold, and Bruno Salvy, On the non-holonomic character of logarithms, powers and the n-th prime function, arXiv:math/0501379 [math.CO], 2005.
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, 2009; see page 109.
Aviezri S. Fraenkel and Moshe Mor, Combinatorial compression and partitioning of large dictionaries, Computer J., Vol. 26 (1983), pp. 336-343. See Tables 4 and 5.
Harvey M. Friedman, Concrete Mathematical Incompleteness: Basic Emulation Theory, Hilary Putnam on Logic and Mathematics, Outstanding Contributions to Logic, Vol. 9, Springer, Cham, 2018, pp. 179-234.
Florent Foucaud, Ralf Klasing and Peter J. Slater, Centroidal bases in graphs, arXiv preprint arXiv:1406.7490 [math.CO], 2014.
Wolfgang Gatterbauer and Dan Suciu, Approximate Lifted Inference with Probabilistic Databases, arXiv preprint arXiv:1412.1069 [cs.DB], 2014.
Wolfgang Gatterbauer and Dan Suciu, Dissociation and propagation for approximate lifted inference with standard relational database management systems, The VLDB Journal, Vol. 26, No. 1 (February 2017), pp 5-30; DOI 10.1007/s00778-016-0434-5.
Joël Gay and Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.
Christian Geist and Ulle Endriss, Automated search for impossibility theorems in social choice theory: ranking sets of objects, arXiv:1401.3866 [cs.AI], 2014; J. Artif. Intell. Res. (JAIR), Vol. 40 (2011), pp. 143-174.
Olivier Gérard, Re: Horse Race Puzzle.
Seyoum Getu, Louis W. Shapiro, Wen-jin Woan, and Leon C. Woodson, How to guess a generating function, SIAM J. Discrete Math., Vol. 5, No. 4 (1992), pp. 497-499.
Robert Gill, The number of elements in a generalized partition semilattice, Discrete mathematics, Vol. 186, No. 1-3 (1998), pp. 125-134. See Example 1.
Samuele Giraudo, Combinatorial operads from monoids, arXiv preprint arXiv:1306.6938 [math.CO], 2013.
Manfred Göbel, On the number of special permutation-invariant orbits and terms, in Applicable Algebra in Engin., Comm. and Comp. (AAECC 8), Vol. 8, No. 6 (1997), pp. 505-509.
W. Steven Gray and Makhin Thitsa, System Interconnections and Combinatorial Integer Sequences, in: System Theory (SSST), 2013 45th Southeastern Symposium on, Date of Conference: 11-11 March 2013.
Martin Griffiths and István Mező, A generalization of Stirling Numbers of the Second Kind via a special multiset, JIS, Vol. 13 (2010), Article 10.2.5.
O. A. Gross, Preferential arrangements, Amer. Math. Monthly, Vol. 69, No. 1 (1962), pp. 4-8.
Gottfried Helms, Discussion of a problem concerning summing of like powers, 2007.
Michael E. Hoffman, Updown categories: Generating functions and universal covers, arXiv preprint arXiv:1207.1705 [math.CO], 2012.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 41.
Marsden Jacques and Dennis Wong, Greedy Universal Cycle Constructions for Weak Orders, Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020): Algorithms and Discrete Applied Mathematics, pp. 363-370.
Jacques Marsden, Dennis Wong, and Kyounga Woo. Generating Gray codes for weak orders in constant amortized time, Discrete Mathematics, Vo. 343, No. 10 (2020), 111992.
Svante Janson, Euler-Frobenius numbers and rounding, arXiv preprint arXiv:1305.3512 [math.PR], 2013.
Marek Jarociński and Bartosz Maćkowiak, Online Appendix to "Granger-Causal-Priority and Choice of Variables in Vector Autoregressions", 2013.
Vít Jelínek, Ida Kantor, Jan Kynčl, and Martin Tancer, On the growth of the Möbius function of permutations, arXiv:1809.05774 [math.CO], 2018.
Niraj Khare, Rudolph Lorentz, and Catherine Huafei Yan, Bivariate Gončarov polynomials and integer sequences, Science China Mathematics, Vol. 57, No. 1 (2014), pp. 1561-1578; alternative link.
Dongseok Kim, Young Soo Kwon, and Jaeun Lee, Enumerations of finite topologies associated with a finite graph, arXiv preprint arXiv:1206.0550 [math.CO], 2012. See Th. 4.3. - From N. J. A. Sloane, Nov 09 2012
Donald E. Knuth, John Riordan, and N. J. A. Sloane, Correspondence, 1970.
Martin J. Kochanski, How many orders are there?
Ali Sinan Koksal, Yewen Pu, Saurabh Srivastava, Rastislav Bodik, Jasmin Fisher, and Nir Piterman, Synthesis of biological models from mutation experiments, Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 2013, pp. 469-482.
Takao Komatsu and José L. Ramírez, Some determinants involving incomplete Fubini numbers, arXiv:1802.06188 [math.NT], 2018.
Germain Kreweras, Une dualité élémentaire souvent utile dans les problèmes combinatoires, Mathématiques et Sciences Humaines 3 (1963): 31-41.
Alex Kumjian, David Pask, Aidan Sims, and Michael F. Whittaker, Topological spaces associated to higher-rank graphs, arXiv preprint arXiv:1310.6100 [math.OA], 2013.
Hans Maassen and Thom Bezembinder, Generating random weak orders and the probability of a Condorcet winner, Social Choice and Welfare, Vol. 19, No. 3 (2002), pp. 517-532.
P. A. MacMahon, Yoke-chains and multipartite compositions in connexion with the analytical forms called "trees, Proc. London Math. Soc., Vol. 22 (1891), pp. 330-346; reprinted in Coll. Papers I, pp. 600-616.
Victor Meally, Comparison of several sequences given in Motzkin's paper "Sorting numbers for cylinders...", letter to N. J. A. Sloane, N. D.
Elliott Mendelson, Races with Ties, Math. Mag., Vol. 55, No. 3 (1982), pp. 170-175.
István Mező, Periodicity of the last digits of some combinatorial sequences, J. Int. Seq., Vol. 17 (2014), Article 14.1.1; arXiv preprint, arXiv:1308.1637 [math.CO], 2013.
István Mező and Árpád Baricz, On the generalization of the Lambert W function with applications in theoretical physics, arXiv preprint arXiv:1408.3999 [math.CA], 2014.
Moshe Mor and Aviezri S. Fraenkel, Cayley permutations, Discrete Math., Vol. 48, No. 1 (1984), pp. 101-112.
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]
Todd Mullen, On Variants of Diffusion, Dalhousie University (Halifax, NS Canada, 2020).
Norihiro Nakashima and Shuhei Tsujie, Enumeration of Flats of the Extended Catalan and Shi Arrangements with Species, arXiv:1904.09748 [math.CO], 2019.
Roger B. Nelsen and Harvey Schmidt, Jr., Chains in power sets, Math. Mag., Vol. 64, No. 1 (1991), pp. 23-31.
S. Nkonkobe and V. Murali, On Some Identities of Barred Preferential Arrangements, arXiv preprint arXiv:1503.06173 [math.CO], 2015.
S. Nkonkobe and V. Murali. A study of a family of generating functions of Nelsen-Schmidt type and some identities on restricted barred preferential arrangements, Discrete Mathematics, Vol. 340 (2017), pp. 1122-1128.
Mathilde Noual and Sylvain Sene, Towards a theory of modelling with Boolean automata networks-I. Theorisation and observations, arXiv preprint arXiv:1111.2077 [cs.DM], 2011.
J.-C. Novelli and J.-Y. Thibon, Polynomial realizations of some trialgebras, Proc. Formal Power Series and Algebraic Combinatorics 2006 (San-Diego, 2006); arXiv:math/0605061 [math.CO], 2006.
J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014.
J.-C. Novelli, J.-Y. Thibon, and L. K. Williams, Combinatorial Hopf algebras, noncommutative Hall-Littlewood functions, and permutation tableaux, Adv. Math., Vol. 224, No. 4 (2010), pp. 1311-1348.
Arthur Nunge, Eulerian polynomials on segmented permutations, arXiv:1805.01797 [math.CO], 2018.
OEIS Wiki, Sorting numbers.
Karolina Okrasa and Paweł Rzążewski, Intersecting edge distinguishing colorings of hypergraphs, arXiv:1804.10470 [cs.DM], 2018.
K. A. Penson, P. Blasiak, G. Duchamp, A. Horzela, and A. I. Solomon, Hierarchical Dobinski-type relations via substitution and the moment problem, arXiv:quant-ph/0312202, 2003.
Tilman Piesk, Tree of weak orderings in concertina cube. Illustration of a(3) = 13, used with permission. See also the original of this figure on Wikimedia Commons.
Vincent Pilaud and Viviane Pons, Permutrees, arXiv preprint arXiv:1606.09643 [math.CO], 2016-2017.
Claudio de J. Pita Ruiz V., Some Number Arrays Related to Pascal and Lucas Triangles, J. Int. Seq., Vol. 16 (2013), Article 13.5.7.
Robert A. Proctor, Let's Expand Rota's Twelvefold Way For Counting Partitions!, arXiv:math/0606404 [math.CO], 2006-2007.
Helmut Prodinger, Ordered Fibonacci partitions, Canad. Math. Bull. 26 (1983), no. 3, 312--316. MR0703402 (84m:05012). [See F_n on page 312.]
Yash Puri and Thomas Ward, Arithmetic and growth of periodic orbits, J. Integer Seq., Vol. 4 (2001), Article 01.2.1.
S. Ramanujan, Notebook entry.
Joe Sawada and Dennis Wong, An Efficient Universal Cycle Construction for Weak Orders, University of Guelph, School of Computer Science (2019), presented at the 30th Coast Combinatorics Conference at University of Hawaii, Manoa.
Joe Sawada and Dennis Wong. Efficient universal cycle constructions for weak orders, 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.]
Benjamin Schreyer, Rigged Horse Numbers and their Modular Periodicity, arXiv:2409.03799 [math.CO], 2024. See p. 12.
N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, arXiv:math/0307064 [math.CO], 2003; Order, Vol. 21 (2004), pp. 83-89.
Jacob Sprittulla, The ordered Bell numbers as weighted sums of odd or even Stirling numbers of the second kind, arXiv:2109.12705 [math.CO], 2021.
Daniel J. Velleman and Gregory S. Call, Permutations and combination locks, Math. Mag., Vol. 68, No. 4 (1995), pp. 243-253.
Carl G. Wagner, Enumeration of generalized weak orders, Preprint, 1980. [Annotated scanned copy] Arch. Math., Vol. 39 (1982), pp. 147-152.
Carl G. Wagner and N. J. A. Sloane, Correspondence, 1980.
F. V. Weinstein, Notes on Fibonacci partitions, arXiv:math/0307150 [math.NT], 2003-2015 (see page 9).
Eric Weisstein's World of Mathematics, Combination Lock.
Wikipedia, Ordered Bell number.
Herbert S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 175, Eq. 5.2.6, 5.2.7.
Andrew T. Wilson, Torus link homology and the nabla operator, Journal of Combinatorial Theory, Series A, Vol. 154 (2018), pp. 129-144; arXiv preprint, arXiv:1606.00764 [math.CO], 2016.
Ai-Min Xu and Zhong-Di Cen, Some identities involving exponential functions and Stirling numbers and applications, J. Comput. Appl. Math., Vol. 260 (2014), pp. 201-207.
Yan X Zhang, Four Variations on Graded Posets, arXiv preprint arXiv:1508.00318 [math.CO], 2015.
Yi Zhu and Evgueni T. Filipov, An efficient numerical approach for simulating contact in origami assemblages, Proc. R. Soc. A, Vol. 475 (2019), 20190366.
FORMULA
a(n) = Sum_{k=0..n} k! * StirlingS2(n,k) (whereas the Bell numbers A000110(n) = Sum_{k=0..n} StirlingS2(n,k)).
E.g.f.: 1/(2-exp(x)).
a(n) = Sum_{k=1..n} binomial(n, k)*a(n-k), 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)^(-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
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
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: 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
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..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^(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)
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
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
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) = 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/(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
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
From Sergei N. Gladkovskii, from Oct 2011 to Oct 2013: (Start)
Continued fractions:
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).
E.g.f.: 1 + x/(G(0)-2*x) where G(k) = x + k + 1 - x*(k+1)/G(k+1).
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).
G.f.: 1 + x/G(0) where G(k) = 1 - 3*x*(k+1) - 2*x^2*(k+1)*(k+2)/G(k+1).
G.f.: 1/G(0) where G(k) = 1 - x*(k+1)/( 1 - 2*x*(k+1)/G(k+1) ).
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) ).
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) ). (End)
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) = 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
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
Conjecture: a(n) = Sum_{k=0..2^(n-1)-1} A284005(k) for n > 0 with a(0) = 1. - Mikhail Kurkov, Jul 08 2018
a(n) = A074206(k) for squarefree k with n prime factors. In particular a(n) = A074206(A002110(n)). - Amiram Eldar, May 13 2019
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
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
Sum_{n>=0} 1/a(n) = 2.425674839121428857970063350500499393706641093287018840857857170864211946122664... - Vaclav Kotesovec, Jun 17 2021
From Jacob Sprittulla, Oct 05 2021: (Start)
The following identities hold for sums over Stirling numbers of the second kind with even or odd second argument:
a(n) = 2 * Sum_{k=0..floor(n/2)} ((2k)! * Stirling2(n,2*k) ) - (-1)^n = 2*A052841-(-1)^n
a(n) = 2 * Sum_{k=0..floor(n/2)} ((2k+1)!* Stirling2(n,2*k+1))+ (-1)^n = 2*A089677+(-1)^n
a(n) = Sum_{k=1..floor((n+1)/2)} ((2k-1)!* Stirling2(n+1,2*k))
a(n) = Sum_{k=0..floor((n+1)/2)} ((2k)! * Stirling2(n+1,2*k+1)). (End)
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
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
# next Maple program:
b:= proc(n, k) option remember;
`if`(n=0, k!, k*b(n-1, k)+b(n-1, k+1))
end:
a:= n-> b(n, 0):
seq(a(n), n=0..20); # Alois P. Heinz, Aug 04 2021
MATHEMATICA
Table[(PolyLog[-z, 1/2] + KroneckerDelta[z])/2, {z, 0, 20}] (* 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 *)
Table[HurwitzLerchPhi[1/2, -n, 0]/2, {n, 0, 20}] (* Jean-François Alcover, Jan 31 2016 *)
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 *)
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 *)
Prepend[Table[-(-1)^k HurwitzLerchPhi[2, -k, 0]/2, {k, 1, 50}], 1] (* Federico Provvedi, Sep 05 2020 *)
Table[Sum[k!*StirlingS2[n, k], {k, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Nov 22 2020 *)
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 */
(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 */
(PARI) {a(n) = if( n<1, n==0, sum(k=1, n, binomial(n, k) * a(n-k)))}; /* Michael Somos, Jul 16 2017 */
(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 */
(Sage)
@CachedFunction
[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
(Python)
from math import factorial
from sympy.functions.combinatorial.numbers import stirling
def A000670(n): return sum(factorial(k)*stirling(n, k) for k in range(n+1)) # Chai Wah Wu, Nov 08 2022
(Magma)
R<x>:=PowerSeriesRing(Rationals(), 40);
Coefficients(R!(Laplace( 1/(2-Exp(x)) ))); // G. C. Greubel, Jun 11 2024
CROSSREFS
See A240763 for a list of the actual preferential arrangements themselves.
A000629, this sequence, A002050, A032109, A052856, A076726 are all more-or-less the same sequence. - N. J. A. Sloane, Jul 04 2012
Asymptotic to A034172.
Cf. A002144, A002869, A004121, A004122, A007047, A007318, A048144, A053525, A080253, A080254, A011782, A154921, A162312, A163204, A242280, A261959, A290376, A074206.
Column k=1 of A326322.
KEYWORD
nonn,core,nice,easy,changed
AUTHOR
STATUS
approved