A219614 Number of ways to put n labeled objects into n labeled boxes so that no two nonempty boxes are adjacent.

1, 1, 2, 9, 46, 335, 2786, 28357, 325382, 4280859, 62437882, 1010306825, 17852477006, 343275422503, 7120802805650, 158697470231757, 3778977532041430, 95794295907958547, 2574920565897373610, 73164585387874543057, 2191028450841437523230, 68974613397532849153311

Offset

0,3

Links

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

V. Kotesovec, Interesting asymptotic formulas for binomial sums, Jun 09 2013

Formula

a(n) = Sum_{k>=0} binomial(n-k+1,k)*Stirling2(n,k)*k!.

Limit n->infinity (a(n)/n!)^(1/n) = (3*r^2-3*r+1)/(1-2*r) = 1.53445630931668421506236..., where r = 0.410751485627... is the root of the equation (1-2*r)^2 + r*(1-3*r+3*r^2)*LambertW(-exp(-1/r)/r) = 0. - Vaclav Kotesovec, Dec 08 2012

Example

a(3) = 9 because we have: (1,1,3), (1,3,1), (1,3,3), (3,1,1), (3,1,3), (3,3,1), (1,1,1), (2,2,2), (3,3,3).

Maple

with (combinat):
a:= n-> add(stirling2(n, k)*k! *binomial(n-k+1, k), k=0..ceil(n/2)):
seq (a(n), n=0..30);  # Alois P. Heinz, Dec 06 2012

Mathematica

Table[Sum[Binomial[n-k+1, k]StirlingS2[n, k]k!, {k, 0, n}], {n, 0, 20}]
(* Program for numerical value of the limit (a(n)/n!)^(1/n) *) (3*r^2-3*r+1)/(1-2*r)/.FindRoot[(1-2*r)^2+r*(1-3*r+3*r^2)*LambertW[-E^(-1/r)/r]==0, {r, 1/2}, WorkingPrecision->100] (* Vaclav Kotesovec, Dec 08 2012 *)

Crossrefs

Cf. A120368.

Sequence in context: A161798 A365855 A134091 * A183166 A032331 A049371

Adjacent sequences: A219611 A219612 A219613 * A219615 A219616 A219617

Keyword

nonn

Author

Geoffrey Critzer, Dec 06 2012

Status

approved