tag:blogger.com,1999:blog-4068183698747623113.post341199773624255718..comments2014-06-11T04:05:31.722-04:00Comments on A CS Professor's blog: Counting permutations: an open questionClaire Mathieuhttp://www.blogger.com/profile/10957755706440077623noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-4068183698747623113.post-16773910498075315512012-10-01T15:20:08.994-04:002012-10-01T15:20:08.994-04:00To answer my own question, I guess one way of thin...To answer my own question, I guess one way of thinking about it is as follows.<br /><br />Fix one direction, and place one 1 uniformly and independently at random on each of the n^d parallel lines in that direction. For each of the dn^d lines not in the fixed direction, there's an approximately 1/e chance that the line contains exactly one 1 (the limiting distribution is Poisson with mean 1). <br /><br />These events aren't independent for different lines, but they should me "nearly" independent in some sense (placing one 1 on one line doesn't have too much impact on the possible locations of 1's on other lines). So you might expect the probability every line contains exactly one 1 to be roughly e^{-d n^d}. Kevin C.http://www.blogger.com/profile/08760942816103747988noreply@blogger.comtag:blogger.com,1999:blog-4068183698747623113.post-46953826895220656152012-09-28T19:46:14.849-04:002012-09-28T19:46:14.849-04:00Is there some natural heuristic that suggests why ...Is there some natural heuristic that suggests why this should be the correct bound? Kevin C.http://www.blogger.com/profile/08760942816103747988noreply@blogger.com