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

%I #40 Sep 12 2015 11:00:29

%S 1,1,2,9,46,335,2786,28357,325382,4280859,62437882,1010306825,

%T 17852477006,343275422503,7120802805650,158697470231757,

%U 3778977532041430,95794295907958547,2574920565897373610,73164585387874543057,2191028450841437523230,68974613397532849153311

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

%H Alois P. Heinz, <a href="/A219614/b219614.txt">Table of n, a(n) for n = 0..200</a>

%H V. Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Interesting asymptotic formulas for binomial sums</a>, Jun 09 2013

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

%F 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

%e 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).

%p with (combinat):

%p a:= n-> add(stirling2(n, k)*k! *binomial(n-k+1, k), k=0..ceil(n/2)):

%p seq (a(n), n=0..30); # _Alois P. Heinz_, Dec 06 2012

%t Table[Sum[Binomial[n-k+1,k]StirlingS2[n,k]k!,{k,0,n}],{n,0,20}]

%t (* 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 *)

%Y Cf. A120368.

%K nonn

%O 0,3

%A _Geoffrey Critzer_, Dec 06 2012