| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 638.1 | Partitions | ENGINE::ROTH | | Mon Jan 05 1987 08:12 | 18 |
| Such a sum is called a partition and leads to some very deep problems
in number theory.
There is an interesting grapical way of representing the sums - let
each i[k] be a row of i[k] dots, there will be m rows; eg:
o o o o i[1] = 4
o o o i[2] = 3
o i[3] = 1
This leads to a dual summation by transposing the figure
o o o j[i] = 3
o o j[2] = 2
o o j[3] = 2
o j[4] = 1
- Jim
|
| 638.2 | solution for m = 5 | EAGLE1::DANTOWITZ | Happy gnu year! | Mon Jan 05 1987 10:40 | 22 |
| For m=5 I got the following result for the number of sets
(i , i , i , i , i ) where the sum of the five is N.
1 2 3 4 5
g(N) = g(N-1) + h(N)
h(N) = h(N-1) + (N+1)(N+2)/2
g(1) = 5; h(1) = 4;
g(N) represents the number of sets of i with a sum of N where
j
0 <= i <= N.
j
Is there a closed form solution for this type of relationship?
David
|
| 638.3 | 00001000... | VINO::JMUNZER | | Mon Jan 05 1987 12:46 | 10 |
| How many strings of 1's and 0's are there that have (m-1) 1's and N 0's?
For m=5, each string can be diagrammed as:
0000000001000000000000010000000010000000010000000000
<---i ---> <----i ----> <--i --> <--i --> <---i --->
1 2 3 4 5
John
|
| 638.4 | Same sum | EAGLE1::DANTOWITZ | Happy gnu year! | Mon Jan 05 1987 13:22 | 7 |
| Re .3:
This is the same problem expressed in .0 since no two sets of i produce
j
the same string.
David
|
| 638.5 | | VINO::JMUNZER | | Mon Jan 05 1987 13:49 | 7 |
| Re .4: right --
( N + m - 1 )
( )
( m - 1 )
John
|
| 638.6 | | CLT::GILBERT | eager like a child | Mon Jan 05 1987 13:59 | 7 |
| Are the i ordered tuples or unordered sets?
j
If ordered tuples, then X(m,N) = C(N+m-1,m-1).
If they are unordered sets, the problem becomes quite interesting,
with a variety of important uses.
|
| 638.7 | A variation | EAGLE1::DANTOWITZ | Happy gnu year! | Mon Jan 05 1987 15:16 | 24 |
| Re .-1 :
What are some of the important uses for such numbers?
The results I needed were for an unordered set. For
my use I really only needed to solve it for m=5. The
solutions for m=1, 2, and 3 are trivial.
Getting closer to J.M.'s suggestion how about:
a b c d e
0 1 0 1 0
Where a+b+c+d+e = N?
How many UNIQUE patterns are generated? (The total number
of patterns is the function g(N) for m=5 presented earlier.)
This too was part of the problem I was working on. The answer
isn't too difficult.
David
|