|
%I
%S 1,10,107,1346,19917,341986,6713975,148717762,3674435393,100284451730,
%T 2998366140915,97510068994690,3428106725444117,129590070259759042,
%U 5242767731544271343,226057515078414496898,10350122253780835777545
%N Number of car parking assignments of n cars in n spaces, if one car does not park.
%C k=1 column of table 1, p. 4. The k=0 column is (with proper offset) A000272. Abstract: Suppose that n drivers each choose a preferred parking space in a linear car park with m spaces. Each driver goes to the chosen space and parks there if it is free and otherwise takes the first available space with larger number (if any). If all drivers park successfully, the sequence of choices is called a parking function. In general, if k drivers fail to park, we have a defective parking function of defect k. Let cp(n,m,k) be the number of such functions.
%C In this paper, we establish a recurrence relation for the numbers cp(n,m,k) and express this as an equation for a three-variable generating function. We solve this equation using the kernel method and extract the coefficients explicitly: it turns out that the cumulative totals are partial sums in Abel's binomial identity. Finally, we compute the asymptotics of cp(n,m,k. In particular, for the case m=n, if choices are made independently at random, the limiting distribution of the defect (the number of drivers who fail to park), scaled by the square root of n, is the Rayleigh distribution. On the other hand, in case m=omega(n), the probability that all spaces are occupied tends asymptotically to one.
%H Peter J. Cameron, Daniel Johannsen, Thomas Prellberg and Pascal Schweitzer, <a href="http://arxiv.org/abs/0803.0302">Counting Defective Parking Functions</a>
%F a(n) = 2*(n+2)^(n-1)-(3*n+1)*(n+1)^(n-2). - _Vladeta Jovovic_, Jul 21 2008
%F a(n)=2*A007830(n-1)-A016777(n)*A007830(n-2). [From _R. J. Mathar_, Aug 09 2008]
%e Table 1 of Cameron et al.:
%e ================================================================================================================
%e ....|........k=0.|........k=1.|........k=2.|........k=3.|.......k=4.|......k=5.|.....k=6.|...k=7.|..k=8.|k=9|
%e ================================================================================================================
%e n=1..|..........1.|............|............|............|...........|..........|.........|.......|......|...|.
%e n=2..|..........3.|..........1.|............|............|...........|..........|.........|.......|......|...|.
%e n=3..|.........16.|.........10.|..........1.|............|...........|..........|.........|.......|......|...|.
%e n=4..|........125.|........107.|.........23.|..........1.|...........|..........|.........|.......|......|...|.
%e n=5..|.......1296.|.......1346.|........436.|.........46.|.........1.|..........|.........|.......|......|...|.
%e n=6..|......16807.|......19917.|.......8402.|.......1442.|........87.|........1.|.........|.......|......|...|.
%e n=7..|.....262144.|.....341986.|.....173860.|......41070.|......4320.|......162.|.......1.|.......|......|...|.
%e n=8..|....4782969.|....6713975.|....3924685.|....1166083.|....176843.|....12357.|.....303.|.....1.|......|...|.
%e n=9..|..100000000.|..148717762.|...96920092.|...34268902.|...6768184.|...710314.|...34660.|...574.|....1.|...|.
%e n=10.|.2357947691.|.3674435393.|.2612981360.|.1059688652.|.256059854.|.36046214.|.2743112.|.96620.|.1103.|.1.|.
%e ================================================================================================================
%Y Cf. A000272.
%K nonn,uned,changed
%O 2,2
%A _Jonathan Vos Post_, Jul 09 2008
%E Extended beyond a(10) by _R. J. Mathar_, Aug 09 2008
| 