|
| |
|
|
A000670
|
|
Fubini numbers: number of preferential arrangements of n labeled elements; or number of weak orders on n labeled elements; or number of ordered partitions of [n].
(Formerly M2952 N1191)
|
|
525
|
|
|
|
1, 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563, 1622632573, 28091567595, 526858348381, 10641342970443, 230283190977853, 5315654681981355, 130370767029135901, 3385534663256845323, 92801587319328411133, 2677687796244384203115
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Number of ways n competitors can rank in a competition, allowing for the possibility of ties.
Also number of asymmetric generalized weak orders on n points.
Also called the ordered Bell numbers.
A weak order is a relation that is transitive and complete.
Called Fubini numbers by Comtet: counts formulas in Fubini theorem when switching the order of summation in multiple sums. - Olivier Gérard, Sep 30 2002 [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 & 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
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
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
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
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
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
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
"{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)
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
|
|
|
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
|
Jean-Christophe Aval, Adrien Boussicault, and Philippe Nadeau, Tree-like Tableaux, Electronic Journal of Combinatorics, Vol. 20, No. 4 (2013), #P34.
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.
Olivier Bodini, Antoine Genitrini, and Mehdi Naima, Ranked Schröder Trees, arXiv:1808.08376 [cs.DS], 2018.
Anders Claesson and T. Kyle Petersen, Conway's napkin problem, Amer. Math. Monthly, Vol. 114, No. 3 (2007), pp. 217-231.
Elliott Mendelson, Races with Ties, Math. Mag., Vol. 55, No. 3 (1982), pp. 170-175.
Moshe Mor and Aviezri S. Fraenkel, Cayley permutations, Discrete Math., Vol. 48, No. 1 (1984), pp. 101-112.
Roger B. Nelsen and Harvey Schmidt, Jr., Chains in power sets, Math. Mag., Vol. 64, No. 1 (1991), pp. 23-31.
Vincent Pilaud and Viviane Pons, Permutrees, arXiv preprint arXiv:1606.09643 [math.CO], 2016-2017.
|
|
|
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) 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
a(n) = Sum_{k=0..n} (-1)^k*k!*Stirling2(n+1, k+1)*(1+(-1)^k)/2. - Paul Barry, Apr 20 2005
a(n) = 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
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
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
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
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
E.g.f.: 1 + x/(G(0)-2*x) where G(k) = x + k + 1 - x*(k+1)/G(k+1); (continued fraction, Euler's 1st kind, 1-step). - Sergei N. Gladkovskii, Jul 11 2012
E.g.f. (2 - 2*x)*(1 - 2*x^3/(8*x^2 - 4*x + (x^2 - 4*x + 2)*G(0)))/(x^2 - 4*x + 2) where G(k) = k^2 + k*(x+4) + 2*x + 3 - x*(k+1)*(k+3)^2 /G(k+1); (continued fraction, Euler's 1st kind, 1-step). - Sergei N. Gladkovskii, Oct 01 2012
G.f.: 1 + x/G(0) where G(k) = 1 - 3*x*(k+1) - 2*x^2*(k+1)*(k+2)/G(k+1); (continued fraction). - Sergei N. Gladkovskii, Jan 11 2013
G.f.: 1/G(0) where G(k) = 1 - x*(k+1)/( 1 - 2*x*(k+1)/G(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Mar 23 2013
a(n) is always odd. For odd prime p and n >= 1, a((p-1)*n) = 0 (mod p). - Peter Bala, Sep 18 2013
G.f.: 1 + x/Q(0), where Q(k) = 1 - 3*x*(2*k+1) - 2*x^2*(2*k+1)*(2*k+2)/( 1 - 3*x*(2*k+2) - 2*x^2*(2*k+2)*(2*k+3)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Sep 23 2013
G.f.: T(0)/(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
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
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
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.
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):
|
|
|
MATHEMATICA
|
Table[(PolyLog[-z, 1/2] + KroneckerDelta[z])/2, {z, 0, 20}] (* Wouter Meeussen *)
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 *)
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
def A000670(n) : return 1 if n == 0 else add(A000670(k)*binomial(n, k) for k in range(n))
(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
(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
|
|
|
CROSSREFS
|
See A240763 for a list of the actual preferential arrangements themselves.
Cf. A002144, A002869, A004121, A004122, A007047, A007318, A048144, A053525, A080253, A080254, A011782, A154921, A162312, A163204, A242280, A261959, A290376, A074206.
|
|
|
KEYWORD
|
nonn,core,nice,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
