## Poll

 I'm interested in this topic too. 7 votes (41.17%) I solved this problem when I was 15. No votes (0%) I have no idea how to talk to women. 2 votes (11.76%) I'm clueless 2 votes (11.76%) Isn't the 6-4 tile called a partition? 2 votes (11.76%) Doesn't this topic violate the New Rule? 6 votes (35.29%) I'll wait for teliot to come along. No votes (0%) Total eclipse reminder -- 04/08/2024 4 votes (23.52%) Live Stream reminder Aug 15 2 votes (11.76%) Tigres del Norte are playing Laughlin on Oct 26 1 vote (5.88%)

17 members have voted

unJon Joined: Jul 1, 2018
• Posts: 1802
August 20th, 2019 at 2:09:10 PM permalink
Quote: Wizard

That hits the nail on the head. This is the kind of thing that is probably best discussed over a few beers than a calculator, but, briefly, I feel nothing in math is a coincidence or random. There are patterns in everything, but sometimes we can't find an exact expression for them...yet. Everything seems to boil down to some function of pi, e, or prime numbers. Some, maybe me, would go so far as to claim it is evidence of a higher power.

Don�t forget Pascal�s triangle and sine waves in the list of concepts that pop up in interesting places.
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
gordonm888 Joined: Feb 18, 2015
• Posts: 2563
August 20th, 2019 at 2:11:58 PM permalink
Quote: Wizard

If there's a term for it, I don't know what it is. The way my math works is I keep track of the maximum height in any given partition. For example, the number of partitions in 100 equals:

P(100) = P(1) + P(2) + ... + P(50) (these are for the cases where the height of the longest stack is 50 to 100) + P(51,49) + P(52,48) + ... P (100,1),
where P(x,y) = Number of partitions where x is the total items and y is the maximum height of a stack.

For example if the height of the largest stack is 30, then there are 70 left, but you can't have a stack higher than 30.

Just one way of getting the answer by brute force.

Yes, I do something very similar, except I use the length of the partition. This is the table I calculate for the the first 10 numbers. In this table the number being partitioned is in the first column, and the row across the top is the length of the partitions. This table gives the number of partitions of a given length for each number - and, in the last column, the total number of partitions. However if you want to create the number of partitions of 10 of various lengths, it is necessary to first calculate values for the first 9 rows. And if you wanted to create a row for the partitions of 200, you would first need to calculate the rows for 1-199.

1
2
3
4
5
6
7
8
9
10
Total
1
1
1
2
1
1
2
3
1
1
1
3
4
1
2
1
1
5
5
1
2
2
1
1
7
6
1
3
3
2
1
1
11
7
1
3
4
3
2
1
1
15
8
1
4
5
5
3
2
1
1
22
9
1
4
7
6
5
3
2
1
1
30
10
1
5
8
9
7
5
3
2
1
1
42

I think one approach is to seek analytical formulas for all the entries in any given row in this table and then sum to get the total number of partitions.

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

Notice that this table appears to have distinct patterns and it may be possible to find analytical formulas to calculate these numbers.. The question in my mind is: if we can find algebraic formulas to calculate this 'permutations' table, might that be an intermediate step to calculate the "number of partitions" table that I showed first? or, more directly, the total number of partitions for any given number?
Last edited by: gordonm888 on Aug 20, 2019
So many better men, a few of them friends, were dead. And a thousand thousand slimy things lived on, and so did I.
unJon Joined: Jul 1, 2018
• Posts: 1802
August 20th, 2019 at 2:59:14 PM permalink
Quote: gordonm888

Yes, I do something very similar, except I use the length of the partition. This is the table I calculate for the the first 10 numbers. In this table the number being partitioned is in the first column, and the row across the top is the length of the partitions. This table gives the number of partitions of a given length for each number - and, in the last column, the total number of partitions. However if you want to create the number of partitions of 10 of various lengths, it is necessary to first calculate values for the first 9 rows. And if you wanted to create a row for the partitions of 200, you would first need to calculate the rows for 1-199.

