Partitions

Quote: kubikulann

Quote: gordonm888

I note that one can assign a number of permutations to any partition (e.g.: the partition 3-2-1-1 has 12 permutations, ) and then sum up the number of permutations for every entry in this table. When I do that I get this table:

	1	2	3	4	5	6	7	8	9	10	Total
1	1										1
2	1	1									2
3	1	2	1								4
4	1	3	3	1							8
5	1	4	6	4	1						16
6	1	5	10	10	5	1					32
7	1	6	15	20	15	6	1				64
8	1	7	21	35	35	21	7	1			128
9	1	8	28	56	70	56	28	8	1		256
10	1	9	36	84	126	126	84	36	9	1	512

This is Pascal’s table. (aka Binomial coefficients table)

Quote: Wizard

Sorry to interrupt a good discussion, but here is a count of the number of pieces by size. The left column shows the piece size and along the top row is the base number that is getting partitioned.

Piece	1	2	3	4	5	6	7	8	9	10
1	1	2	4	7	12	19	30	45	67	97
2		1	1	3	4	8	11	19	26	41
3			1	1	2	4	6	9	15	21
4				1	1	2	3	6	8	13
5					1	1	2	3	5	8
6						1	1	2	3	5
7							1	1	2	3
8								1	1	2
9									1	1
10										1
Total	1	3	6	12	20	35	54	86	128	192

Offhand, the only interesting pattern I'm seeing is the total number of pieces generally divide lots of ways:

6 = 2*3
12 = 2*2*3
20 =2*2*5
35 = 5*7
54 = 2*3*3*3
86 = 2 * 43
128 = 2*2*2*2*2*2*2
192 = 2*2*2*2*2*2*3

I guess 86 is the exception.

Quote: gordonm888

The long silence after my last post ...

Quote: Wizard

I found a very good estimate for the P(n) if you know P(n-1).

Here it is

P(n) = P(n-1) * exp(0.923266 * n^-0.448858)

{snip}

I'm sure the estimate would become more accurate if I threw in more decimal places.

Quote: gordonm888

I think you could come up with a more accurate version of this formula if you derived two different formulas: one each for even and odd values of n. If you use one formula, you should always tend to overestimate for odd n and underestimate for even n.

Quote: Wizard

Doesn't this odd and even effect diminish over time? I did some calculus to get at a direct formula. However, there is already a good formula for this. I'll put it in spoiler tags. I'll just say that it goes back to what I wrote earlier, that series seems to always come down to pi, e, and primes. I'll add to that the Fibonacci series.

Partitions estimate

P(n) = 1/(4n*sqrt(3)) * exp(pi * sqrt(2n/3))

Quote: Wizard

Let me put into a table, what you said, because I love tables. The third column represents the sum of partitions from 1 to n-1, for n. For examples, for n=5, it equals P(1)+ P(2) + P(3) + P(4). As Gordon said, this column equals one less than the number of pieces of size one in the partition of n.

n	Partitions	Sum from 1 to n-1	Size 1
1	1	0	1
2	2	1	2
3	3	3	4
4	5	6	7
5	7	11	12
6	11	18	19
7	15	29	30
8	22	44	45
9	30	66	67
10	42	96	97
11	56	138	139
12	77	194	195
13	101	271	272
14	135	372	373
15	176	507	508

Offhand, I can't think of why this is true.

Quote: Wizard

Dang, I wrote out a long post on this, but the Internet was down and I lost it.

I'll just try to quickly rephrase the point. Let's let O(n) = Pieces of size 1 in the partitions of n.

As an example, consider O(5). We can tack on a one piece onto every partition of 4. However, the partitions of 4 already had some one pieces.

O(5) = P(4) + O(4).

To get O(4), we can tack on a one piece onto every partition of 3. However, the partitions of 3 already had some one pieces.

O(5) = P(4) + P(3) + O(3)

To get O(3), we can tack on a one piece onto every partition of 2. However, the partitions of 2 already had some one pieces.

O(5) = P(4) + P(3) + P(2) + O(2)

To get O(2), we can tack on a one piece onto every partition of 1. However, the partitions of 1 already had a single one piece.

O(5) = P(4) + P(3) + P(2) + P(1) + O(1) = P(4) + P(3) + P(2) + P(1) + 1 = 5 + 3 + 2 + 1 + 1 = 12

Quote: Wizard

Here are the Ramanujan identities.  Let P(x) = number of partitions of x.

P(5x + 4) is always divisible by 5
P(7x + 5) is always divisible by 7
P(11x + 6) is always divisible by 11

Here are a couple more that were discovered later:

P(17303x + 237) is always divisible by 13
P(206839x + 839) is always divisible by 17
P(1977147619x + 815655) is always divisible by 19

Makes you suspect there is another identity for the next prime, 23, but we haven't found it yet.

Quote: Wizard

Damn Excel doesn't handle big numbers very well, so my sample size is rather small...

I think I'll add more code to check the factorization for larger numbers. I can handle numbers up to 2^64 in C++. Projects like this make me jealous of the people who have Mathematica.

