A240172 O.g.f.: Sum_{n>=0} n! * x^n * (1+x)^n.

1, 1, 3, 10, 44, 234, 1470, 10656, 87624, 806280, 8211000, 91707120, 1114793280, 14653936080, 207138844080, 3133376225280, 50508380361600, 864341342363520, 15650522186302080, 298948657681094400, 6007868689030387200, 126719410500228268800, 2799004485444175008000, 64613640777996615782400

Offset: 0

Author

Paul D. Hanna, Aug 02 2014

Keywords

• nonn

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

Examples

			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 +...
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..450

Crossrefs

Column k=2 of A276890.

Programs

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 *)

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),", "))

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