1
2
3
4
5
6
7
8
9
10
Total
1
1
1
2
1
1
2
3
1
1
1
3
4
1
2
1
1
5
5
1
2
2
1
1
7
6
1
3
3
2
1
1
11
7
1
3
4
3
2
1
1
15
8
1
4
5
5
3
2
1
1
22
9
1
4
7
6
5
3
2
1
1
30
10
1
5
8
9
7
5
3
2
1
1
42

I think one approach is to seek analytical formulas for all the entries in any given row in this table and then sum to get the total number of partitions.

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

Notice that this table appears to have distinct patterns and it may be possible to find analytical formulas to calculate these numbers.. The question in my mind is: if we can find algebraic formulas to calculate this 'permutations' table, might that be an intermediate step to calculate the "number of partitions" table that I showed first? or, more directly, the total number of partitions for any given number?

It looks to me that every number in the last table can be generated as the sum of the number directly above and the number just above and to the left.
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
ThatDonGuy Joined: Jun 22, 2011
• Posts: 4278
August 20th, 2019 at 4:24:49 PM permalink
For those of you interested in some "professional" analysis, Donald Knuth of Stanford goes into partition generation in volume 4A of his Art of Computer Programming series of books. Volumes 1-3 have been around for decades, and are generally considered to be the Computer Scientist's Bible - at least, in my opinion (and that's saying something when a Berkeley graduate praises somebody at Stanford).
discflicker Joined: Jan 1, 2011
• Posts: 452
August 20th, 2019 at 7:59:31 PM permalink
Can this explain why it is that electron orbitals fill up in a strange order? Could it be that these orbitals follow distinct groupings that numerically break down into partitions? I think so! It functions as if there are a huge number of combinations, but since all electrons are identical, we only need to consider the numbers of PERMUTATIONS... that 's what I suspect... the counts of these various permutations define the atomic orbitals. Similar to the way a dish of sand will form distinct geometric shapes at various frequencies, the placements of the orbitals, as well as their discrete energy elevations, fall into distinct numeric groupings. Here is an example of applying sets of distinct numeric groupings into the physics of electron orbitals...

https://brianwhitworth.com/quantum-realism-4-6-3-the-evolution-of-electron-shells/

If you look at these tables, they definitely resemble many of the data relation discussed on this thread.

Marty, 20-Aug-2019
The difference between zero and the smallest possible number? It doesn't matter; once you cross that edge, it might as well be the difference between zero and 1. The difference between infinity and reality? They are mutually exclusive.
gordonm888 Joined: Feb 18, 2015
• Posts: 2563
August 20th, 2019 at 8:16:16 PM permalink
Quote: unJon

Quote: gordonm888

Yes, I do something very similar, except I use the length of the partition. This is the table I calculate for the the first 10 numbers. In this table the number being partitioned is in the first column, and the row across the top is the length of the partitions. This table gives the number of partitions of a given length for each number - and, in the last column, the total number of partitions. However if you want to create the number of partitions of 10 of various lengths, it is necessary to first calculate values for the first 9 rows. And if you wanted to create a row for the partitions of 200, you would first need to calculate the rows for 1-199.

1
2
3
4
5
6
7
8
9
10
Total
1
1
1
2
1
1
2
3
1
1
1
3
4
1
2
1
1
5
5
1
2
2
1
1
7
6
1
3
3
2
1
1
11
7
1
3
4
3
2
1
1
15
8
1
4
5
5
3
2
1
1
22
9
1
4
7
6
5
3
2
1
1
30
10
1
5
8
9
7
5
3
2
1
1
42

I think one approach is to seek analytical formulas for all the entries in any given row in this table and then sum to get the total number of partitions.

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

Notice that this table appears to have distinct patterns and it may be possible to find analytical formulas to calculate these numbers.. The question in my mind is: if we can find algebraic formulas to calculate this 'permutations' table, might that be an intermediate step to calculate the "number of partitions" table that I showed first? or, more directly, the total number of partitions for any given number?

It looks to me that every number in the last table can be generated as the sum of the number directly above and the number just above and to the left.

