Search: a094816 -id:a094816
|
|
A130190
|
|
Denominators of z-sequence for the Sheffer matrix (triangle) A094816 (coefficients of Poisson-Charlier polynomials).
|
|
+20
5
|
|
|
1, 2, 6, 4, 15, 12, 42, 24, 90, 10, 33, 8, 910, 105, 90, 48, 255, 180, 3990, 420, 6930, 330, 345, 720, 13650, 273, 378, 28, 145, 20, 14322, 2464, 117810, 3570, 7, 24, 1919190, 1729, 2730, 840, 9471, 13860, 99330, 1540, 217350, 4830, 4935, 10080, 324870
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
The numerators are given in A130189.
See A130189 for the W. Lang link on z-sequences for Sheffer matrices.
The prime factors of each a(n) are such that n!/a(n) has the prime, p = n+1, as the denominator of its reduced fraction, and if n+1 is not prime then n!/a(n) is an integer, except at n = 3, which has denominator = 2. Also see alternate formula for a(n) below. - Richard R. Forberg, Dec 28 2014
As implied above, at n = p-1 the largest prime factor of a(n) is p. For a(m), where m is an integer within the set given by A089965, the two largest prime factors of a(m) are m+1 and (m+1)/2. Furthermore, it appears, when n+1 is not a prime no prime factor of a(n) is greater than k/2, where k is the next higher value of n where n+1 is prime. Two examples at this upper limit of k/2 are n = 104 and 105, where the highest prime factor of a(n) is 53; it is then at n = k = 106 where n+1 is prime. - Richard R. Forberg, Jan 01 2015
|
|
LINKS
|
|
|
FORMULA
|
a(n) = denominator(z(n)),n>=0, with the e.g.f. for z(n) given in A130189.
Alternate: a(n) = denominator((1/e)*Sum_{k>=0}*(Sum_{j=0..k} j^n/k!)). NOTE: Numerators are different from A130189, and given by A248716. - Richard R. Forberg, Dec 28 2014
This more generalized expression ((1/e)*Sum_{k>=0} (Sum_{j=0..k} (j+m)^n/k!)), gives the same denominators for any integer m. - Richard R. Forberg, Jan 14 2015
|
|
MAPLE
|
seq(denom(add(Stirling2(n, k)/(k+1), k=0..n)), n=0..20); # Peter Luschny, Apr 28 2009
|
|
MATHEMATICA
|
Denominator[Table[(1/Exp[1])* Sum[Sum[j^n/k!, {j, 0, k}], {k, 0, Infinity}], {n, 0, 100}]] (* Richard R. Forberg, Dec 28 2014 *)
Table[Denominator[Sum[StirlingS2[n, k]/(k + 1), {k, 0, n}]], {n, 0, 50}] (* G. C. Greubel, Jul 10 2018 *)
|
|
PROG
|
(PARI) a(n) = denominator(sum(k=0, n, stirling(n, k, 2)/(k+1))); \\ Michel Marcus, Jan 15 2015, after Maple
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A290311
|
|
Triangle T(n, k) read by rows: row n gives the coefficients of the row polynomials of the (n+1)-th diagonal sequence of the Sheffer triangle A094816 (special Poisson-Charlier).
|
|
+20
5
|
|
|
1, 1, 0, 1, 3, -1, 1, 17, -2, -1, 1, 80, 49, -27, 2, 1, 404, 733, -153, -49, 9, 1, 2359, 7860, 1622, -1606, 150, 9, 1, 16057, 80715, 58965, -17840, -3876, 1163, -50, 1, 125656, 858706, 1150722, 47365, -175756, 18239, 2359, -267, 1, 1112064, 9710898, 19571174, 7548463, -3175846, -491809, 194777, -9884, -413
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
The o.g.f. of the (n+1)-th diagonal sequence of the Sheffer triangle (e^x, -(log(1-x))) (the product of two Sheffer triangles A007318*A132393 = Pascal*|Stirling1|) is P(n, x)/(1 - x)^{2*n+1}, for n >= 0., with the numerator polynomials P(n, x) = Sum_{k=0..n} T(n, k)*x^k.
O.g.f.'s for diagonal sequences of Sheffer matrices (lower triangular) can be computed via Lagrange's theorem. For the special case of Jabotinsky matrices (1, f(x)) this has been done by P. Bala (see the link under A112007), and the method can be generalized to Sheffer (g(x), f(x)), as shown in the W. Lang link given below.
|
|
LINKS
|
|
|
FORMULA
|
T(n, k) = [x^n] P(n, x) with the numerator polynomials (in rising powers) of the o.g.f. of the (n+1)-th diagonal sequence of the triangle A094816. See the comment above.
|
|
EXAMPLE
|
The triangle T(n, k) begins:
n\k 0 1 2 3 4 5 6 7 8 9 ...
0: 1
1: 1 0
2: 1 3 -1
3: 1 17 -2 -1
4: 1 80 49 -27 2
5: 1 404 733 -153 -49 9
6: 1 2359 7860 1622 -1606 150 9
7: 1 16057 80715 58965 -17840 -3876 1163 -50
8: 1 125656 858706 1150722 47365 -175756 18239 2359 -267
9: 1 1112064 9710898 19571174 7548463 -3175846 -491809 194777 -9884 -413
...
n = 2: the o.g.f. of the third diagonal of triangle A094816, [1, 8, 29, 75, 160, ...] = A290312 is (1 + 3*x - x^2)/(1 - x)^5.
|
|
MATHEMATICA
|
rows = 10; nmax = 30(*terms to find every gf*);
T = Table[(-1)^(n - k) Sum[Binomial[-j - 1, -n - 1] StirlingS1[j, k], {j, 0, n}], {n, 0, nmax}, {k, 0, nmax}];
row[n_] := FindGeneratingFunction[Diagonal[T, -n], x] // Numerator // CoefficientList[-#, x]&; row[0] = {1}; row[1] = {1, 0};
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A130189
|
|
Numerators of z-sequence for the Sheffer matrix (triangle) A094816 (coefficients of Poisson-Charlier polynomials).
|
|
+20
4
|
|
|
1, -1, 5, -7, 68, -167, 2057, -4637, 75703, -39941, 676360, -902547, 602501827, -432761746, 2438757091, -8997865117, 346824403906, -1857709421899, 325976550837563, -282728710837871, 39928855264303811, -16874802689368067, 162083496666375118, -3212329557624761759
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
The denominators are given in A130190.
This z-sequence is useful for the recurrence for S(n,m=0):= A094816(n,0) (first column): S(n,0) = n*Sum_{j=0..n-1} z(j)*S(n-1,j), n >= 1, S(0,0)=1.
See the W. Lang link under A006232 with a summary on a- and z-sequences for Sheffer matrices.
|
|
LINKS
|
|
|
FORMULA
|
E.g.f. for rationals z(n)=a(n)/A130190(n) (in lowest terms): (1-exp(-h(x)))/h(x) with h(x):=1-exp(-x).
|
|
EXAMPLE
|
Rationals z(n): [1, -1/2, 5/6, -7/4, 68/15, -167/12, 2057/42, -4637/24, ...].
Recurrence from z(n) sequence for S(n,0)= A094816(n,0) for n=4: 1 = S(4,0) = 4*(1*1 - (1/2)*8 + (5/6)*6 - (7/4)*1) with the 3rd row [1,8,6,1] of A094816.
|
|
MAPLE
|
seq(numer((-1)^n*add(Stirling2(n, k)/(k+1), k=0..n)), n=0..20); # Peter Luschny, Apr 28 2009
|
|
MATHEMATICA
|
Table[(-1)^n*Numerator[Sum[StirlingS2[n, k]/(k + 1), {k, 0, n}]], {n, 0, 50}] (* G. C. Greubel, Jul 10 2018 *)
|
|
PROG
|
(PARI) a(n) = (-1)^n*numerator(sum(k=0, n, stirling(n, k, 2)/(k+1))); \\ Michel Marcus, Jan 15 2015
|
|
CROSSREFS
|
|
|
KEYWORD
|
sign,frac,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A290312
|
|
Third diagonal sequence of the Sheffer triangle A094816 (special Charlier).
|
|
+20
4
|
|
|
1, 8, 29, 75, 160, 301, 518, 834, 1275, 1870, 2651, 3653, 4914, 6475, 8380, 10676, 13413, 16644, 20425, 24815, 29876, 35673, 42274, 49750, 58175, 67626, 78183, 89929, 102950, 117335, 133176, 150568, 169609, 190400, 213045, 237651, 264328, 293189, 324350, 357930
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
|
|
LINKS
|
|
|
FORMULA
|
G.f.: (1 + 3*x - x^2)/(1 - x)^5.
E.g.f.: exp(x)*(1 + 7*x + 14*x^2/2! + 11*x^3/3! + 3*x^4/4!). This is computed from the o.g.f. with eqs. (23)-(25) of the Wolfdieter Lang 2017 link in A282629.
a(n) = (24 + 70*n + 69*n^2 + 26*n^3 + 3*n^4) / 24.
a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5) for n > 4.
(End)
|
|
PROG
|
(PARI) Vec((1 + 3*x - x^2)/(1 - x)^5 + O(x^60)) \\ Colin Barker, Jul 29 2017
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A290313
|
|
Fourth diagonal sequence of the Sheffer triangle A094816 (special Charlier).
|
|
+20
3
|
|
|
1, 24, 145, 545, 1575, 3836, 8274, 16290, 29865, 51700, 85371, 135499, 207935, 309960, 450500, 640356, 892449, 1222080, 1647205, 2188725, 2870791, 3721124, 4771350, 6057350, 7619625, 9503676, 11760399, 14446495, 17624895, 21365200, 25744136, 30846024, 36763265, 43596840, 51456825, 60462921, 70744999, 82443660, 95710810, 110710250
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
|
|
LINKS
|
|
|
FORMULA
|
O.g.f: (1 + 17*x - 2*x^2 - x^3)/(1 - x)^7.
E.g.f.: exp(x)*(1 + 23*x + 98*x^2/2! + 181*x^3/3! + 170*x^4/4! + 80*x^5/5! + 15*x^6/6!).
a(n) = (48 + 256*n + 422*n^2 + 303*n^3 + 105*n^4 + 17*n^5 + n^6) / 48.
a(n) = 7*a(n-1) - 21*a(n-2) + 35*a(n-3) - 35*a(n-4) + 21*a(n-5) - 7*a(n-6) + a(n-7) for n > 6.
(End)
|
|
PROG
|
(PARI) Vec((1 + 17*x - 2*x^2 - x^3) / (1 - x)^7 + O(x^50)) \\ Colin Barker, Jul 29 2017
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A290314
|
|
Fifth diagonal sequence of the Sheffer triangle A094816 (special Charlier).
|
|
+20
2
|
|
|
1, 89, 814, 4179, 15659, 47775, 125853, 296703, 641058, 1290718, 2451449, 4432792, 7686042, 12851762, 20818302, 32792898, 50387031, 75717831, 111527416, 161322161, 229533997, 321705945, 444704195, 606959145, 818737920, 1092450996, 1442995659, 1888139134, 2448944324, 3150241204, 4021147020, 5095638548
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
|
|
LINKS
|
|
|
FORMULA
|
O.g.f.: (1 + 80*x + 49*x^2 - 27*x^3 + 2*x^4)/(1-x)^9.
E.g.f: exp(x)*(1 + 88*x + 637*x^2/2! + 2003*x^3/3! + 3472*x^4/4! + 3574*x^5/5! + 2185*x^6/6! + 735*x^7/7! + 105*x^8/8!).
a(n) = (5760 + 67248*n + 158180*n^2 + 161700*n^3 + 87695*n^4 + 26952*n^5 + 4670*n^6 + 420*n^7 + 15*n^8) / 5760.
a(n) = 9*a(n-1) - 36*a(n-2) + 84*a(n-3) - 126*a(n-4) + 126*a(n-5) - 84*a(n-6) + 36*a(n-7) - 9*a(n-8) + a(n-9) for n>8.
(End)
|
|
PROG
|
(PARI) Vec((1 + 80*x + 49*x^2 - 27*x^3 + 2*x^4) / (1 - x)^9 + O(x^50)) \\ Colin Barker, Jul 29 2017
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A000522
|
|
Total number of ordered k-tuples (k=0..n) of distinct elements from an n-element set: a(n) = Sum_{k=0..n} n!/k!.
(Formerly M1497 N0589)
|
|
+10
285
|
|
|
1, 2, 5, 16, 65, 326, 1957, 13700, 109601, 986410, 9864101, 108505112, 1302061345, 16926797486, 236975164805, 3554627472076, 56874039553217, 966858672404690, 17403456103284421, 330665665962404000, 6613313319248080001, 138879579704209680022, 3055350753492612960485, 70273067330330098091156
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Total number of permutations of all subsets of an n-set.
Also the number of one-to-one sequences that can be formed from n distinct objects.
Old name "Total number of permutations of a set with n elements", or the same with the word "arrangements", both sound too much like A000142.
Related to number of operations of addition and multiplication to evaluate a determinant of order n by cofactor expansion - see A026243.
a(n) is also the number of paths (without loops) in the complete graph on n+2 vertices starting at one vertex v1 and ending at another v2. Example: when n=2 there are 5 paths in the complete graph with 4 vertices starting at the vertex 1 and ending at the vertex 2: (12),(132),(142),(1342),(1432) so a(2) = 5. - Avi Peretz (njk(AT)netvision.net.il), Feb 23 2001; comment corrected by Jonathan Coxhead, Mar 21 2003
Also row sums of Table A008279, which can be generated by taking the derivatives of x^k. For example, for y = 1*x^3, y' = 3x^2, y" = 6x, y'''= 6 so a(4) = 1 + 3 + 6 + 6 = 16. - Alford Arnold, Dec 15 1999
a(n) is the permanent of the n X n matrix with 2s on the diagonal and 1s elsewhere. - Yuval Dekel, Nov 01 2003
Stirling transform of A006252(n-1) = [1,1,1,2,4,14,38,...] is a(n-1) = [1,2,5,16,65,...]. - Michael Somos, Mar 04 2004
Number of {12,12*,21*}- and {12,12*,2*1}-avoiding signed permutations in the hyperoctahedral group.
a(n) = b such that Integral_{x=0..1} x^n*exp(-x) dx = a-b*exp(-1). - Sébastien Dumortier, Mar 05 2005
a(n) is the number of permutations on [n+1] whose left-to-right record lows all occur at the start. Example: a(2) counts all permutations on [3] except 231 (the last entry is a record low but its predecessor is not). - David Callan, Jul 20 2005
a(n) is the number of permutations on [n+1] that avoid the (scattered) pattern 1-2-3|. The vertical bar means the "3" must occur at the end of the permutation. For example, 21354 is not counted by a(4): 234 is an offending subpermutation. - David Callan, Nov 02 2005
Number of deco polyominoes of height n+1 having no reentrant corners along the lower contour (i.e., no vertical step that is followed by a horizontal step). In other words, a(n)=A121579(n+1,0). A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column. Example: a(1)=2 because the only deco polyominoes of height 2 are the vertical and horizontal dominoes, having no reentrant corners along their lower contours. - Emeric Deutsch, Aug 16 2006
Unreduced numerators of partial sums of the Taylor series for e. - Jonathan Sondow, Aug 18 2006
a(n) is the number of permutations on [n+1] (written in one-line notation) for which the subsequence beginning at 1 is increasing. Example: a(2)=5 counts 123, 213, 231, 312, 321. - David Callan, Oct 06 2006
a(n) is the number of permutations (written in one-line notation) on the set [n + k], k >= 1, for which the subsequence beginning at 1,2,...,k is increasing. Example: n = 2, k = 2. a(2) = 5 counts 1234, 3124, 3412, 4123, 4312. - Peter Bala, Jul 29 2014
a(n) and (1,-2,3,-4,5,-6,7,...) form a reciprocal pair under the list partition transform and associated operations described in A133314. - Tom Copeland, Nov 01 2007
Consider the subsets of the set {1,2,3,...,n} formed by the first n integers. E.g., for n = 3 we have {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}. Let the variable sbst denote a subset. For each subset sbst we determine its number of parts, that is nprts(sbst). The sum over all possible subsets is written as Sum_{sbst=subsets}. Then a(n) = Sum_{sbst=subsets} nprts(sbst)!. E.g., for n = 3 we have 1!+1!+1!+1!+2!+2!+2!+3!=16. - Thomas Wieder, Jun 17 2006
For positive n, equals 1/BarnesG(n+1) times the determinant of the n X n matrix whose (i,j)-coefficient is the (i+j)th Bell number. - John M. Campbell, Oct 03 2011
a(n) is the number of n X n binary matrices with i) at most one 1 in each row and column and ii) the subset of rows that contain a 1 must also be the columns that contain a 1. Cf. A002720 where restriction ii is removed. - Geoffrey Critzer, Dec 20 2011
Number of restricted growth strings (RGS) [d(1),d(2),...,d(n)] such that d(k) <= k and d(k) <= 1 + (number of nonzero digits in prefix). The positions of nonzero digits determine the subset, and their values (decreased by 1) are the (left) inversion table (a rising factorial number) for the permutation, see example. - Joerg Arndt, Dec 09 2012
Number of a restricted growth strings (RGS) [d(0), d(1), d(2), ..., d(n)] where d(k) >= 0 and d(k) <= 1 + chg([d(0), d(1), d(2), ..., d(k-1)]) and chg(.) gives the number of changes of its argument. Replacing the function chg(.) by a function asc(.) that counts the ascents in the prefix gives A022493 (ascent sequences). - Joerg Arndt, May 10 2013
The sequence t(n) = number of i <= n such that floor( e i! ) is a square is mentioned in the abstract of Luca & Shparlinski. The values are t(n)=0 for 0 <= n <= 2 and t(n) = 1 for at least 3 <= n <= 300. - R. J. Mathar, Jan 16 2014
a(n) is the number of ways at most n people can queue up at a (slow) ticket counter when one or more of the people may choose not to queue up. Note that there are C(n,k) sets of k people who quene up and k! ways to queue up. Since k can run from 0 to n, a(n) = Sum_{k=0..n} n!/(n-k)! = Sum_{k=0..n} n!/k!. For example, if n=3 and the people are A(dam), B(eth), and C(arl), a(3)=16 since there are 16 possible lineups: ABC, ACB, BAC, BCA, CAB, CBA, AB, BA, AC, CA, BC, CB, A, B, C, and empty queue. - Dennis P. Walsh, Oct 02 2015
As the row sums of A008279, Motzkin uses the abbreviated notation $n_<^\Sigma$ for a(n).
The piecewise polynomial function f defined by f(x) = a(n)*x^n/n! on each interval [ 1-1/a(n), 1-1/a(n+1) ) is continuous on [0,1) and lim_{x->1} f(x) = e. - Luc Rousseau, Oct 15 2019
a(n) is composite for 3 <= n <= 2015, but a(2016) is prime (or at least a strong pseudoprime): see Johansson link. - Robert Israel, Jul 27 2020
In general, sequences of the form a(0)=a, a(n) = n*a(n-1) + k, n>0, will have a closed form of n!*a + floor(n!*(e-1))*k. - Gary Detlefs, Oct 26 2020
a(2*n) is odd and a(2*n+1) is even. More generally, a(n+k) == a(n) (mod k) for all n and k. It follows that for each positive integer k, the sequence obtained by reducing a(n) modulo k is periodic, with the exact period dividing k. Various divisibility properties of the sequence follow from this; for example, a(5*n+2) == a(5*n+4) == 0 (mod 5), a(25*n+7) == a(25*n+19) == 0 (mod 25) and a(13*n+4) == a(13*n+10)== a(13*n+12) == 0 (mod 13). (End)
Number of possible ranking options on a typical ranked choice voting ballot with n candidates (allowing undervotes). - P. Christopher Staecker, May 05 2024
|
|
REFERENCES
|
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 75, Problem 9.
J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 65, p. 23, Ellipses, Paris 2008.
J. M. Gandhi, On logarithmic numbers, Math. Student, 31 (1963), 73-83.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 16.
D. Singh, The numbers L(m,n) and their relations with prepared Bernoulli and Eulerian numbers, Math. Student, 20 (1952), 66-70.
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).
|
|
LINKS
|
F. Ardila, F. Rincón, and L. Williams, Positroids, non-crossing partitions, and positively oriented matroids, in FPSAC 2014, Chicago, USA; Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, 2014, 555-666.
Olivier Bodini, Antoine Genitrini, and Mehdi Naima, Ranked Schröder Trees, arXiv:1808.08376 [cs.DS], 2018.
Xing Gao and William F. Keigher, Interlacing of Hurwitz series, Communications in Algebra, 45:5 (2017), 2163-2185, DOI: 10.1080/00927872.2016.1226885. See Ex. 2.16.
Lorenz Halbeisen and Norbert Hungerbuehler, Number theoretic aspects of a combinatorial function, Notes on Number Theory and Discrete Mathematics 5 (1999) 138-150. (ps, pdf)
J. Sondow and K. Schalm, Which partial sums of the Taylor series for e are convergents to e? (and a link to the primes 2, 5, 13, 37, 463), II, arXiv:0709.0671 [math.NT], 2006-2009; Gems in Experimental Mathematics (T. Amdeberhan, L. A. Medina, and V. H. Moll, eds.), Contemporary Mathematics, vol. 517, Amer. Math. Soc., Providence, RI, 2010.
|
|
FORMULA
|
a(n) = n*a(n-1) + 1, a(0) = 1.
a(n) = n! * Sum_{k=0..n} 1/k! = n! * (e - Sum_{k>=n+1} 1/k!). - Michael Somos, Mar 26 1999
a(0) = 1; for n > 0, a(n) = floor(e*n!).
E.g.f.: exp(x)/(1-x).
Integral representation as n-th moment of a nonnegative function on a positive half-axis: a(n) = e*Integral_{x=0..infinity} (x^n*e^(-x)*Heaviside(x-1). - Karol A. Penson, Oct 01 2001
Formula, in Mathematica notation: Special values of Laguerre polynomials, a(n)=(-1)^n*n!*LaguerreL[n, -1-n, 1], n=1, 2, ... . This relation cannot be checked by Maple, as it appears that Maple does not incorporate Laguerre polynomials with second index equal to negative integers. It does check with Mathematica. - Karol A. Penson and Pawel Blasiak ( blasiak(AT)lptl.jussieu.fr), Feb 13 2004
G.f.: Sum_{k>=0} k!*x^k/(1-x)^(k+1). a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n, k)*k^(n-k)*(k+1)^k. - Vladeta Jovovic, Aug 18 2002
a(n) = e*Gamma(n+1,1) where Gamma(z,t) = Integral_{x>=t} e^(-x)*x^(z-1) dx is incomplete gamma function. - Michael Somos, Jul 01 2004
a(n) = 1 + n + n*(n-1) + n*(n-1)*(n-2) + ... + n!. - Jonathan Sondow, Aug 18 2006
a(n) = Sum_{k=0..n} binomial(n,k) * k!; interpretation: for all k-subsets (sum), choose a subset (binomial(n,k)), and permutation of subset (k!). - Joerg Arndt, Dec 09 2012
a(n) = Sum_{k=0..n} A094816(n, k), n>=0 (row sums of Poisson-Charlier coefficient matrix). - N. J. A. Sloane, Nov 10 2007
Act on 1/(1-x) with 1/(1-xDx) = Sum_{j>=0} (xDx)^j = Sum_{j>=0} x^j*D^j*x^j = Sum_{j>=0} j!*x^j*L(j,-:xD:,0) where Lag(n,x,0) are the Laguerre polynomials of order 0, D the derivative w.r.t. x and (:xD:)^j = x^j*D^j. Truncating the operator series at the j = n term gives an o.g.f. for a(0) through a(n) consistent with Jovovic's.
These results and those of Penson and Blasiak, Arnold, Bottomley and Deleham are related by the operator A094587 (the reverse of A008279), which is the umbral equivalent of n!*Lag[n,(.)!*Lag[.,x,-1],0] = (1-D)^(-1) x^n = (-1)^n * n! Lag(n,x,-1-n) = Sum_{j=0..n} binomial(n,j)*j!*x^(n-j) = Sum_{j=0..n} (n!/j!)*x^j. Umbral substitution of b(.) for x and then letting b(n)=1 for all n connects the results. See A132013 (the inverse of A094587) for a connection between these operations and 1/(1-xDx).
(End)
a(n) = n!*e - 1/(n + 1/(n+1 + 2/(n+2 + 3/(n+3 + ...)))).
Asymptotic result (Ramanujan): n!*e - a(n) ~ 1/n - 1/n^3 + 1/n^4 + 2/n^5 - 9/n^6 + ..., where the sequence [1,0,-1,1,2,-9,...] = [(-1)^k*A000587(k)], for k>=1.
a(n) is a difference divisibility sequence, that is, the difference a(n) - a(m) is divisible by n - m for all n and m (provided n is not equal to m). For fixed k, define the derived sequence a_k(n) = (a(n+k)-a(k))/n, n = 1,2,3,... . Then a_k(n) is also a difference divisibility sequence.
For example, the derived sequence a_0(n) is just a(n-1). The set of integer sequences satisfying the difference divisibility property forms a ring with term-wise operations of addition and multiplication.
Recurrence relations: a(0) = 1, a(n) = (n-1)*(a(n-1) + a(n-2)) + 2, for n >= 1. a(0) = 1, a(1) = 2, D-finite with recurrence: a(n) = (n+1)*a(n-1) - (n-1)*a(n-2) for n >= 2. The sequence b(n) := n! satisfies the latter recurrence with the initial conditions b(0) = 1, b(1) = 1. This leads to the finite continued fraction expansion a(n)/n! = 1/(1-1/(2-1/(3-2/(4-...-(n-1)/(n+1))))), n >= 2.
Limit_{n->infinity} a(n)/n! = e = 1/(1-1/(2-1/(3-2/(4-...-n/((n+2)-...))))). This is the particular case m = 0 of the general result m!/e - d_m = (-1)^(m+1) *(1/(m+2 -1/(m+3 -2/(m+4 -3/(m+5 -...))))), where d_m denotes the m-th derangement number A000166(m).
For sequences satisfying the more general recurrence a(n) = (n+1+r)*a(n-1) - (n-1)*a(n-2), which yield series acceleration formulas for e/r! that involve the Poisson-Charlier polynomials c_r(-n;-1), refer to A001339 (r=1), A082030 (r=2), A095000 (r=3) and A095177 (r=4).
For the corresponding results for the constants log(2), zeta(2) and zeta(3) refer to A142992, A108625 and A143007 respectively.
(End)
G.f. satisfies: A(x) = 1/(1-x)^2 + x^2*A'(x)/(1-x). - Paul D. Hanna, Sep 03 2008
G.f.: 1/(1-2*x-x^2/(1-4*x-4*x^2/(1-6*x-9*x^2/(1-8*x-16*x^2/(1-10*x-25*x^2/(1-... (continued fraction);
G.f.: 1/(1-x-x/(1-x/(1-x-2*x/(1-2*x/(1-x-3*x/(1-3*x/(1-x-4*x/(1-4*x/(1-x-5*x/(1-5*x/(1-... (continued fraction).
(End)
O.g.f.: Sum_{n>=0} (n+2)^n*x^n/(1 + (n+1)*x)^(n+1). - Paul D. Hanna, Sep 19 2011
G.f. hypergeom([1,k],[],x/(1-x))/(1-x), for k=1,2,...,9 is the generating function for A000522, A001339, A082030, A095000, A095177, A096307, A096341, A095722, and A095740. - Mark van Hoeij, Nov 07 2011
G.f.: 1/U(0) where U(k) = 1 - x - x*(k+1)/(1 - x*(k+1)/U(k+1)); (continued fraction). - Sergei N. Gladkovskii, Oct 14 2012
E.g.f.: 1/U(0) where U(k) = 1 - x/(1 - 1/(1 + (k+1)/U(k+1))); (continued fraction). - Sergei N. Gladkovskii, Nov 16 2012
G.f.: 1/(1-x)/Q(0), where Q(k) = 1 - x/(1-x)*(k+1)/(1 - x/(1-x)*(k+1)/Q(k+1)); (continued fraction). - Sergei N. Gladkovskii, May 19 2013
G.f.: 2/(1-x)/G(0), where G(k) = 1 + 1/(1 - x*(2*k+2)/(x*(2*k+3) - 1 + x*(2*k+2)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 31 2013
G.f.: (B(x)+ 1)/(2-2*x) = Q(0)/(2-2*x), where B(x) be g.f. A006183, Q(k) = 1 + 1/(1 - x*(k+1)/(x*(k+1) + (1-x)/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 08 2013
G.f.: 1/Q(0), where Q(k) = 1 - 2*x*(k+1) - x^2*(k+1)^2/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Sep 30 2013
E.g.f.: e^x/(1-x) = (1 - 12*x/(Q(0) + 6*x - 3*x^2))/(1-x), where Q(k) = 2*(4*k+1)*(32*k^2 + 16*k + x^2 - 6) - x^4*(4*k-1)*(4*k+7)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 18 2013
G.f.: conjecture: T(0)/(1-2*x), where T(k) = 1 - x^2*(k+1)^2/(x^2*(k+1)^2 - (1 - 2*x*(k+1))*(1 - 2*x*(k+2))/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 18 2013
0 = a(n)*(+a(n+1) - 3*a(n+2) + a(n+3)) + a(n+1)*(+a(n+1) - a(n+3)) + a(n+2)*(+a(n+2)) for all n>=0. - Michael Somos, Jul 04 2014
a(n) = F(n), where the function F(x) := Integral_{0..infinity} e^(-u)*(1 + u)^x du smoothly interpolates this sequence to all real values of x. Note that F(-1) = G and for n = 2,3,... we have F(-n) = (-1)^n/(n-1)! *( A058006(n-2) - G ), where G = 0.5963473623... denotes Gompertz's constant - see A073003.
a(n) = n!*e - e*( Sum_{k >= 0} (-1)^k/((n + k + 1)*k!) ).
(End)
a(n) = (e/(2*Pi))*Integral_{x=-oo..oo} (n+1+i*x)!/(1+i*x) dx. - David Ulgenes, Apr 18 2023
Sum_{i=0..n} (-1)^(n-i) * binomial(n, i) * a(i) = n!. - Werner Schulte, Apr 03 2024
|
|
EXAMPLE
|
G.f. = 1 + 2*x + 5*x^2 + 16*x^3 + 65*x^4 + 326*x^5 + 1957*x^6 + 13700*x^7 + ...
With two objects we can form 5 sequences: (), (a), (b), (a,b), (b,a), so a(2) = 5.
The 16 arrangements of the 3-set and their RGS (dots denote zeros) are
[ #] RGS perm. of subset
[ 1] [ . . . ] [ ]
[ 2] [ . . 1 ] [ 3 ]
[ 3] [ . 1 . ] [ 2 ]
[ 4] [ . 1 1 ] [ 2 3 ]
[ 5] [ . 1 2 ] [ 3 2 ]
[ 6] [ 1 . . ] [ 1 ]
[ 7] [ 1 . 1 ] [ 1 3 ]
[ 8] [ 1 . 2 ] [ 3 1 ]
[ 9] [ 1 1 . ] [ 1 2 ]
[10] [ 1 1 1 ] [ 1 2 3 ]
[11] [ 1 1 2 ] [ 1 3 2 ]
[12] [ 1 1 3 ] [ 2 3 1 ]
[13] [ 1 2 . ] [ 2 1 ]
[14] [ 1 2 1 ] [ 2 1 3 ]
[15] [ 1 2 2 ] [ 3 1 2 ]
[16] [ 1 2 3 ] [ 3 2 1 ]
(End)
|
|
MAPLE
|
a(n):= exp(1)*int(x^n*exp(-x)*Heaviside(x-1), x=0..infinity); # Karol A. Penson, Oct 01 2001
G(x):=exp(x)/(1-x): f[0]:=G(x): for n from 1 to 26 do f[n]:=diff(f[n-1], x) od: x:=0: seq(f[n], n=0..20);
G:=exp(z)/(1-z): Gser:=series(G, z=0, 21):
for n from 0 to 20 do a(n):=n!*coeff(Gser, z, n): end do
k := 1; series(hypergeom([1, k], [], x/(1-x))/(1-x), x=0, 20); # Mark van Hoeij, Nov 07 2011
# one more Maple program:
a:= proc(n) option remember;
`if`(n<0, 0, 1+n*a(n-1))
end:
seq(simplify(KummerU(-n, -n, 1)), n = 0..23); # Peter Luschny, May 10 2022
|
|
MATHEMATICA
|
Table[FunctionExpand[Gamma[n + 1, 1]*E], {n, 0, 24}]
nn = 20; Accumulate[Table[1/k!, {k, 0, nn}]] Range[0, nn]! (* Jan Mangaldan, Apr 21 2013 *)
FoldList[#1*#2 + #2 &, 0, Range@ 23] + 1 (* or *)
RecurrenceTable[{a[n + 1] == (n + 1) a[n] + 1, a[0] == 1}, a, {n, 0, 12}] (* Emanuele Munarini, Apr 27 2017 *)
nxt[{n_, a_}]:={n+1, a(n+1)+1}; NestList[nxt, {0, 1}, 30][[All, 2]] (* Harvey P. Dale, Jan 29 2023 *)
|
|
PROG
|
(PARI) {a(n) = local(A); if( n<0, 0, A = vector(n+1); A[1]=1; for(k=1, n, A[k+1] = k*A[k] + 1); A[n+1])}; /* Michael Somos, Jul 01 2004 */
(PARI) {a(n) = if( n<0, 0, n! * polcoeff( exp( x +x * O(x^n)) / (1 - x), n))}; /* Michael Somos, Mar 06 2004 */
(PARI) a(n)=local(A=1+x+x*O(x^n)); for(i=1, n, A=1/(1-x)^2+x^2*deriv(A)/(1-x)); polcoeff(A, n) \\ Paul D. Hanna, Sep 03 2008
(PARI) {a(n)=local(X=x+x*O(x^n)); polcoeff(sum(m=0, n, (m+2)^m*x^m/(1+(m+1)*X)^(m+1)), n)} /* Paul D. Hanna */
(PARI) a(n)=sum(k=0, n, binomial(n, k)*k!); \\ Joerg Arndt, Dec 14 2014
(Haskell)
import Data.List (subsequences, permutations)
a000522 = length . choices . enumFromTo 1 where
choices = concat . map permutations . subsequences
(Sage)
@CachedFunction
def b(n, i, t):
if n <= 1:
return 1
return sum(b(n - 1, j, t + (j == i)) for j in range(t + 2))
def a(n):
return b(n, 0, 0)
v000522 = [a(n) for n in range(33)]
print(v000522)
(Magma) [1] cat [n eq 1 select (n+1) else n*Self(n-1)+1: n in [1..25]]; // Vincenzo Librandi, Feb 15 2015
(Maxima) a(n) := if n=0 then 1 else n*a(n-1)+1; makelist(a(n), n, 0, 12); /* Emanuele Munarini, Apr 27 2017 */
|
|
CROSSREFS
|
Cf. A000166, A002627, A006231, A064383, A064384, A008290, A010844, A010845, A014508, A038159, A054091, A058006, A072453, A072456, A073591, A082030, A095000, A095177, A108625, A121579, A124779, A142992, A143007, A158359, A158821, A195254, A222637-A222639, A038155, A000217.
See also A370973, Nearest integer to e*n!.
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A027641
|
|
Numerator of Bernoulli number B_n.
|
|
+10
240
|
|
|
1, -1, 1, 0, -1, 0, 1, 0, -1, 0, 5, 0, -691, 0, 7, 0, -3617, 0, 43867, 0, -174611, 0, 854513, 0, -236364091, 0, 8553103, 0, -23749461029, 0, 8615841276005, 0, -7709321041217, 0, 2577687858367, 0, -26315271553053477373, 0, 2929993913841559, 0, -261082718496449122051
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,11
|
|
COMMENTS
|
a(n)/A027642(n) (Bernoulli numbers) provide the a-sequence for the Sheffer matrix A094816 (coefficients of orthogonal Poisson-Charlier polynomials). See the W. Lang link under A006232 for a- and z-sequences for Sheffer matrices. The corresponding z-sequence is given by the rationals A130189(n)/A130190(n).
Harvey (2008) describes a new algorithm for computing Bernoulli numbers. His method is to compute B(k) modulo p for many small primes p and then reconstruct B(k) via the Chinese Remainder Theorem. The time complexity is O(k^2 log(k)^(2+eps)). The algorithm is especially well-suited to parallelization. - Jonathan Vos Post, Jul 09 2008
Regard the Bernoulli numbers as forming a vector = B_n, and the variant starting (1, 1/2, 1/6, 0, -1/30, ...), (i.e., the first 1/2 has sign +) as forming a vector Bv_n. The relationship between the Pascal triangle matrix, B_n, and Bv_n is as follows: The binomial transform of B_n = Bv_n. B_n is unchanged when multiplied by the Pascal matrix with rows signed (+-+-, ...), i.e., (1; -1,-1; 1,2,1; ...). Bv_n is unchanged when multiplied by the Pascal matrix with columns signed (+-+-, ...), i.e., (1; 1,-1; 1,-2,1; 1,-3,3,-1; ...). - Gary W. Adamson, Jun 29 2012
The sequence of the Bernoulli numbers B_n = a(n)/A027642(n) is the inverse binomial transform of the sequence {A164555(n)/A027642(n)}, illustrated by the fact that they appear as top row and left column in A190339. - Paul Curtz, May 13 2016
Named by de Moivre (1773; "the numbers of Mr. James Bernoulli") after the Swiss mathematician Jacob Bernoulli (1655-1705). - Amiram Eldar, Oct 02 2023
|
|
REFERENCES
|
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 810.
Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 49.
Harold T. Davis, Tables of the Mathematical Functions. Vols. 1 and 2, 2nd ed., 1963, Vol. 3 (with V. J. Fisher), 1962; Principia Press of Trinity Univ., San Antonio, TX, Vol. 2, p. 230.
Harold M. Edwards, Riemann's Zeta Function, Academic Press, NY, 1974; see p. 11.
Steven R. Finch, Mathematical Constants, Cambridge, 2003, Section 1.6.1.
Herman H. Goldstine, A History of Numerical Analysis, Springer-Verlag, 1977; Section 2.6.
L. M. Milne-Thompson, Calculus of Finite Differences, 1951, p. 137.
Hans Rademacher, Topics in Analytic Number Theory, Springer, 1973, Chap. 1.
|
|
LINKS
|
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
|
|
FORMULA
|
E.g.f: x/(exp(x) - 1); take numerators.
Recurrence: B^n = (1+B)^n, n >= 2 (interpreting B^j as B_j).
B_{2n}/(2n)! = 2*(-1)^(n-1)*(2*Pi)^(-2n) Sum_{k>=1} 1/k^(2n) (gives asymptotics) - Rademacher, p. 16, Eq. (9.1). In particular, B_{2*n} ~ (-1)^(n-1)*2*(2*n)!/(2*Pi)^(2*n).
Sum_{i=1..n-1} i^k = ((n+B)^(k+1)-B^(k+1))/(k+1) (interpreting B^j as B_j).
B_{n-1} = - Sum_{r=1..n} (-1)^r binomial(n, r) r^(-1) Sum_{k=1..r} k^(n-1). More concisely, B_n = 1 - (1-C)^(n+1), where C^r is replaced by the arithmetic mean of the first r n-th powers of natural numbers in the expansion of the right-hand side. [Bergmann]
Sum_{i>=1} 1/i^(2k) = zeta(2k) = (2*Pi)^(2k)*|B_{2k}|/(2*(2k)!).
B_{2n} = (-1)^(m-1)/2^(2m+1) * Integral{-inf..inf, [d^(m-1)/dx^(m-1) sech(x)^2 ]^2 dx} (see Grosset/Veselov).
Let B(s,z) = -2^(1-s)(i/Pi)^s s! PolyLog(s,exp(-2*i*Pi/z)). Then B(2n,1) = B_{2n} for n >= 1. Similarly the numbers B(2n+1,1), which might be called Co-Bernoulli numbers, can be considered, and it is remarkable that Leonhard Euler in 1755 already calculated B(3,1) and B(5,1) (Opera Omnia, Ser. 1, Vol. 10, p. 351). (Cf. the Luschny reference for a discussion.) - Peter Luschny, May 02 2009
The B_n sequence is the left column of the inverse of triangle A074909, the "beheaded" Pascal's triangle. - Gary W. Adamson, Mar 05 2012
E.g.f. E(x)= 2 - x/(tan(x) + sec(x) - 1)= Sum_{n>=0} a(n)*x^n/n!, a(n)=|B(n)|, where B(n) is Bernoulli number B_n.
E(x)= 2 + x - B(0), where B(k)= 4*k+1 + x/(2 + x/(4*k+3 - x/(2 - x/B(k+1)))); (continued fraction, 4-step). (End)
E.g.f.: x/(exp(x)-1)= U(0); U(k)= 2*k+1 - x(2*k+1)/(x + (2*k+2)/(1 + x/U(k+1))); (continued fraction). - Sergei N. Gladkovskii, Dec 05 2012
E.g.f.: 2*(x-1)/(x*Q(0)-2) where Q(k) = 1 + 2*x*(k+1)/((2*k+1)*(2*k+3) - x*(2*k+1)*(2*k+3)^2/(x*(2*k+3) + 4*(k+1)*(k+2)/Q(k+1))); (recursively defined continued fraction). - Sergei N. Gladkovskii, Feb 26 2013
a(n) = numerator(B(n)), B(n) = (-1)^n*Sum_{k=0..n} Stirling1(n,k) * Stirling2(n+k,n) / binomial(n+k,k). - Vladimir Kruchinin, Mar 16 2013
E.g.f.: x/(exp(x)-1) = E(0) where E(k) = 2*k+1 - x/(2 + x/E(k+1)); (continued fraction). - Sergei N. Gladkovskii, Mar 16 2013
G.f. for Bernoulli(n) = a(n)/A027642(n): psi_1(1/x)/x - x, where psi_n(z) is the polygamma function, psi_n(z) = (d/dz)^(n+1) log(Gamma(z)). - Vladimir Reshetnikov, Apr 24 2013
E.g.f.: 2*E(0) - 2*x, where E(k)= x + (k+1)/(1 + 1/(1 - x/E(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 10 2013
B_n = Sum_{m=0..n} (-1)^m *A131689(n, m)/(m + 1), n >= 0. See one of the Maple programs. - Wolfdieter Lang, May 05 2017
a(n) = numerator(-2*cos(Pi*n/2)*Gamma(n+1)*zeta(n)/(2*Pi)^n), for n=0 and n>1.
a(n) = numerator(-n*zeta(1-n)), for n=0 and n>1. (End)
|
|
EXAMPLE
|
B_n sequence begins 1, -1/2, 1/6, 0, -1/30, 0, 1/42, 0, -1/30, 0, 5/66, 0, -691/2730, 0, 7/6, 0, -3617/510, ...
|
|
MAPLE
|
B := n -> add((-1)^m*m!*Stirling2(n, m)/(m+1), m=0..n);
B := n -> bernoulli(n);
|
|
MATHEMATICA
|
Numerator[ Range[0, 40]! CoefficientList[ Series[x/(E^x - 1), {x, 0, 40}], x]]
Numerator[CoefficientList[Series[PolyGamma[1, 1/x]/x - x, {x, 0, 40}, Assumptions -> x > 0], x]] (* Vladimir Reshetnikov, Apr 24 2013 *)
|
|
PROG
|
(PARI) a(n)=numerator(bernfrac(n))
(Maxima) B(n):=(-1)^((n))*sum((stirling1(n, k)*stirling2(n+k, n))/binomial(n+k, k), k, 0, n);
(SageMath)
[bernoulli(n).numerator() for n in range(41)] # Peter Luschny, Feb 19 2016
(SageMath) # Alternatively:
f, R, C = 1, [1], [1]+[0]*(len-1)
for n in (1..len-1):
f *= n
for k in range(n, 0, -1):
C[k] = C[k-1] / (k+1)
C[0] = -sum(C[k] for k in (1..n))
R.append((C[0]*f).numerator())
return R
(Python)
from sympy import bernoulli
from fractions import Fraction
[bernoulli(i).as_numer_denom()[0] for i in range(51)] # Indranil Ghosh, Mar 18 2017
(Python)
from sympy import bernoulli
def A027641(n): return bernoulli(n).p
|
|
CROSSREFS
|
This is the main entry for the Bernoulli numbers and has all the references, links and formulas. Sequences A027642 (the denominators of B_n) and A000367/A002445 = B_{2n} are also important!
|
|
KEYWORD
|
sign,frac,nice,core
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A068985
|
|
Decimal expansion of 1/e.
|
|
+10
99
|
|
|
3, 6, 7, 8, 7, 9, 4, 4, 1, 1, 7, 1, 4, 4, 2, 3, 2, 1, 5, 9, 5, 5, 2, 3, 7, 7, 0, 1, 6, 1, 4, 6, 0, 8, 6, 7, 4, 4, 5, 8, 1, 1, 1, 3, 1, 0, 3, 1, 7, 6, 7, 8, 3, 4, 5, 0, 7, 8, 3, 6, 8, 0, 1, 6, 9, 7, 4, 6, 1, 4, 9, 5, 7, 4, 4, 8, 9, 9, 8, 0, 3, 3, 5, 7, 1, 4, 7, 2, 7, 4, 3, 4, 5, 9, 1, 9, 6, 4, 3, 7, 4, 6, 6, 2, 7
(list;
constant;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,1
|
|
COMMENTS
|
From the "derangements" problem: this is the probability that if a large number of people are given their hats at random, nobody gets their own hat.
Also, this is lim_{n->inf} P(n), where P(n) is the probability that a random rooted forest on [n] is a tree. See linked file. - Washington Bomfim, Nov 01 2010
Also, -1/e is the global minimum of x*log(x) at x = 1/e and the global minimum of x*e^x at x = -1. - Rick L. Shepherd, Jan 11 2014
Also, the asymptotic probability of success in the secretary problem (also known as the sultan's dowry problem). - Andrey Zabolotskiy, Sep 14 2019
The asymptotic density of numbers with an odd number of trailing zeros in their factorial base representation (A232745). - Amiram Eldar, Feb 26 2021
For large range size s where numbers are chosen randomly r times, the probability when r = s that a number is randomly chosen exactly 1 time. Also the chance that a number was not chosen at all. The general case for the probability of being chosen n times is (r/s)^n / (n! * e^(r/s)). - Mark Andreas, Oct 25 2022
|
|
REFERENCES
|
Anders Hald, A History of Probability and Statistics and Their Applications Before 1750, Wiley, NY, 1990 (Chapter 19).
John Harris, Jeffry L. Hirst, and Michael Mossinghoff, Combinatorics and Graph Theory, Springer Science & Business Media, 2009, p. 161.
L. B. W. Jolley, Summation of Series, Dover, 1961, eq. (103) on page 20.
Traian Lalescu, Problem 579, Gazeta Matematică, Vol. 6 (1900-1901), p. 148.
John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.
Manfred R. Schroeder, Number Theory in Science and Communication, Springer Science & Business Media, 2008, ch. 9.5 Derangements.
Walter D. Wallis and John C. George, Introduction to Combinatorics, CRC Press, 2nd ed. 2016, theorem 5.2 (The Derangement Series).
David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987, p. 27.
|
|
LINKS
|
James Grime and Brady Haran, Derangements, Numberphile video, 2017.
Eric Weisstein's World of Mathematics, e.
|
|
FORMULA
|
Equals 2*(1/3! + 2/5! + 3/7! + ...). [Jolley]
Equals 1 - Sum_{i >= 1} (-1)^(i - 1)/i!. [Michon]
Equals j_1(i)/i = cos(i) + i*sin(i), where j_1(z) is the spherical Bessel function of the first kind and i = sqrt(-1). - Stanislav Sykora, Jan 11 2017
The series representation 1/e = Sum_{k >= 0} (-1)^k/k! is the case n = 0 of the following series acceleration formulas:
1/e = n!*Sum_{k >= 0} (-1)^k/(k!*R(n,k)*R(n,k+1)), n = 0,1,2,..., where R(n,x) = Sum_{k = 0..n} (-1)^k*binomial(n,k)*k!*binomial(-x,k) are the row polynomials of A094816. (End)
1/e = 1 - Sum_{n >= 0} n!/(A(n)*A(n+1)), where A(n) = A000522(n). - Peter Bala, Nov 13 2019
Equals Integral_{x=0..1} x * sinh(x) dx. - Amiram Eldar, Aug 14 2020
Equals lim_{n->oo} (n+1)!^(1/(n+1)) - n!^(1/n) (Lalescu, 1900-1901). - Amiram Eldar, Mar 29 2022
|
|
EXAMPLE
|
1/e = 0.3678794411714423215955237701614608674458111310317678... = A135005/5.
|
|
MATHEMATICA
|
|
|
PROG
|
(PARI)
default(realprecision, 110);
|
|
CROSSREFS
|
Cf. asymptotic probabilities of success for other "nothing but the best" variants of the secretary problem: A325905, A242674, A246665.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
|
|
1, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10, -11, -12, -13, -14, -15, -16, -17, -18, -19, -20, -21, -22, -23, -24, -25, -26, -27, -28, -29, -30, -31, -32, -33, -34, -35, -36, -37, -38, -39, -40, -41, -42, -43, -44, -45, -46, -47, -48, -49, -50, -51, -52, -53, -54, -55, -56
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
a(n) is the weighted sum over all derangements (permutations with no fixed points) of n elements where each permutation with an odd number of cycles has weight +1 and each with an even number of cycles has weight -1. [Michael Somos, Jan 19 2011]
|
|
LINKS
|
|
|
FORMULA
|
E.g.f.: (1-x)*exp(x).
a(n) = Sum_{k=0..n} A094816(n,k)*(-1)^k (alternating row sums of Poisson-Charlier coefficient matrix).
|
|
EXAMPLE
|
a(4) = -3 because there are 6 derangements with one 4-cycle with weight -1 and 3 derangements with two 2-cycles with weight +1. - Michael Somos, Jan 19 2011
|
|
MAPLE
|
|
|
MATHEMATICA
|
CoefficientList[Series[(1 - 2 x)/(1 - x)^2, {x, 0, 60}], x] Range[0, 60]!
CoefficientList[Series[Exp[x] (1 - x), {x, 0, 60}], x]
Flatten[NestList[(#/.x_/; x>1->Sequence[x, 2x])-1&, {1}, 60]]
|
|
PROG
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
sign,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
Search completed in 0.032 seconds
|