User:Compart

From Wiki-site

Jump to: navigation, search
C O M P A R T

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

Contents

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 I_m=\{0,1,...,m-1\}\, 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


 :         C=(A_0,A_1,...,A_{m-1})\,


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


[1]        \bigcup_{i\in I_m}A_i=A

[2]         A_i \cap A_j = \varnothing.\,for any i and j in Im with ij,

[3]         \left| A_i \right|\in S \, for each i\in I_m\,


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

 
Denote by  \overline{C}_m(A,S) \,  the set of compositions of the k-set A into m parts over set S\, 

and by   \overline{c}_m(k,S) \, the number of compositions of a \scriptstyle k \,-sets into \scriptstyle m \, parts oover S \,.

Let be  C=(A_0,A_1,...,A_{m-1})\, a composition of k-set A  into m parts  over set

 S\,  then sequence


            |C|=(|A_0|,|A_1|,...,|A_{m-1}|)=(c_0,c_1,...,c_{m-1})\,


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

over set  S\,  because it fulfills conditions


           c_0+c_1+...+c_{m-1}=k\, , c_i\in S , i\in I_m \,


Denote by  C_{S}^{A}(c_0,c_1,...,c_{m-1})\, the set of all compositions of k-set A into m parts

over set S\, with common trace  (c_0,c_1,...c_{m-1})\,.   is clear that


[CK]      \overline C_{m}(A,S)=\bigcup _{\stackrel{ c_{0}+c_{1}+...+c_{m-1}=k}{c_{i}\in S ,i\in I_{m}}}C_{S}^{A}(c_0,c_1,...,c_{m-1})


Lets C be a composition from the set  C_{S}^{A}(c_0,c_1,...,c_{m-1})\, then first part who contain

celements from k elemnts in disposition can be choosen in  \binom {k}{c_0}\,  ways  after  that rest

 k-c_0\, elements from wich to fill second part who contain c_1\, elements we can do that in

 \binom{k-c_0}{c_1}\, ways. In this manner to fulfills first two parts we can do that in \binom{k}{c_0}\binom{k-c_0}{c_1}\,  

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


         \binom{k}{c_0}\binom{k-c_0}{c_1}\binom{k-c_0-c_1}{c_2}...\binom{k-c_0-c_1-c_2-...-c_{m-2}}{c_{m-1}}


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


              \frac{k!}{c_{0}!c_{1}!...c_{m-1}!}\,  where  c_0+c_1+...+c_{m-1}=k\, , c_i\in S , i\in I_m \,

In this way we prove that


             |C_{S}^{A}(c_{0},c_{1},...,c_{m-1})|=\frac{k!}{c_{0}!c_{1}!...c_{m-1}!}\,


If we consider above formula and [CK]  follow that


[CB]     \overline c_{m}(k,S)=\sum_{\stackrel{ c_{0}+c_{1}+...+c_{m-1}=k}{c_{i}\in S ,i\in I_{m}}} \frac {k!}{c_{0}!c_{1}!...c_{m-1}!}\,


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


            \overline c_0(0,S)=1\,,   \overline c_{0}(k,S)=0,k>0


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


[RCB]   \overline c_m(k,S)=\sum_{j\in S}\binom{k}{j}\overline c_{m-1}(k-j,S)


using formula [CB] we have 


          \overline c_{m}(k,S)=\sum_{\stackrel{ c_{0}+c_{1}+...+c_{m-1}=k}{c_{i}\in S ,i\in I_{m}}} \frac {k!}{c_{0}!c_{1}!...c_{m-1}!}=

                            =\sum_{c_{m-1}\in S}\sum_{\stackrel{ c_{0}+c_{1}+...+c_{m-2}=k-c_{m-1}}{c_{i}\in S ,i\in I_{m-1}}} \frac {k!}{c_{0}!c_{1}!...c_{m-1}!}=\,

                           =\sum_{j\in S}\frac{1}{j!}\sum_{\stackrel{ c_{0}+c_{1}+...+c_{m-2}=k-j}{c_{i}\in S ,i\in I_{m-1}}} \frac {k!}{c_{0}!c_{1}!...c_{m-2}!}=\,

                          =\sum_{j\in S}\frac{k!}{j!(k-j)!}\sum_{\stackrel{ c_{0}+c_{1}+...+c_{m-2}=k-j}{c_{i}\in S ,i\in I_{m-1}}} \frac {(k-j)!}{c_{0}!c_{1}!...c_{m-2}!}=\,

                          =\sum_{j\in S}\binom{k}{j}\overline c_{m-1}(k-j,S)


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 I_m=\{0,1,...,m-1\}\, the set of natural numbers leser

