Compart is a personal blog of Adi Dani. Teacher of mathematics in secondary school "Niko Nestor" Struga.
Composition of a kset over set S
Let S be a subset of N and A a kset, then each msequence of subsets of A whose terms are called parts and
 number of elements of parts belong to set S
 the parts are pairwise disjoint
 union of all parts is equal to A
is called composition of kset 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 kset and
:
a msequence 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 msequence C is called a composition of kset A into mparts over set S
Denote by the set of compositions of the kset A into m parts over set
and by the number of compositions of a sets into parts oover .
Let be a composition of kset 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 kset 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_{0 }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 ksets 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 ksets 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 msequence of natural numbers who fulfills the
conditions
is called composition of natural number kinto mparts 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 kset 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 kset
is numbered by a number from set or in other words.
For example for 3set we have
1
Let be a composition of kset A into m parts over set then msequence
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
