Search: id:A000670 Results 1-1 of 1 results found. %I A000670 M2952 N1191 %S A000670 1,1,3,13,75,541,4683,47293,545835,7087261,102247563,1622632573, %T A000670 28091567595,526858348381,10641342970443,230283190977853, %U A000670 5315654681981355,130370767029135901,3385534663256845323 %N A000670 Number of preferential arrangements of n labeled elements; or number of weak orders on n labeled elements. %C A000670 Number of ways n competitors can rank in a competition, allowing for the possibility of ties. %C A000670 Also number of asymmetric generalized weak orders on n points. %C A000670 Also called the ordered Bell numbers, i.e. the number of ordered partitions of {1,..,n}. %C A000670 A weak order is a relation that is transitive and complete. %C A000670 Called Fubini numbers by Comtet: counts formulae in Fubini theorem when switching the order of summation in multiple sums. - Olivier Gerard, Sep 30, 2002 %C A000670 If the points are unlabeled then the answer is a(0) = 1, a(n) = 2^(n-1) (cf. A011782). %C A000670 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 (tch(AT)maths.warwick.ac.uk), Feb 10 2003 %C A000670 Also number of labeled (1+2)-free posets. - Detlef Pauly, May 25 2003 %C A000670 Also the number of chains of subsets starting with the empty set and ending with a set of n distinct objects. - Andy Niedermaier (aniedermaier(AT)hmc.edu), Feb 20 2004 %C A000670 Stirling transform of A007680(n) = [3, 10, 42, 216, . . . ] gives [3, 13,75,541,...]. - Michael Somos Mar 04 2004 %C A000670 Stirling transform of a(n)=[1,3,13,75,...] is A083355(n)=[1,4,23,175, ...]. - Michael Somos Mar 04 2004 %C A000670 Stirling transform of A000142(n)=[1,2,6,24,120,...] is a(n)=[1,3,13,75, ...]. - Michael Somos Mar 04 2004 %C A000670 Stirling transform of A005359(n-1)=[1,0,2,0,24,0,...] is a(n-1)=[1,1, 3,13,75,...]. - Michael Somos Mar 04 2004 %C A000670 Stirling transform of A005212(n-1)=[0,1,0,6,0,120,0,...] is a(n-1)=[0, 1,3,13,75,...]. - Michael Somos Mar 04 2004 %C A000670 Unreduced denominators in convergent to log(2) = lim[n->inf, na(n-1)/ a(n)]. %C A000670 a(n) is congruent to a(n+(p-1)p^(h-1)) (mod p^h) for n>=h (see Barsky). %C A000670 Stirling-Bernoulli transform of 1/(1-x^2). - Paul Barry (pbarry(AT)wit.ie), Apr 20 2005 %C A000670 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 A000670 With p(n) = the number of integer partitions of n, p(i) = the number of parts of the i-th partition of n, d(i) = the number of different parts of the i-th partition of n, p(j,i) = the j-th part of the i-th partition of n, m(i,j) = multiplicity of the j-th part of the i-th partition of n, sum_{i=1}^{p(n)} = sum over i and prod_{j=1}^{d(i)} = product over j one has: a(n) = sum_{i=1}^{p(n)} (n!/(prod_{j=1}^{p(i)}p(i, j)!)) * (p(i)!/(prod_{j=1}^{d(i)} m(i,j)!)) - Thomas Wieder (wieder.thomas(AT)t-online.de), May 18 2005 %C A000670 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 A000670 Occurs also as first column of a matrix-inversion occuring in a sum-of-like-powers problem. Consider the problem for any fixed natural number m>2 of finding solutions to the equation sum(k=1,n,k^m) = (k+1)^m. Erdos conjectured that there are no solutions for n,m>2. Let D be the matrix of differences of D[m,n] := sum(k=1,n,k^m) - (k+1)^m. Then the generating functions for the rows of this matrix D constitute a set of polynomials in n (for varying n along columns) and the m-th polynomial defining the m-th row. Let GF_D be the matrix of the coefficients of this set of polynomials. Then the present sequence is the (unsigned) first column of GF_D^-1. - Gottfried Helms, Apr 01 2007 %C A000670 Assuming A=ln2, D is d/dx and f(x)=x/(exp(x)-1), we have a(n) = (n!/2A^(n+1)) sum( k=0 to n, (A^k/k!) D^n f(-A) ) which gives Wilf's asymptotic value when n tends to infinity. Equivalently, D^n f(-a) = 2( A*a(n)-2*a(n-1) ). - Martin Kochanski (mjk(AT)cardbox.com), May 10 2007 %C A000670 List partition transform (see A133314) of (1,-1,-1,-1,...). - Tom Copeland (tcjpn(AT)msn.com), Oct 24 2007 %C A000670 First column of A154921. [From Mats Granvik (mats.granvik(AT)abo.fi), Jan 17 2009] %C A000670 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}. [From Martin Griffiths (griffm(AT)essex.ac.uk), Mar 25 2009] %C A000670 Starting (1, 3, 13, 75,...) = row sums of triangle A163204 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Jul 23 2009] %C A000670 Equals double inverse binomial transform of A007047: (1, 3, 11, 51,...). [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 04 2009] %C A000670 Contribution from Miklos Kristof (kristmikl(AT)freemail.hu), Nov 02 2009: (Start) %C A000670 If f(x)=sum(c(n)*x^n ,n=0..infinity) converges for every x, then %C A000670 sum(f(n*x)/2^(n+1), n=0..infinity) = sum(c(n)*a(n)*x^n, n=0..infinity). %C A000670 Example: sum(exp(n*x)/2^(n+1), n=0..infinity) = sum(a(n)*x^n/n!, n=0..infinity)= 1/(2-exp(x)) = E.g.f. (End) %D A000670 Ralph W. Bailey, "The number of weak orderings of a finite set", Social Choice and Welfare, Vol. 15 (1998), pp. 559-562. %D A000670 N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 44 (P(x)). %D A000670 Kenneth S. Brown, Buildings, Springer-Verlag, 1988 %D A000670 A. Cayley, On the theory of the analytical forms called trees II, Phil. Mag. 18 (1859), 374-378 = Math. Papers Vol. 4, pp. 112-115. %D A000670 J. L. Chandon, J. LeMaire and J. Pouget, Denombrement des quasi-ordres sur un ensemble fini, Math. Sci. Humaines, No. 62 (1978), 61-80. %D A000670 A. Claesson and T. K. Petersen, Conway's napkin problem, Amer. Math. Monthly, 114 (No. 3, 2007), 217-231. %D A000670 Pietro Codara, Ottavio M. D'Antona and Vincenzo Marra, Best Approximation of Ruspini Partitions in Goedel Logic, in Symbolic and Quantitative Approaches to Reasoning with Uncertainty, Lecture Notes in Computer Science, Volume 4724/2007, Springer-Verlag. [From N. J. A. Sloane, Jul 09 2009] %D A000670 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 228. %D A000670 J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 13, pp 4, Ellipses, Paris 2008. %D A000670 P. J. Freyd, On the size of Heyting semi-lattices, preprint, 2002. %D A000670 S. Getu et al., How to guess a generating function, SIAM J. Discrete Math., 5 (1992), 497-499. %D A000670 I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983. %D A000670 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd Ed., 1994, exercise 7.44 (pp. 378, 571). %D A000670 O. A. Gross, Preferential arrangements, Amer. Math. Monthly, 69 (1962), 4-8. %D A000670 Hans Maassen and Thom Bezembinder, Generating random weak orders and the probability of a Condorcet winner, Social Choice and Welfare, 19,3 (2002), 517-532. %D A000670 P. A. MacMahon, Yoke-trains and multipartite compositions in connexion with the analytical forms called "trees", Proc. London Math. Soc. 22 (1891), 330-346; reprinted in Coll. Papers I, pp. 600-616. %D A000670 E. Mendelsohn, Races with ties, Math. Mag. 55 (1982), 170-175. %D A000670 M. Mor and A. S. Fraenkel, Cayley permutations, Discrete Math., 48 (1984), 101-112. %D A000670 T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. %D A000670 T. S. Motzkin, Sorting numbers ...: for a link to this paper see A000262. %D A000670 M. Muresan, Generalized Fubini numbers. Stud. Cerc. Mat. 37 (1985), no. 1, pp. 70-76. %D A000670 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence). %D A000670 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). %D A000670 R. P. Stanley, Enumerative Combinatorics, Wadsworth, Vol. 1, 1986; see Example 3.15.10, p. 146. %D A000670 D. J. Velleman and G. S. Call, Permutations and combination locks, Math. Mag., 68 (1995), 243-253. %D A000670 C. G. Wagner, Enumeration of generalized weak orders. Arch. Math. (Basel) 39 (1982), no. 2, 147-152. %D A000670 H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 147. %H A000670 N. J. A. Sloane, Table of n, a(n) for n = 0..100 %H A000670 D. Barsky, Analyse p-adique et suites classiques de nombres, Sem. Loth. Comb. B05b (1981) 1-21. %H A000670 P. Blasiak, K. A. Penson and A. I. Solomon, Dobinski-type relations and the log-normal distribution. %H A000670 P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5. %H A000670 P. Flajolet, S. Gerhold and B. Salvy, On the non-holonomic character of logarithms, powers and the n-th prime function %H A000670 P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 109 %H A000670 Olivier Gerard, Re: Horse Race Puzzle. %H A000670 M. Goebel, On the number of special permutation-invariant orbits and terms, in Applicable Algebra in Engin., Comm. and Comp. (AAECC 8), Volume 8, Number 6, 1997, pp. 505-509 (Lect. Notes Comp. Sci.) %H A000670 Gottfried Helms, Discussion of a problem concerning summing of like powers %H A000670 INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 41 %H A000670 M. J. Kochanski, How many orders are there?. %H A000670 J.-C. Novelli and J.-Y. Thibon, Polynomial realizations of some trialgebras, Proc. Formal Power Series and Algebraic Combinatorics 2006 (San-Diego, 2006) %H A000670 K. A. Penson, P. Blasiak, G. Duchamp, A. Horzela and A. I. Solomon, Hierarchical Dobinski-type relations via substitution and the moment problem %H A000670 Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1. %H A000670 S. Ramanujan, Notebook entry %H A000670 N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 83-89. %H A000670 Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics. %H A000670 H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 175, Eq. 5.2.6, 5.2.7. %H A000670 Index entries for "core" sequences %H A000670 Index entries for related partition-counting sequences %F A000670 a(n) = Sum_{ k=1 to n} k! StirlingS2(n, k) (whereas the Bell numbers A000110(n) = Sum_{ k=1 to n} StirlingS2(n, k)). %F A000670 E.g.f.: 1/(2-exp(x)). Recurrence: a(n)=Sum_{k>0} binomial(n, k)*a(n-k), a(0)=1. %F A000670 The e.g.f. y(x) satisfies y' = 2y^2 - y. %F A000670 a(n) is asymptotic to (1/2)*n!*log_2(e)^(n+1), where log_2(e) = 1.442695... [Wilf] %F A000670 For n >= 1, a(n) = (n!/2) * Sum from k=-infinity to infinity of (log(2) + 2 pi i k)^(-n-1) - from Dean Hickerson (dean.hickerson(AT)yahoo.com) %F A000670 a(n) = ((x*d/dx)^n)(1/(2-x)) evaluated at x=1. - Karol A. Penson (penson(AT)lptl.jussieu.fr), Sep 24 2001 %F A000670 For n>=1, a(n) = sum(k>=1, (k-1)^n/2^k) = A000629(n)/2. - Benoit Cloitre (benoit7848c(AT)orange.fr), Sep 08 2002 %F A000670 Value of the n-th Eulerian polynomial (cf. A008292) at x=2. - Vladeta Jovovic (vladeta(AT)eunet.rs), Sep 26 2003 %F A000670 a(n) = A076726(n)/2. %F A000670 a(n)=sum{k=0..n, (-1)^k*k!*S2(n+1, k+1)(1+(-1)^k)/2}; - Paul Barry (pbarry(AT)wit.ie), Apr 20 2005 %F A000670 a(n) + a(n+1) = 2*A005649(n) . - Philippe DELEHAM, May 16 2005 - Thomas Wieder (wieder.thomas(AT)t-online.de), May 18 2005 %F A000670 Equals inverse binomial transform of A000629. - Gary W. Adamson (qntmpkt(AT)yahoo.com), May 30 2005 %F A000670 First Eulerian transform of the powers of 2 [A000079]. See A000142 for definition of FET. - Ross La Haye (rlahaye(AT)new.rr.com), Feb 14 2005 %F A000670 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 A000670 Recurrence: 2a(n)=(a+1)^n where superscripts are converted to subscripts after binomial expansion - reminiscent of Bernoulli numbers' B_n=(B+1)^n - Martin Kochanski (mjk(AT)cardbox.com), May 10 2007 %F A000670 a(n) = (-1)^n * n!*Laguerre(n,P((.),2)), umbrally, where P(j,t) are the polynomials in A131758. - Tom Copeland (tcjpn(AT)msn.com), Sep 27 2007 %F A000670 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 (penson(AT)lptl.jussieu.fr), Oct 04 2007 %F A000670 a(n)=Sum_{k, 0<=k<=n} A131689(n,k). [From Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Nov 03 2008] %F A000670 Contribution from Peter Bala (pbala(AT)talktalk.net), Jul 01 2009: (Start) %F A000670 ANALOGY WITH THE BERNOULLI NUMBERS. %F A000670 We enlarge upon the above comment of M. Kochanski. %F A000670 The Bernoulli polynomials B_n(x), n = 0,1,..., are given by the formula %F A000670 (1)... B_n(x) := sum {k = 0..n} binomial(n,k)*B(k)*x^(n-k), %F A000670 where B(n) denotes the sequence of Bernoulli numbers B(0) = 1, %F A000670 B(1) = -1/2, B(2) = 1/6, B(3) = 0, .... %F A000670 By analogy, we associate with the present sequence an Appell sequence %F A000670 of polynomials {P_n(x)}n>=0 defined by %F A000670 (2)... P_n(x) := sum {k = 0..n} binomial(n,k)*a(k)*x^(n-k). %F A000670 These polynomials have similar properties to the Bernoulli polynomials. %F A000670 The first few values are P_0(x) = 1, P_1(x) = x + 1, %F A000670 P_2(x) = x^2 + 2*x + 3, P_3(x) = x^3 + 3*x^2 + 9*x + 13 and %F A000670 P_4(x) = x^4 + 4*x^3 + 18*x^2 + 52*x + 75. See A154921 for the %F A000670 triangle of coefficients of these polynomials. %F A000670 The e.g.f. for this polynomial sequence is %F A000670 (3)... exp(x*t)/(2 - exp(t)) = 1 + (x + 1)*t + (x^2 + 2*x + 3)*t^2/2! %F A000670 + .... %F A000670 The polynomials satisfy the difference equation %F A000670 (4)... 2*P_n(x - 1) - P_n(x) = (x - 1)^n, %F A000670 and so may be used to evaluate the weighted sums of powers of integers %F A000670 (1/2)*1^m + (1/2)^2*2^m + (1/2)^3*3^m + ... + (1/2)^(n-1)*(n-1)^m %F A000670 via the formula %F A000670 (5)... sum {k = 1..n-1} (1/2)^k*k^m = 2*P_m(0) - (1/2)^(n-1)*P_m(n), %F A000670 analogous to the evaluation of the sums 1^m + 2^m + ... + (n-1)^m in %F A000670 terms of Bernoulli polynomials. %F A000670 This last result can be generalised to %F A000670 (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 A000670 For more properties of the polynomials P_n(x) refer to A154921. %F A000670 For further information on weighted sums of powers of integers and %F A000670 the associated polynomial sequences see A162312. %F A000670 The present sequence also occurs in the evaluation of another sum of %F A000670 powers of integers. Define %F A000670 (7)... S_m(n) := sum {k = 1..n-1} (1/2)^k*((n-k)*k)^m, m = 1,2,.... %F A000670 Then %F A000670 (8)... S_m(n) = (-1)^m *[2*Q_m(-n) - (1/2)^(n-1)*Q_m(n)], %F A000670 where Q_m(x) are polynomials in x given by %F A000670 (9)... Q_m(x) = sum {k = 0..m} a(m+k)*binomial(m,k)*x^(m-k). %F A000670 The first few values are Q_1(x) = x + 3, Q_2(x) = 3*x^2 + 26*x + 75 %F A000670 and Q_3(x) = 13*x^3 + 225*x^2 + 1623*x + 4683. %F A000670 For example, m = 2 gives %F A000670 (10)... S_2(n) := sum {k = 1..n-1} (1/2)^k*((n-k)*k)^2 %F A000670 = 2*(3*n^2 - 26*n + 75) - (1/2)^(n-1)*(3*n^2 + 26*n + 75). %F A000670 (End) %e A000670 Let the points be labeled 1,2,3,... a(2) = 3: 1<2, 2<1, 1=2; a(3) = 13: 1<2<3, 1<3<2, ... (6 such), 1=2<3, 1=3<2, 2=3<1, 1<2=3, 2<1=3, 3<1=2, 1=2=3. %e A000670 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. %p A000670 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 A000670 with(combstruct); SeqSetL := [S, {S=Sequence(U), U=Set(Z,card >= 1)}, labeled]; seq(count(SeqSetL,size=j),j=1..12); %p A000670 with(combinat):a:=n->sum(sum((-1)^(k-i)*binomial(k, i)*i^n, i=0..n),k=0..n): seq(a(n), n=0..18); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 03 2007 %t A000670 Table[ PolyLog[ -z, 1/2 ] /2, {z, 1, 11} ] (from Wouter Meeussen) %t A000670 Clear[a, n, m, k] 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 (rlbagulatftn(AT)yahoo.com), Sep 13 2008 %o A000670 (PARI) a(n)=if(n<0,0,n!*polcoeff(subst(1/(1-y),y,exp(x+x*O(x^n))-1),n)) %Y A000670 Binomial transform of A052841. %Y A000670 Inverse binomial transform of A000629 - Joe Keane (jgk(AT)jgk.org). %Y A000670 Asymptotic to A034172. Cf. A053525, A002869, A004121, A004122. %Y A000670 For n>0, a(n)=A052882(n)/n. %Y A000670 Cf. A080253, A080254, A011782. %Y A000670 A052856(n)=1+a(n), if n>0. %Y A000670 First row of array A094416 (generalized ordered Bell numbers). %Y A000670 Diagonal of A135313. [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 19 2008] %Y A000670 A154921, A162312. [From Peter Bala (pbala(AT)talktalk.net), Jul 01 2009] %Y A000670 A163204 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Jul 23 2009] %Y A000670 A007047 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 04 2009] %Y A000670 Sequence in context: A074517 A007178 A034172 this_sequence A032036 A026072 A063646 %Y A000670 Adjacent sequences: A000667 A000668 A000669 this_sequence A000671 A000672 A000673 %K A000670 easy,core,nonn,nice,new %O A000670 0,3 %A A000670 N. J. A. Sloane (njas(AT)research.att.com). Search completed in 0.009 seconds