# User:Compart

 C O M P A R T

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

## 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.