|
| |
|
|
A000629
|
|
Number of necklaces of partitions of n+1 labeled beads.
|
|
141
|
|
|
|
1, 2, 6, 26, 150, 1082, 9366, 94586, 1091670, 14174522, 204495126, 3245265146, 56183135190, 1053716696762, 21282685940886, 460566381955706, 10631309363962710, 260741534058271802, 6771069326513690646, 185603174638656822266, 5355375592488768406230
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
Also the number of logically distinct strings of first order quantifiers in which n variables occur (C. S. Peirce, c. 1903). - Stephen Pollard (spollard(AT)truman.edu), Jun 07 2002
Stirling transform of A052849(n) = [2, 4, 12, 48, 240, ...] is a(n) = [2, 6, 26, 150, 1082, ...]. - Michael Somos, Mar 04 2004
Stirling transform of A000142(n-1) = [1, 1, 2, 6, 24, ...] is a(n-1) = [1, 2, 6, 26, ...]. - Michael Somos, Mar 04 2004
Stirling transform of (-1)^n * A024167(n-1) = [0, 1, -1, 5, -14, 94, ...] is a(n-2) = [0, 1, 2, 6, 26, ...]. - Michael Somos, Mar 04 2004
The asymptotic expansion of 2*log(n) - (2^1*log(1) + 2^2*log(2) + ... + 2^n*log(n))/2^n is (a(1)/1)/n + (a(2)/2)/n^2 + (a(3)/3)/n^3 + ... - Michael Somos, Aug 22 2004
This is the sequence of cumulants of the probability distribution of the number of tails before the first head in a sequence of fair coin tosses. - Michael Hardy (hardy(AT)math.umn.edu), May 01 2005
This is the number of cyclically ordered partitions of n+1 labeled points. The ordered version is A000670. - Michael Somos, Jan 08 2011
A000670(n+1) = p(n+1) where p(x) is the unique degree-n polynomial such that p(k) = a(k) for k = 0, 1, ..., n. - Michael Somos, Apr 27 2012
Row sums of A154921 as conjectured above by Granvik. a(n) gives the number of outcomes of a race between n horses H1,...,Hn, where if a horse falls it is not ranked. For example, when n = 2 the 6 outcomes are a dead heat, H1 wins H2 second, H2 wins H1 second, H1 wins H2 falls, H2 wins H1 falls or both fall. - Peter Bala, May 15 2012
Also the number of disjoint areas of a Venn diagram for n multisets. - Aurelian Radoaca, Jun 27 2016
Also the number of ways of ordering n nonnegative integers, allowing for the possibility of ties, and also comparing the smallest integers with 0. Each comparison with 0 gives two possibilities, x > 0 or x=0. As such, without comparison with 0, we get A000670, the number of ways of ordering n nonnegative integers, allowing for the possibility of ties, or the number of ways n competitors can rank in a competition, allowing for the possibility of ties. For instance, for 2 nonnegative integers x,y, there are the following 6 ways of ordering them: x = y = 0, x = y > 0, x > y = 0, x > y > 0, y > x = 0, y > x > 0. - Aurelian Radoaca, Jul 09 2016
Also the number of ordered set partitions of subsets of {1,...,n}. Also the number of chains of distinct nonempty subsets of {1,...,n}. - Gus Wiseman, Feb 01 2019
Number of combinations of a Simplex lock having n buttons.
Also the number of vertices in the axis-aligned polytope consisting of all vectors x in R^n where, for all k in {1,...,n}, the k-th smallest coordinate of x lies in the interval [0, k]. - Adam P. Goucher, Jan 18 2023
Number of idempotent Boolean relation matrices whose complement is also idempotent. See Rosenblatt link. - Geoffrey Critzer, Feb 26 2023
|
|
|
REFERENCES
|
R. Austin, R. K. Guy, and R. Nowakowski, unpublished notes, circa 1987.
N. G. de Bruijn, Asymptotic Methods in Analysis, Dover, 1981, p. 36.
Eric Hammer, The Calculations of Peirce's 4.453, Transactions of the Charles S. Peirce Society, Vol. 31 (1995), pp. 829-839.
D. E. Knuth, personal communication.
J. D. E. Konhauser et al., Which Way Did the Bicycle Go?, MAA 1996, p. 174.
Charles Sanders Peirce, Collected Papers, eds. C. Hartshorne and P. Weiss, Harvard University Press, Cambridge, Vol. 4, 1933, pp. 364-365. (CP 4.453 in the electronic edition of The Collected Papers of Charles Sanders Peirce.)
Dawidson Razafimahatolotra, Number of Preorders to Compute Probability of Conflict of an Unstable Effectivity Function, Preprint, Paris School of Economics, University of Paris I, Nov 23 2007.
|
|
|
LINKS
|
|
|
|
FORMULA
|
O.g.f.: Sum_{n>=0} 2^n*n!*x^n / Product_{k=0..n} (1+k*x). - Paul D. Hanna, Jul 20 2011
E.g.f.: exp(x) / (2 - exp(x)) = d/dx log(1 / (2 - exp(x))).
a(n) = Sum_{k>=1} k^n/2^k.
a(n) = 1 + Sum_{j=0..n-1} C(n, j)*a(j).
a(n) = round(n!/log(2)^(n+1)) (just for n <= 15). - Henry Bottomley, Jul 04 2000
a(n) = Sum_{k=0..n} (-1)^(n-k)*Stirling2(n, k)*k!*2^k. - Vladeta Jovovic, Sep 29 2003
a(n) = Sum_{k=0..n} Stirling2(n+1, k+1)*k!. - Paul Barry, Apr 20 2005
a(n) = 2*(-1)^n * n!*Laguerre(n,P((.),2)), umbrally, where P(j,t) are the polynomials in A131758. - Tom Copeland, Sep 28 2007
a(n) = 2^n*A(n,1/2); A(n,x) the Eulerian polynomials. - Peter Luschny, Aug 03 2010
a(n) = (-1)^n*b(n), where b(n) = -2*Sum_{k=0..n-1} binomial(n,k)*b(k), b(0)=1. - Vladimir Kruchinin, Jan 29 2011
Row sums of A028246. Let f(x) = x+x^2. Then a(n+1) = (f(x)*d/dx)^n f(x) evaluated at x = 1. - Peter Bala, Oct 06 2011
O.g.f.: 1+2*x/(U(0)-2*x) where U(k)=1+3*x+3*x*k-2*x*(k+2)*(1+x+x*k)/U(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 14 2011
E.g.f.: exp(x)/(2 - exp(x)) = 2/(2-Q(0))-1; Q(k)=1+x/(2*k+1-x*(2*k+1)/(x+(2*k+2)/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Nov 14 2011
G.f.: 1 / (1 - 2*x / (1 - 1*x / (1 - 4*x / (1 - 2*x / (1 - 6*x / ...))))). - Michael Somos, Apr 27 2012
G.f.: 1/G(0) where G(k) = 1 - x*(2*k+2)/( 1 - x*(k+1)/G(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Mar 23 2013
E.g.f.: 1/E(0) where E(k) = 1 - x/(k+1)/(1 - 1/(1 + 1/E(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Mar 27 2013
G.f.: T(0)/(1-2*x), where T(k) = 1 - 2*x^2*(k+1)^2/(2*x^2*(k+1)^2 - (1 - 2*x - 3*x*k)*(1 - 5*x - 3*x*k)/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 29 2013
a(n) = log(2)*integral_{x>=0} (ceiling(x))^n * 2^(-x) dx. - Peter Bala, Feb 06 2015
|
|
|
EXAMPLE
|
a(2)=6: the necklace representatives on 1,2,3 are ({123}), ({12},{3}), ({13},{2}), ({23},{1}), ({1},{2},{3}), ({1},{3},{2})
G.f. = 1 + 2*x + 6*x^2 + 26*x^3 + 150*x^4 + 1082*x^5 + 9366*x^6 + 94586*x^7 + ...
The a(3) = 26 ordered set partitions of subsets of {1,2,3} are:
{} {{1}} {{2}} {{3}} {{12}} {{13}} {{23}} {{123}}
{{1}{2}} {{1}{3}} {{2}{3}} {{1}{23}}
{{2}{1}} {{3}{1}} {{3}{2}} {{12}{3}}
{{13}{2}}
{{2}{13}}
{{23}{1}}
{{3}{12}}
{{1}{2}{3}}
{{1}{3}{2}}
{{2}{1}{3}}
{{2}{3}{1}}
{{3}{1}{2}}
{{3}{2}{1}}
(End)
|
|
|
MAPLE
|
spec := [ B, {B=Cycle(Set(Z, card>=1))}, labeled ]; [seq(combstruct[count](spec, size=n), n=0..20)];
a:=n->add(Stirling2(n+1, k)*(k-1)!, k=1..n+1); # Mike Zabrocki, Feb 05 2005
|
|
|
MATHEMATICA
|
a[ 0 ] = 1; a[ n_ ] := (a[ n ] = 1 + Sum[ Binomial[ n, k ] a[ n-k ], {k, 1, n} ])
a[ n_] := If[ n<0, 0, PolyLog[ -n, 1/2]]; (* Michael Somos, Mar 07 2011 *)
Table[Sum[(-1)^(n-k) StirlingS2[n, k]k! 2^k, {k, 0, n}], {n, 0, 20}] (* Harvey P. Dale, Oct 21 2011 *)
Join[{1}, Rest[t=30; Range[0, t]! CoefficientList[Series[2/(2 - Exp[x]), {x, 0, t}], x]]] (* Vincenzo Librandi, Jan 02 2016 *)
|
|
|
PROG
|
(PARI) {a(n) = if( n<0, 0, n! * polcoeff(subst( (1 + y) / (1 - y), y, exp(x + x * O(x^n)) - 1), n))} /* Michael Somos, Mar 04 2004 */
(PARI) {a(n)=polcoeff(sum(m=0, n, 2^m*m!*x^m/prod(k=1, m, 1+k*x+x*O(x^n))), n)} \\ Paul D. Hanna, Jul 20 2011
(Python)
from math import comb
from functools import lru_cache
@lru_cache(maxsize=None)
|
|
|
CROSSREFS
|
Binomial transform of A000670, also double of A000670. - Joe Keane (jgk(AT)jgk.org)
A diagonal of the triangular array in A241168.
|
|
|
KEYWORD
|
nonn,easy,eigen,nice,changed
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
