|
| |
|
|
A001515
|
|
Bessel polynomial y_n(x) evaluated at x=1.
(Formerly M1803 N0713)
|
|
59
|
|
|
|
1, 2, 7, 37, 266, 2431, 27007, 353522, 5329837, 90960751, 1733584106, 36496226977, 841146804577, 21065166341402, 569600638022431, 16539483668991901, 513293594376771362, 16955228098102446847, 593946277027962411007, 21992967478132711654106, 858319677924203716921141
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
For some applications it is better to start this sequence with an extra 1 at the beginning: 1, 1, 2, 37, 266, 2431, 27007, 353522, 5329837, ... (again with offset 0). This sequence now has its own entry - see A144301.
Number of partitions of {1,...,k}, n <= k <= 2n, into n blocks with no more than 2 elements per block. Restated, number of ways to use the elements of {1,...,k}, n <= k <= 2n, once each to form a collection of n sets, each having 1 or 2 elements. - Bob Proctor, Apr 18 2005, Jun 26 2006. E.g., for n=2 we get: (k=2): {1,2}; (k=3): {1,23}, {2,13}, {3,12}; (k=4): {12,34}, {13,24}, {14,23}, for a total of a(2) = 7 partitions.
Equivalently, number of sequences of n unlabeled items such that each item occurs just once or twice (cf. A105749). - David Applegate, Dec 08 2008
Numerator of (n+1)-th convergent to 1+tanh(1). - Benoit Cloitre, Dec 20 2002
f0:=proc(n) local k; add((n+k)!/((n-k)!*k!*2^k),k=0..n); end; [seq(f0(n),n=0..10)];
# that is this sequence
f1:=proc(n) local k; add((n+k+1)!/((n-k)!*k!*2^k),k=0..n); end; [seq(f1(n),n=0..10)];
f2:=proc(n) local k; add((n+k+2)!/((n-k)!*k!*2^k),k=0..n); end; [seq(f2(n),n=0..10)];
f3:=proc(n) local k; add((n+k+3)!/((n-k)!*k!*2^k),k=0..n); end; [seq(f3(n),n=0..10)];
f4:=proc(n) local k; add((n+k+4)!/((n-k)!*k!*2^k),k=0..n); end; [seq(f4(n),n=0..10)];
a(n) is also the numerator of the continued fraction sequence beginning with 2 followed by 3 and the remaining odd numbers: [2,3,5,7,9,11,13,...]. - Gil Broussard, Oct 07 2009
Also, number of scenarios in the Gift Exchange Game when a gift can be stolen at most once. - N. J. A. Sloane, Jan 25 2017
|
|
|
REFERENCES
|
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 77.
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
|
Moa Apagodu, David Applegate, N. J. A. Sloane, and Doron Zeilberger, On-Line Appendix I to "Analysis of the gift exchange problem", giving Type D recurrences for G_1(n) through G_15(n) (see A001515, A144416, A144508, A144509, A149187, A281358-A281361)
Moa Apagodu, David Applegate, N. J. A. Sloane, and Doron Zeilberger, On-Line Appendix II to "Analysis of the gift exchange problem", giving Type C recurrences for G_1(n) through G_15(n) (see A001515, A144416, A144508, A144509, A149187, A281358-A281361)
|
|
|
FORMULA
|
The following formulas can all be found in (or are easily derived from formulas in) Grosswald's book.
D-finite with recurrence: a(0) = 1, a(1) = 2; thereafter a(n) = (2*n-1)*a(n-1) + a(n-2).
E.g.f.: exp(1-sqrt(1-2*x))/sqrt(1-2*x).
a(n) = Sum_{ k = 0..n } binomial(n+k,2*k)*(2*k)!/(k!*2^k).
Equivalently, a(n) = Sum_{ k = 0..n } (n+k)!/((n-k)!*k!*2^k) = Sum_{ k = n..2n } k!/((2n-k)!*(k-n)!*2^(k-n)).
a(n) = Hypergeometric2F0( [n+1, -n] ; - ; -1/2).
a(n) ~ exp(1)*(2n)!/(n!*2^n) as n -> oo. [See Grosswald, p. 124]
G.f.: 1/(1-x-x/(1-x-2*x/(1-x-3*x/(1-x-4*x/(1-x-5*x/(1-.... (continued fraction). - Paul Barry, Feb 08 2009
a(-1 - n) = a(n).
(a(n+1) + a(n+2))^2 = a(n)*a(n+2) + a(n+1)*a(n+3) for all integer n. (End)
G.f.: 1/G(0) where G(k) = 1 - x - x*(2*k+1)/(1 - x - 2*x*(k+1)/G(k+1)); (continued fraction). - Sergei N. Gladkovskii, Oct 05 2012
E.g.f.: E(0)/(2*sqrt(1-2*x)), where E(k) = 1 + 1/(1 - 2*x/(2*x + (k+1)*(1+sqrt(1-2*x))/E(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 23 2013
G.f.: T(0)/(1-x), where T(k) = 1 - (k+1)*x/((k+1)*x - (1-x)^2/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 15 2013
a(n) = exp(1)*sqrt(2/Pi)*BesselK(1/2+n,1). - Gerry Martens, Jul 22 2015
a(n) = (1/n!)*Integral_{x = 0..inf} exp(-x)*x^n*(1 + x/2)^n dx.
E.g.f.: d/dx( exp(x*c(x/2)) ) = 1 + 2*x + 7*x^2/2! + 37*x^3/3! + ..., where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108. (End)
a(n) = (1/2)_{n} * 2^n * hypergeometric1f1(-n; -2*n; 2).
G.f.: (1/(1-t))*hypergeometric2f0(1, 1/2; -; 2*t/(1-t)^2). (End)
|
|
|
EXAMPLE
|
y_0 = 1
y_1 = 1 + x
y_2 = 1 + 3*x + 3*x^2
y_3 = 1 + 6*x + 15*x^2 + 15*x^3, etc.
G.f. = 1 + 2*x + 7*x^2 + 37*x^3 + 266*x^4 + 2431*x^5 + 27007*x^6 + 353522*x^7 + ...
|
|
|
MAPLE
|
A001515 := proc(n) option remember; if n=0 then 1 elif n=1 then 2 else (2*n-1)*A001515(n-1)+A001515(n-2); fi; end;
A001515:=proc(n) local k; add( (n+k)!/((n-k)!*k!*2^k), k=0..n); end;
A001515:= n-> hypergeom( [n+1, -n], [], -1/2);
bessel := proc(n, x) add(binomial(n+k, 2*k)*(2*k)!*x^k/(k!*2^k), k=0..n); end;
|
|
|
MATHEMATICA
|
RecurrenceTable[{a[0]==1, a[1]==2, a[n]==(2n-1)a[n-1]+a[n-2]}, a[n], {n, 25}] (* Harvey P. Dale, Jun 18 2011 *)
Table[Sum[BellY[n+1, k, (2 Range[n+1] - 3)!!], {k, n+1}], {n, 0, 20}] (* Vladimir Reshetnikov, Nov 09 2016 *)
|
|
|
PROG
|
(PARI) {a(n) = if( n<0, n = -1 - n); sum( k=0, n, (2*n - k)! / (k! * (n-k)!) * 2^(k-n))} /* Michael Somos, Apr 08 2012 */
(Haskell)
(Magma) [(&+[Binomial(n+j, 2*j)*Catalan(j)*Factorial(j+1)/2^j: j in [0..n]]): n in [0..30]]; // G. C. Greubel, Sep 26 2023
(SageMath) [sum(binomial(n+j, 2*j)*binomial(2*j, j)*factorial(j)//2^j for j in range(n+1)) for n in range(31)] # G. C. Greubel, Sep 26 2023
|
|
|
CROSSREFS
|
See A144301 for other formulas and comments.
Replace "sets" with "lists" in comment: A001517.
The gift scenarios sequences when a gift can be stolen at most s times, for s = 1..9, are this sequence, A144416, A144508, A144509, A149187, A281358, A281359, A281360, A281361.
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
