User:Compart

Compart is a personal blog of Adi Dani. Teacher of mathematics in secondary school "Niko Nestor" Struga.

• Published papers

• Contributed talks
• Books
• Compositions over arithmetic progressions
• nt
• Partitions of sets

Composition of a k-set over set S

Let S be a subset of N and A  a k-set, then each m-sequence of subsets of A whose terms are called parts and

1. number of elements of parts belong to set S
2. the parts are pairwise disjoint
3. union of all parts is equal to A

is called composition of k-set A into m parts over set S.

As you may noticed there is not mentioned condition that parts are nonempty sets I think that conditition who is

wanted in many almost all books on combinatorics is intetionally omitted here because the empty set equally as

other sets can be a part

Composition of sets

Let be S a subset of N and  the set of natural numbers leser

than m,m>1. Lets A be any set who have k elements we call simply a k-set and

 :         

a m-sequence whose terms (blocks or parts) are subsets of set A that fulfills the conditions

[1]        

[2]         for any i and j in I_m with i ≠ j,

[3]          for each

then the m-sequence C is called a composition of k-set A into m-parts over set S

 
Denote by    the set of compositions of the k-set A into m parts over set  

and by    the number of compositions of a -sets into  parts oover .

Let be   a composition of k-set A  into m parts  over set

   then sequence

is called weight of composition C. Weight is composition of natural number k into m parts

over set    because it fulfills conditions

            , 

Denote by   the set of all compositions of k-set A into m parts

over set  with common trace  .   is clear that

[CK]      

Lets C be a composition from the set   then first part who contain

c₀ elements from k elemnts in disposition can be choosen in    ways  after  that rest

  elements from wich to fill second part who contain  elements we can do that in

  ways. In this manner to fulfills first two parts we can do that in   

ways. Continue this way to fill all parts we get that it can do in

distinct ways. Easily can prove that expression above is equal at

                where   , 

In this way we prove that

If we consider above formula and [CK]  follow that

[CB]     

Formula [CB] count the number of compositions of k-sets into m parts over set S as we see

the formula is very complicated and is defined for m>0, We must notice that compositions of

nonempty  set  into  0  parts  do not exists  but, since empty set has no  elements we must

aximatise that exists 1 composition of empty set into 0 parts that means

            ,   

Now for m>0 we will prove a very interesting recurrence

[RCB]   

using formula [CB] we have 

Number of compositions of k-sets into m parts over set S can be interpreted as number of way

of placing of k distinguishable objects into m distinguishable boxes with condition that into

each box can be placed  s elements only if s is element of S

Composition of natural numbers

Let be S a subset of N and  the set of natural numbers leser

than m,m>1.The m-sequence of natural numbers  who fulfills the

conditions

is called composition of natural number k-into m-parts over set S

 
Denote by    the set of compositions of the k into m parts over set    and by  

[CB]        

the number of compositions of the k into m parts over set S. Formula [CB] is defined for m>0,

We must notice that compositions of nonempty set into 0 parts  do  not  exists, but  since

empty sequencet has no terms we must axiomatise thats,exists 1 composition of number 0

into 0 parts that means 

                 ,     

Now for m>0 we will prove a very interesting recurrence

[RCB]   

using formula [CB] we have 

     Number of compositions of natural number k into m parts over set S can be interpreted as

number of ways of placing of k indistinguishable objects into m distinguishable boxes with

condition that into each box can be placed  s elements only if s is element of S

Partitions of set over S

Now we introduce concept of partition of set and find a recurrence

Let be  a k-set and  the set of all subsets of  set 

For each   we defines a number

that is called binary code of subset and this number may take values from 0 for empty subset to

for entire set that from definition is subset of itself. This way we prove that each subset of a k-set

is numbered by a number from set   or in other words.

For example for 3-set  we have

		Binary code

1

Let be   a composition of k-set A  into m parts  over set    then m-sequence

is called shadow of composition C of set A that is a composition of number  into m parts because

Partition of natural number  into m parts  is called trace of 

composition C. Is clear that two distinct compositions have distinct shadows but two distinct compositions

can have the same trace. Now we can define

The set of all compositions of set A into m parts over set S that have the same trace is called a partition

of set A into m parts over set S.

Sequences, sets and multisets