than m,m>1.The m-sequence of natural numbers c=(c_0,c_1,...,c_{m-1})\, who fulfills the

conditions


               c_0+c_1+...+c_{m-1}=k,c_i\in S , i\in I_m \,


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

 
Denote by  {C}_m(k,S) \,  the set of compositions of the k into m parts over set  S\,  and by  


[CB]         c_{m}(k,S)=\sum_{\stackrel{ c_{0}+c_{1}+...+c_{m-1}=k}{c_{i}\in S ,i\in I_{m}}} 1\,


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 


                 c_0(0,S)=1\,    c_0(k,S)=0,k>0\,

            

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


[RCB]   c_m(k,S)=\sum_{j\in S} c_{m-1}(k-j,S)


using formula [CB] we have 


           c_{m}(k,S)=\sum_{\stackrel{ c_{0}+c_{1}+...+c_{m-1}=k}{c_{i}\in S ,i\in I_{m}}} 1=

                             =\sum_{c_{m-1}\in S}\sum_{\stackrel{ c_{0}+c_{1}+...+c_{m-2}=k-c_{m-1}}{c_{i}\in S ,i\in I_{m-1}}} 1=\,

                              =\sum_{j\in S}\sum_{\stackrel{ c_{0}+c_{1}+...+c_{m-2}=k-j}{c_{i}\in S ,i\in I_{m-1}}}1 =\,

                              =\sum_{j\in S} c_{m-1}(k-j,S)


     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=\{a_0,a_1,...,a_{k-1}\}\, a k-set and S(A_k)\, the set of all subsets of  set A_k\,

For each  B\subset A_k\, we defines a number


          g_B=\sum_{a_j\in B} {2^j}\,


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


         g_{A_k}=\sum_{a_j\in A_k}2^j=2^0+2^1+...+2^{k-1}=\frac{1-2^k}{1-2}=2^k-1\, 


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 I_{2k}=\{0,1,...,2^k-1\}\,  or in other words.


       |S(A_k)|=|I_{2^k}|=2^k\,


For example for 3-set A_3=\{a_0,a_1,a_2\}\, we have

 

S(A_3)\, I_{2^3}=I_8 \, Binary code
\empty\, 0\, 000\,
\{a_0\}\, 2^0=1\, 001\,
\{a_1\}\, 2^1=2\, 010\,
\{a_0,a_1\}\, 2^0+2^1=3\, 011\,
\{a_2\}\, 2^2=4\, 100\,
\{a_0,a_2\}\, 2^0+2^2=5\, 101\,
\{a_1,a_2\}\, 2^1+2^2=6\, 110\,
\{a_0,a_1,a_2\}\, 2^0+2^1+2^2=7\, 111\,

1

Let be  C=(C_0,C_1,...,C_{m-1})\, a composition of k-set A  into m parts  over set  S\,  then m-sequence


          g(C)=(g_{C_0},g_{C_1},...,g_{C_{m-1}})


is called shadow of composition C of set A that is a composition of number 2^{k-1}\, into m parts because

 

        g_{C_0}+g_{C_1}+...+g_{C_{m-1}}=\sum_{a_j\in C_0}2^j+\sum_{a_j\in C_1}2^j+...+\sum_{a_j\in C_{m-1}}2^j=\,


                                     =\sum_{a_{j} \in {C_0 \cup C_1 \cup ...\cup C_{m-1}}}2^j=\sum_{a_{j}\in{ A_k}}2^j=2^{0+1+...+k-1}=2^{k}-1\,


Partition of natural number 2^{k}-1\, into m parts t(C)=[g_{C_0},g_{C_1},...,g_{C_{m-1}}] 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


Personal tools

sl
דומיין בעברית  דומיין  דומין  תוכנה לניהול  קשרי לקוחות  CRM, ניהול קשרי לקוחות  דומין בעברית  פורומים  ספרדית  גיבוי