[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

638.0. "some sum" by EAGLE1::DANTOWITZ (DmD) Wed Dec 31 1986 17:23

	If you have m variables: i    such that 0 <= i  <= N 
                                  j                   j

        and         m
                   ---     
                   \   i  = N
                   /    j
                   ---
                   j=1

    
        How many sets of  (i , i , ... , i )  are possible?
                            1   2         m


	David        

T.RTitleUserPersonal
Name
DateLines
638.1PartitionsENGINE::ROTHMon Jan 05 1987 11:1218
    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.2solution for m = 5EAGLE1::DANTOWITZHappy gnu year!Mon Jan 05 1987 13:4022
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.300001000...VINO::JMUNZERMon Jan 05 1987 15:4610
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.4Same sumEAGLE1::DANTOWITZHappy gnu year!Mon Jan 05 1987 16:227
Re .3:

This is the same problem expressed in .0 since no two sets of i  produce
                                                               j
the same string.

David
638.5VINO::JMUNZERMon Jan 05 1987 16:497
Re .4:  right --

    			( N + m - 1 )
			(	    )
			(   m - 1   )

John
638.6CLT::GILBERTeager like a childMon Jan 05 1987 16:597
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.7A variationEAGLE1::DANTOWITZHappy gnu year!Mon Jan 05 1987 18:1624
	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