Yes, I agree. But the desire is to generate the numbers on any given row without generating all the previous rows. I think that can be done for the permutation table, and perhaps for the "number of partitions table." But whether it will lend itself to a tractable analytic expression is not clear. But I think its an attractive line of inquiry to pursue.
So many better men, a few of them friends, were dead. And a thousand thousand slimy things lived on, and so did I.
gordonm888 Joined: Feb 18, 2015
• Posts: 2563
August 21st, 2019 at 6:32:12 AM permalink
Quote: gordonm888

Yes, I do something very similar, except I use the length of the partition. This is the table I calculate for the the first 10 numbers. In this table the number being partitioned is in the first column, and the row across the top is the length of the partitions. This table gives the number of partitions of a given length for each number - and, in the last column, the total number of partitions. However if you want to create the number of partitions of 10 of various lengths, it is necessary to first calculate values for the first 9 rows. And if you wanted to create a row for the partitions of 200, you would first need to calculate the rows for 1-199.

1
2
3
4
5
6
7
8
9
10
Total
1
1
1
2
1
1
2
3
1
1
1
3
4
1
2
1
1
5
5
1
2
2
1
1
7
6
1
3
3
2
1
1
11
7
1
3
4
3
2
1
1
15
8
1
4
5
5
3
2
1
1
22
9
1
4
7
6
5
3
2
1
1
30
10
1
5
8
9
7
5
3
2
1
1
42

I think one approach is to seek analytical formulas for all the entries in any given row in this table and then sum to get the total number of partitions.

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

Notice that this table appears to have distinct patterns and it may be possible to find analytical formulas to calculate these numbers.. The question in my mind is: if we can find algebraic formulas to calculate this 'permutations' table, might that be an intermediate step to calculate the "number of partitions" table that I showed first? or, more directly, the total number of partitions for any given number?

D'oh. The values in the 2nd table are combin(N,L) where the first column is N and the first row is L.
So many better men, a few of them friends, were dead. And a thousand thousand slimy things lived on, and so did I.
kubikulann Joined: Jun 28, 2011
• Posts: 905
August 21st, 2019 at 6:46:44 AM permalink
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)
Reperiet qui quaesiverit
gordonm888 Joined: Feb 18, 2015
• Posts: 2563
August 21st, 2019 at 12:32:59 PM permalink
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)

Thank you, Kubikulann! You are not only very smart, but apparently you know/remember more math than most of us, lol.

Well, Pascal's Triangle/Table has all the qualities we have been noticing. As Unjon pointed out, every table entry is the sum of two table entries above it. As I pointed out, every entry can be calculated independently as combin(n,k) and that the rows in the table, as I compiled it, sum to 2n. Its a remarkable triangle/table and has been very well studied and characterized by zillions of mathematicians.

RECAP
I arrived at Pascal's table by creating Table A - the table of partitions of N that are of length L, because we can sum across the rows to get the total partitions of N. Table A can be created readily by using recursive methods on a spreadsheet or in a computer program, so if you want to know the number of partitions of any N, you must first calculate rows 1...N-1 of the table. We are seeking a non-recursive way to calculate the partitions of any given N>

So, I created Table B -which for any given N,L is the sum of the permutations (Rearrangements in a linear sequence) of all the partitions of N that are length L. I was hoping this table might have entries that could be calculated directly and might be an intermediate step to directly calculating any row of Table A. And, eureka!, the Table B is the well-known Pascal's Table and every entry is indeed directly calculable as being combin(N,L).

So, can we use the value of an N,L entry in Pascal's table to derive the value of an N,L entry in Table A? I have started to work on that and my preliminary conclusion is that we will need to know the number of partitions for 1 to N-1 in order to go from the Nth row in Pascal's table to the Nth row in Table A. That is, we probably need to do the identical amount of work as the recursion method for calculating partitions. So, right now, starting with a row in Table B (Pascal's table) and deriving a row in Table A doesn't look like a promising approach.

I guess the thing to try next is to see whether there is a way of directly calculating all the entries in a Row in Table A. Obviously, seeking a non-recursive (direct) algorithm for calculating partitions of any given N is a very difficult problem.
So many better men, a few of them friends, were dead. And a thousand thousand slimy things lived on, and so did I.
Wizard Joined: Oct 14, 2009
• Posts: 21923
August 21st, 2019 at 2:13:17 PM permalink
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.
It's not whether you win or lose; it's whether or not you had a good bet.