Quote: Wizard

I took the analysis of how often total partitions are divisible by a prime number up to an initial quantity of 405. Here are the results.

Prime	Count in 2 to 405	Ratio	Expected
2	181	44.8%	50.0%
3	139	34.4%	33.3%
5	139	34.4%	20.0%
7	101	25.0%	14.3%
11	108	26.7%	9.1%
13	25	6.2%	7.7%
17	17	4.2%	5.9%
23	18	4.5%	4.3%
29	11	2.7%	3.4%

This shows a huge surplus of total partitions divisible by 5, 7, and 11, especially 11. You may recall these are the same primes in the Ramanujan identities. Very interesting...

Quote: Wizard

Thanks for joining the thread!

Quote: Wizard

As to my source, I don't remember. It is entirely possible I made a mistake. Can you quote your own source and I'll correct that post.

Quote: Wizard

I shall check out those videos later, hopefully this evening.

Quote: Ajaxx

If at this point your head is spinning from all these cycles that is more than understandable, but here is the upshot. It seems we so often get a remainder of zero when dividing these first partition numbers by 11 because, for two of the eleven "tracks" (the ones starting at p(6) = 11 and at p(8) = 22) we start off with a remainder of 0, and the matching increment of 0 means that that remainder tends to stay put and keep producing partition numbers divisible by 11. Meanwhile, for the other tracks, we start off with a nonzero remainder — 4, for example, in the case of p(7) = 15 — but since that number is also the increment by which the remainder is allowed to drift, 0 is always one step away: our only choices initially are to drift up to twice the remainder (4 + 4 = 8 in our example), or drift down to 0 (4 - 4 = 0). So for a while, 0 appears way more in our table than any other number, and only when these drifts become more frequent and more random (which you can start to see happening towards the bottom for all but Ramanujan's column) do we approach 17.355% divisibility. The effect is less pronounced for mod 5 and mod 7, which makes sense since only one of the "tracks" starts off with a remainder of 0 in those cases.

Of course, pointing out this underlying phenomenon and calling it an explanation is probably unfair: if you ask me why we get these drifting remainders, the best I could give you would be "math is mystifying." I hope someone much smarter than I am is working on a better answer.

Quote: gordonm888

Quote: Ajaxx

If at this point your head is spinning from all these cycles that is more than understandable, but here is the upshot. It seems we so often get a remainder of zero when dividing these first partition numbers by 11 because, for two of the eleven "tracks" (the ones starting at p(6) = 11 and at p(8) = 22) we start off with a remainder of 0, and the matching increment of 0 means that that remainder tends to stay put...

Another way to state your "mechanism" is to say that n=11 has higher than expected divisibility into the partition numbers p(k) because, when considering  the more limited set of partition numbers p(k), k=0...(n-1) there are two numbers divisible by n (that is, in this case, divisible by 11.)   I wonder how often this occurs, and whether other such values of n have greater than expected divisibility.  For example, does 15 also divide into partition numbers an anomalously large number of times because p(7)=15 and p(9)=30  and those are both divisible by 15?

• The tables for mod 5 and mod 7 below show what happens when you have congruences but bad luck (i.e. no lucky second multiple in the first row). We have Ramanujan's unwavering column of zeroes, but the other columns start at small nonzero remainders that gradually drift with small nonzero increments. For some of the columns (see columns k=0 and k=1 in both tables) that actually means that it takes an usually long time for even a single 0 to appear, while others (like column k=6 in the mod 7 table) linger around 0 for a while before moving on. The overall effect is slightly less multiples than expected for mod 5 initially and slightly more for mod 7, but by the 180th partition number both of those effects have largely faded and we have 35.56% and 26.11% divisibility, respectively — only trivially different from the 36% and ~27.24% we expect.
• Your example, a modulus of 15, shows what happens when you have the converse: luck without congruences. 20% of the numbers in the first row happen to be divisible by 15, but that turns out not to mean much because there is little regularity to how the remainder drifts as you move vertically down the columns from there. Of course, 15's prime factors are 3 and 5, the latter being a Ramanujan prime, so the congruences are not entirely absent from this table; because p(5n + 4) is guaranteed to be divisible by 5, in the columns for k=4, 9 and 14 we can only get remainders that are divisible by 5, i.e. 0, 5, or 10. In other words, we expect not 1 out of 15 numbers (6.67%) in this table to be divisible by 15, but (3/15)×(1/3) + (12/15)×(1/15) = 27/225 = 3/25 = 12%, since there is a 1 out of 3 chance of divisibility in those three special columns and the normal 1 out of 15 chance in the remaining twelve (we get the same number by reasoning that a third of numbers divisible by 5 should be divisible by 15, and we calculated that 36% of partition numbers should be divisible by 5). The actual fraction does indeed approach 12% asymptotically from below as you can see in this chart, mirroring the fact that we approach 36% from below in the case of mod 5 but with additional noise thrown in from the random distribution of multiples of 3.