0.30 btc bounty: maths help (statistics)

[lemonginger]

hours to work out? Come on people this is a permutations 101 question.

[1715416940]

1715416940

[1715416940]

1715416940

[1715416940]

1715416940

[1715416940]

1715416940

[ByteCoin]

You can check your solution against these exact answers:

0	_	738035/120932352
1	_	586435/10077696
2	_	4301435/20155392
3	_	33057475/90699264
4	_	33616325/120932352
5	_	1145495/15116544
6	_	737353/181398528

I don't think it's a particularly easy problem.
An exact formula for the probability of no matches is

6^-12 * Sum_{k=1..6}(6-k)^6 * C(6,k) * Sum_{j=0..k} (-1)^(k-j) * C(k,j) * j^n

where C(a,b)=a!/(b!*(a-b)!)

but this is a simpler case than the other numbers of matches.

Possibly proper mathematicians have more powerful tools to bring to bear on such problems.

Explaining even this simple formula would take quite a lot of work but if you're willing to crack open a maths book then "Stirling numbers of the second kind" would be a good place to start.

ByteCoin

[untitlednotepad]

sorry i thought someone who is familiar with this kind of thing might be able to do it easily. i certainly didn't expect it to take 5 hours for the right person (although i admit it might take me 5 weeks to work it out).

[kjj]

Sorry for resurrecting this ancient thread, but I figure it is already in obsolete, so no one will care.

For some reason, I started thinking about this again.  I had forgotten the part about the Stirling numbers, but I had the "well, duh!" moment when I realized that 6^12 is only about 2 billion, and I might maybe be able to find some sort of computing device capable of iterating all of the combinations.

Code:

  2176782336			Random	Diff		Stirling	Diff
0   13284630	0.6103%		0.61%	-0.0016%	0.6103%		0.0000%
1  126669960	5.8191%		5.82%	-0.0028%	5.8191%		0.0000%
2  464554980	21.3414%	21.33%	0.0081%		21.3414%	0.0000%
3  793379400	36.4473%	36.43%	0.0213%		36.4473%	0.0000%
4  605093850	27.7976%	27.80%	0.0010%		27.7976%	0.0000%
5  164951280	7.5778%		7.60%	-0.0232%	7.5778%		0.0000%
6    8848236	0.4065%		0.41%	-0.0028%	0.4065%		0.0000%