OFFSET
0,3
COMMENTS
Compare to the following identities, which hold for all fixed k:
(1) Sum_{n>=0} n!*x^n = Sum_{n>=0} x^n * (n + k*x)^n / (1 + n*x + k*x^2)^(n+1).
(2) Sum_{n>=0} n!*x^(2*n) = Sum_{n>=0} x^n * (k + n*x)^n / (1 + k*x + n*x^2)^(n+1).
Number of ordered set partitions of [n] such that for each block b the smallest integer interval containing b has at most two elements. a(3) = 10: 12|3, 3|12, 1|23, 23|1, 1|2|3, 1|3|2, 2|1|3, 2|3|1, 3|1|2, 3|2|1 (block 13 is not allowed here). - Alois P. Heinz, Sep 21 2016
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..450
FORMULA
O.g.f.: Sum_{n>=0} n^n * x^n * (1+x)^n / (1 + n*x + n*x^2)^(n+1).
a(n) = Sum_{k=0..[n/2]} binomial(n-k, k) * (n-k)!.
a(n) ~ exp(1) * n!. - Vaclav Kotesovec, Aug 02 2014
EXAMPLE
O.g.f.: A(x) = 1 + x + 3*x^2 + 10*x^3 + 44*x^4 + 234*x^5 + 1470*x^6 +...
where
A(x) = 1 + x*(1+x) + 2!*x^2*(1+x)^2 + 3!*x^3*(1+x)^3 + 4!*x^4*(1+x)^4 +...
Also, we have the identity:
A(x) = 1 + x*(1+x)/(1+x+x^2)^2 + 2^2*x^2*(1+x)^2/(1+2*x+2*x^2)^3 + 3^3*x^3*(1+x)^3/(1+3*x+3*x^2)^4 + 4^4*x^4*(1+x)^4/(1+4*x+4*x^2)^5 +...
MAPLE
a:= proc(n) option remember; `if`(n<3, n^2-n+1,
(n-2)*a(n-1)+(2*n-1)*a(n-2)+(n-1)*a(n-3))
end:
seq(a(n), n=0..25); # Alois P. Heinz, Sep 21 2016
MATHEMATICA
Table[Sum[Binomial[n-k, k] * (n-k)!, {k, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Aug 02 2014 *)
PROG
(PARI) {a(n)=local(A=1); A=sum(m=0, n, m^m*x^m*(1+x)^m/(1 + m*x + m*x^2 +x*O(x^n))^(m+1)); polcoeff(A, n)}
for(n=0, 30, print1(a(n), ", "))
(PARI) {a(n)=sum(k=0, n\2, binomial(n-k, k) * (n-k)! )}
for(n=0, 30, print1(a(n), ", "))
CROSSREFS
KEYWORD
nonn
AUTHOR
Paul D. Hanna, Aug 02 2014
STATUS
approved