User:Adi Dani /Compositions and Partitions of sets

This page is under construction!

Compositions and Partitions of sets over set N_p

Adi Dani, May 2011

KEYWORDS: Compositions of k-set over set N_p ,Partitions of k-set over set N_p.
Concerned with sequences:  A080599, A105749, A144422, A189886, A000085, A001515, A001680, A144416

Definitions

Denote by $N_{p}=\{1,2,\ldots ,p\}\,$

the set of all positive integers no greater than $\scriptstyle p\,$, Lets A be a k-set and

$C=(A_{1},A_{2},...,A_{m})\,$

a m-sequence whose terms are subsets of set A that fullfill conditions

1. $\bigcup _{i\in N_{m}}A_{i}=A$

2. $A_{i}\cap A_{j}=\varnothing .\,$for any i and j in $N_{m}$ with i ≠ j,

3. $\left|A_{i}\right|\in N_{p}\,$ for each $i\in N_{m}\,$

then the sequence C is called a composition of k-set A in m-parts over set $N_{p}\,$
The terms of C are called the blocks, parts or cells of the composition.

Denote by

${\overline {C}}_{m}(A,N_{p})\,$

the set of all compositions of the k-set A in m parts over set $N_{p}\,$ and by

${\overline {c}}_{m}(k,N_{p})\,$

the number of compositions of a $\scriptstyle k\,$-set into $\scriptstyle m\,$ parts of size $\scriptstyle 1,\,2,\,\ldots ,\,p\,$.
This number can be
interpreted as number of placing of k distinguishable objects in m distinguishable boxes
with condition that in each box can be placed at least 1 object but no more than p objects Lets A be a k-set and

$P=\{A_{1},A_{2},,...,A_{m}\}\,$

a m-set of subsets of set A that fullfill conditions

1. $\bigcup _{i\in N_{m}}A_{i}=A$

2. $A_{i}\cap A_{j}=\varnothing .\,$for any i and j in $N_{m}$ with i ≠ j

3. $\left|A_{i}\right|\in N_{p}\,$ for each $i\in N_{m}\,$

then the set P is called a partition of k-set A in m-parts over the set $N_{p}\,$
The elements of P are called the blocks, parts or cells of the partition.

Denote by

${\overline {P}}_{m}(A,N_{p})\,$

the set of all partitions of the k-set A in m parts over the set $N_{p}\,$ and by

${\overline {p}}_{m}(k,N_{p})\,$

the number of partitions of a $\scriptstyle k\,$-sets in m parts over the set $N_{p}\,$ This number can be
interpreted as number of placing of k distinguishable objects in m indistinguishable boxes
with condition that in each box can be placed at least 1 object but no more than p objects

From definitions of partitions and compositions of sets follow that each partition of a
set in m-parts produce $m!$ compositions of same set thats mean

$(R)~~~~{\overline {p}}_{m}(k,N_{p})={\frac {1}{m!}}{\overline {c}}_{m}(k,N_{p})\,$

Number of set compositions over set N_p

Recurrence and initial conditions

(1)... ${\overline {c}}_{0}(0,N_{p})=1\,$

(2)... ${\overline {c}}_{m}(k,N_{p})=0{\text{ if }}k<m{\text{ or }}k>mp;$

(3)... ${\overline {c}}_{m}(k,N_{p})=\sum _{s=1}^{p}{\binom {k}{s}}~{\overline {c}}_{m-1}(k-s,N_{p}).\,$

From (2) for m=0 follow that

(4)... ${\overline {c}}_{0}(k,N_{p})=0{\text{ if }}k>0\,$

Generating function

$\sum _{k=0}^{\infty }{\overline {c}}_{m}(k,N_{p})~{\frac {x^{k}}{k!}}=\sum _{k=m}^{pm}{\overline {c}}_{m}(k,N_{p})~{\frac {x^{k}}{k!}}=\left(x+{\frac {x^{2}}{2!}}+\ldots +{\frac {x^{p}}{p!}}\right)^{m}\,$

Associated sequences

${\overline {c}}(k,N_{p})=\sum _{m=0}^{\infty }{\overline {c}}_{m}(k,N_{p})=\sum _{m=\lfloor k/p\rfloor }^{k}{\overline {c}}_{m}(k,N_{p})\,$

${\overline {c}}_{m}(N_{p})=\sum _{k=0}^{\infty }{\overline {c}}_{m}(k,N_{p})=\sum _{k=m}^{pm}{\overline {c}}_{m}(k,N_{p})\,$

Number of set compositions over set N₂

Table

From general case for $\scriptstyle p\,=\,2\,$ we get

${\overline {c}}_{0}(0,N_{2})=1\,$

${\overline {c}}_{m}(k,N_{2})=0{\text{ if }}k<m{\text{ or }}k>2m;\,$

${\overline {c}}_{m}(k,N_{2})=k{\overline {c}}_{m-1}(k-1,N_{2})+{\frac {1}{2}}k(k-1){\overline {c}}_{m-1}(k-2,N_{2})\,$

Based upon recurrence and initial conditions we can establish the table row after row

m\k 0 1 2 3 4 5 6 7 8 9 10 .. $\scriptstyle {\overline {c}}_{m}(N_{2})$ 0 1 0 0 0 0 0 0 0 0 0 0 . 1 1 0 1 1 0 0 0 0 0 0 0 0 . 2 2 0 0 2 6 6 0 0 0 0 0 0 . 14 3 0 0 0 6 36 90 90 0 0 0 0 . 222 4 0 0 0 0 24 240 1080 2520 2520 0 0 . 6384 5 0 0 0 0 0 120 1800 12600 50400 113400 113400 . 291720 .. . . . . . . . . . . . . . $\scriptstyle {\overline {c}}(k,N_{2})$ 1 1 3 12 66 450 3690 35280 385560 4740120 64751400 . .

this table read by rows after omiting the ending zeroes gives the sequence 1,0,1,1,1,0,0,2,6,6,0,0,0,6,36,90,90,0,0,0,0,... The sequence is not in oeis

Explicit formula

From generating function for $\scriptstyle p\,=\,2\,$ we have that

$\sum _{k=m}^{2m}{\overline {c}}_{m}(k,N_{2})~{\frac {x^{k}}{k!}}=\left(x+{\frac {x^{2}}{2}}\right)^{m}\,$

and using the binomial theorem

    $\left(x+{\frac {x^{2}}{2}}\right)^{m}=\sum _{k=m}^{2m}{\binom {m}{k-m}}{\frac {k!}{2^{k-m}}}{\frac {x^{k}}{k!}}\,$

after equalizing the coefficients next same power of $\scriptstyle x\,$ we get 

${\overline {c}}_{m}(k,N_{2})={\binom {m}{k-m}}{\frac {k!}{2^{k-m}}}\,$

formula count the number of compositions of k-set into m parts over N2

these numbers are showed in table and they are not in oeis

from  m<=k<=2m or k/2<= m<=k follow formulas

  

${\overline {c}}_{m}(N_{2})=\sum _{k=m}^{2m}{\binom {m}{k-m}}{\frac {k!}{2^{k-m}}}\,$

that counts the number of compositions of sets into m parts over N_{2.  I}n other words the

sum of elements in m-th row of above table. These numbers are showed in the last column

of table giving the sequence (Cf. A080599$\scriptstyle (m),\,m\,\geq \,0\,$). Number $\scriptstyle {\overline {c}}_{m}(N_{2})\,$ can be interpreted as

Number of placing of indefinite number of distinguishable objects into $\scriptstyle m\,$ distinguishable

boxes with condition that in each box can be placed at least 1 object but no more than 2 objects.and

${\overline {c}}(k,N_{2})=\sum _{m=\lfloor k/2\rfloor }^{k}{\binom {m}{k-m}}{\frac {k!}{2^{k-m}}}\,$

thats counts the number of compositions of a k-set into parts (subsets) of size 1 or 2. This number

is sum of all numbers thats are placed in k-th column of above table. These numbers are showed in

last row of above table giving the sequence (Cf. A105749$\scriptstyle (k),\,k\,\geq \,0\,$)

For example: all compositions of a 3-set {a,b,c} over $N_{2}\,$ are

$\scriptstyle (\{a,\},\{b,c\}),~(\{b,c\},\{a\}),~(\{b\},\{a,c\}),~(\{a,c\},\{b\}),~(\{c\},\{a,b\}),~(\{a,b\},\{c\})\,$

$\scriptstyle (\{a\},\{b\},\{c\}),~(\{a\},\{c\},\{b\}),~(\{b\},\{a\},\{c\}),~(\{b\},\{c\},\{a\}),~(\{c\},\{a\},\{b\}),~(\{c\},\{b\},\{a\})\,$

Number $\scriptstyle {\overline {c}}(k,N_{2})\,$ can be interpreted as Number of placing of k distinguishable objects in indefinite

number of distinguishable boxes with condition that in each box can be placed at least 1 object

but no more than 2 objects.

Number of set compositions over set N₃

Table

Using the initial conditions and recurrences mentioned for the general case for $\scriptstyle p\,=\,3\,$ we get

${\overline {c}}_{0}(0,N_{3})=1\,$

${\overline {c}}_{m}(k,N_{3})=0{\text{ if }}k<m{\text{ or }}k>3m;\,$

${\overline {c}}_{m}(k,N_{3})={\binom {k}{1}}{\overline {c}}_{m-1}(k-1,N_{3})+{\binom {k}{2}}{\overline {c}}_{m-1}(k-2,N_{3})+{\binom {k}{3}}{\overline {c}}_{m-1}(k-3,N_{3})\,$

from this recurrence now we can construct the following table row after row

m\k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 .. $\scriptstyle {\overline {c}}_{m}(N_{3})$ 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 . 3 2 0 0 2 6 14 20 20 0 0 0 0 0 0 0 0 0 . 62 3 0 0 0 6 36 150 450 1050 1680 1680 0 0 0 0 0 0 . 5052 4 0 0 0 0 24 240 1560 7560 29400 90720 218400 369600 369600 0 0 0 . 10871804 5 0 0 0 0 0 120 1800 16800 117600 667880 3137400 12243000 38880800 96096000 168168000 168168000 . 487424520 .. . . . . . . . . . . . . . . . . . . $\scriptstyle {\overline {c}}(k,N_{3})$ 1 1 3 13 74 530 4550 45570 521640 6717480 96117000 1512819000 25975395600 483169486800 9678799930800 207733600074000 . .

for example, suppose that the row m=3 is done, then for the element $\scriptstyle {\overline {c}}_{4}(k,N_{3})\,$ of row m=4 from the recurrence we have

$\scriptstyle {\overline {c}}_{4}(5,N_{3})=5{\overline {c}}_{3}(4,N_{3})+10{\overline {c}}_{3}(3,N_{3})+10~{\overline {c}}_{3}(2,N_{3})=5\times 36+10\times 6+10\times 0=240.\,$

Explicit formula

From the generating function for $\scriptstyle p\,=\,3\,$ and using the binomial theorem we have

$\sum _{k=m}^{3m}{\overline {c}}_{m}(k,N_{3}){\frac {x^{k}}{k!}}=\left(x+{\frac {x^{2}}{2}}+{\frac {x^{3}}{6}}\right)^{m}\,$

and using the binomial theorem twice we have

$\left(x+{\frac {x^{2}}{2}}+{\frac {x^{3}}{6}}\right)^{m}=\sum _{k=m}^{3m}\left(\sum _{i=0}^{m}{\binom {m}{i}}{\binom {i}{k+2i-3m}}{\frac {k!}{2^{k+i-2m}3^{m-i}}}\right){\frac {x^{k}}{k!}}\,$

from above formulas after equalizing of coefficients next to x taking in account that from m>=i>=k+2i-3m>=0

follow that 0<= i<=3m-k  we can write formula  

${\overline {c}}_{m}(k,N_{3})=\sum _{i=0}^{3m-k}{\binom {m}{i}}{\binom {i}{k+2i-3m}}{\frac {k!}{2^{k+i-2m}3^{m-i}}}\,$

that count the number of compositions of k-set into m parts over set N3 (subsets) of size 1,2 or 3.

This number is placed in comon cell of m-th row and k-th column of above table. The table gives the

sequence oeis|A000000. Number can be explained as number of placing of k distinguishable objects

into m distinguishable boxes with condition that in each box can be placed at least 1 object but no

more than 3 objects. Because from rm<=k<=3m follow that k/3<=m<=k

     ${\overline {c}}_{m}(N_{3})=\sum _{k=m}^{3m}\sum _{i=0}^{3m-k}{\binom {m}{i}}{\binom {i}{k+2i-3m}}{\frac {k!}{2^{k+i-2m}3^{m-i}}}\,$

formula count the number of compositions of sets into m parts over N3 sum of compositions

of sets into m parts over set N₃ or sum of all numbers in the row m of above table these

numbers gives the sequence (Cf. A144422$\scriptstyle (m),\,m\,\geq \,0\,$)

Number $\scriptstyle {\overline {c}}_{m}(N_{3})\,$ can be explained as number of placing of at least m objects but
no more than $\scriptstyle 3m\,$ distinct objects(balls) in $\scriptstyle m\,$ distinct boxes(bins) with
condition that in each box can be placed at least 1 object but no more than 3 objects.

and

    ${\overline {c}}(k,N_{3})=\sum _{m=\lfloor k/3\rfloor }^{k}\sum _{i=0}^{3m-k}{\binom {m}{i}}{\binom {i}{k+2i-3m}}{\frac {k!}{2^{k+i-2m}3^{m-i}}}\,$

that formula count the number of all compositions of a k-set in parts (subsets) of size 1,2

or 3. This number is sum of all numbers thats are placed in k-th column of above table.

giving the sequence  (Cf. A189886$\scriptstyle (k),\,k\,\geq \,0\,$).Number can be explained as number of placing

of  k distinguishable objects into indefinite number of distinguishable  boxes  with
condition that in each box can be placed at least 1 object but no more than 3 objects.

For example: all compositions of a 3-set {a,b,c} over the set $N_{3}\,$ are

$\scriptstyle (\{a,b,c\})\,$

$\scriptstyle (\{a,\},\{b,c\}),~(\{b,c\},\{a\}),~(\{b\},\{a,c\}),~(\{a,c\},\{b\}),~(\{c\},\{a,b\}),~(\{a,b\},\{c\})\,$

$\scriptstyle (\{a\},\{b\},\{c\}),~(\{a\},\{c\},\{b\}),~(\{b\},\{a\},\{c\}),~(\{b\},\{c\},\{a\}),~(\{c\},\{a\},\{b\}),~(\{c\},\{b\},\{a\})\,$

Number of set partitions over set N_p

Recurrence and initial conditions

${\overline {p}}_{0}(0,N_{p})=1\,$

${\overline {p}}_{m}(k,N_{p})=0{\rm {~if~}}k<m{\rm {~and~}}k>mp;\,$

${\overline {p}}_{m}(k,N_{p})=\sum _{s=1}^{p}{\binom {k-1}{k-s}}{\overline {p}}_{m-1}(k-s,N_{p}).\,$

Generating function

$\sum _{k=0}^{\infty }{\overline {p}}_{m}(k,N_{p})~{\frac {x^{k}}{k!}}={\frac {1}{m!}}\left(x+{\frac {x^{2}}{2!}}+\ldots +{\frac {x^{p}}{p!}}\right)^{m}\,$

Associated sequences

${\overline {p}}(k,N_{p})=\sum _{m=0}^{\infty }{\overline {p}}_{m}(k,N_{p})\,$

${\overline {p}}_{m}(N_{p})=\sum _{k=0}^{\infty }{\overline {p}}_{m}(k,N_{p})\,$

Number of set partitions over set N₂

Table

Based on initals conditions and general recurrence for $\scriptstyle p\,=\,2\,$ we have following formulas

${\overline {p}}_{0}(0,N_{2})=1\,$

${\overline {p}}_{m}(k,N_{2})=0{\rm {~if~}}k<m{\rm {~and~}}k>2m;\,$

${\overline {p}}_{m}(k,N_{2})={\overline {p}}_{m-1}(k-1,N_{2})+(k-1){\overline {p}}_{m-1}(k-2,N_{2})\,$

m\k 0 1 2 3 4 5 6 7 8 9 10 .. $\scriptstyle {\overline {p}}_{m}(N_{2})$ 0 1 0 0 0 0 0 0 0 0 0 0 . 1 1 0 1 1 0 0 0 0 0 0 0 0 . 2 2 0 0 1 3 3 0 0 0 0 0 0 . 7 3 0 0 0 1 6 15 15 0 0 0 0 . 37 4 0 0 0 0 1 10 45 105 105 0 0 . 266 5 0 0 0 0 0 1 15 105 420 945 945 . 2431 .. . . . . . . . . . . . . . $\scriptstyle {\overline {p}}(k,N_{2})$ 1 1 2 4 10 26 76 232 764 2620 9496 . .

this table is in oeis A144331

Explicit formula

From relation between compositions and partitions follow that   

${\overline {p}}_{m}(k,N_{2})={\binom {m}{k-m}}{\frac {k!}{m!2^{k-m}}}\,$

formula count the number of partitions of k-set into m parts over N2

these numbers are showed in table and they are not in oeis

from  m<=k<=2m or k/2<= m<=k follow formulas

  

${\overline {p}}_{m}(N_{2})=\sum _{k=m}^{2m}{\binom {m}{k-m}}{\frac {k!}{m!2^{k-m}}}\,$

that counts the number of partitions of sets into m parts over N_{2.  I}n other words the

sum of elements in m-th row of above table. These numbers are showed in the last column

of table giving the sequence A001515). Number $\scriptstyle {\overline {p}}_{m}(N_{2})\,$ can be interpreted as

Number of placing of indefinite number of distinguishable objects into $\scriptstyle m\,$ indistinguishable

boxes with condition that in each box can be placed at least 1 object but no more than 2 objects.and

${\overline {p}}(k,N_{2})=\sum _{m=\lfloor k/2\rfloor }^{k}{\binom {m}{k-m}}{\frac {k!}{m!2^{k-m}}}\,$

thats counts the number of partitions of a k-set into parts (subsets) of size 1 or 2. This number

is sum of all numbers thats are placed in k-th column of above table. These numbers are showed in

last row of above table giving the sequence A000085

For example: all partitions of a 3-set {a,b,c} over $N_{2}\,$ are

$\scriptstyle (\{a,\},\{b,c\}),~(\{b\},\{a,c\}),~(\{c\},\{a,b\}),\,$

$\scriptstyle (\{a\},\{b\},\{c\})\,$

Number $\scriptstyle {\overline {p}}(k,N_{2})\,$ can be interpreted as Number of placing of k distinguishable objects in indefinite

number of indistinguishable boxes with condition that in each box can be placed at least 1 object

but no more than 2 objects.

Number of set partitions over set N₃

Table

Based on initals conditions and general recurrence of number of partitions over N_p for $\scriptstyle p\,=\,3\,$ we have following formulas

${\overline {p}}_{0}(0,N_{3})=1{\rm {~and~}}{\overline {p}}_{0}(k,N_{3})=0{\rm {~if~}}k>0;\,$ m=0

${\overline {p}}_{m}(k,N_{3})={\overline {p}}_{m-1}(k-1,N_{3})+(k-1){\overline {p}}_{m-1}(k-2,N_{3})+{\binom {k-1}{2}}{\overline {p}}_{m-1}(k-3,N_{3})\,$ m>0

based on these formulas we can construct an infinite table by rows m, m>=0 and by colums k, k>=0 in common cell of

row m and column k we place the number of partitions of k set into m parts over set N₃   first row from initial conditions

starts with 1 and all other entries are 0 then based on second formula we fill the row m=1 after that again since row m=1

is filled, continue filling row m=2 etc...In this way we get table.

m\k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 .. $\scriptstyle {\overline {p}}_{m}(N_{3})$ 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 . 3 2 0 0 1 3 7 10 10 0 0 0 0 0 0 0 0 0 . 31 3 0 0 0 1 6 25 75 175 280 280 0 0 0 0 0 0 . 842 4 0 0 0 0 1 10 65 315 1225 3780 9100 15400 15400 0 0 0 . 45296 5 0 0 0 0 0 1 15 140 980 5565 26145 102025 323400 800800 1401400 1401400 . 4061871 .. . . . . . . . . . . . . . . . . . . $\scriptstyle {\overline {p}}(k,N_{3})$ 1 1 2 5 14 46 166 652 2780 12644 61136 312676 1680592 9467680 55704104 341185496 . .

this series 1,0,1,1,1,0,0,1,3,7,10,10,0,0,0,0,1,6,25,75,175,280,280,... is not in oeis

Explicit formula

From formula

${\overline {p}}_{m}(k,N_{3})={\frac {1}{m!}}{\overline {c}}_{m}(k,N_{3})\,$

we conclude that

${\overline {p}}_{m}(k,N_{3})=\sum _{i=0}^{3m-k}{\binom {m}{i}}{\binom {i}{k+2i-3m}}{\frac {k!}{m!2^{k+i-2m}3^{m-i}}}\,$

that count the number of partitions of k-set into m parts over set $N_{3}$. These numbers are placed in
above table giving the sequence oeis|A000000. Number ${\overline {p}}_{m}(k,N_{3})$ can be interpreted as

number of placing of kdistinguishable objects into m indistinguishable boxes with condition that

into each box can be placed at least 1 object but no more than 3 objects.

     ${\overline {p}}_{m}(N_{3})=\sum _{k=m}^{3m}\sum _{i=0}^{3m-k}{\binom {m}{i}}{\binom {i}{k+2i-3m}}{\frac {k!}{m!2^{k+i-2m}3^{m-i}}}\,$

formula count the number of partitions of sets into m parts over N3

the sum of  numbers of partitions of k-sets into exactly m parts of size 1,2 or 3 alias
sum of elements placed in m-th row of above table. These sums appears in last

column of table giving the sequence oeis|A144416. Number $\scriptstyle {\overline {p}}_{m}(N_{3})\,$ can be explained as

number of placing of indefinite number of distinguishable  objects into m indistiguishable
boxes with condition that into each box can be placed at least 1 object but no more than 3

objects. and

    ${\overline {p}}(k,N_{3})=\sum _{m=\lfloor k/3\rfloor }^{k}\sum _{i=0}^{3m-k}{\binom {m}{i}}{\binom {i}{k+2i-3m}}{\frac {k!}{m!2^{k+i-2m}3^{m-i}}}\,$

that formula count number of partitions of k-set with parts over N3

the sum of all partitions of k-set where k is fixed natural number, into parts  of size 1,2 or 3 alias
the sum of  elements placed in k-th column of above table. These sums are placed in last row
of table giving the sequence oeis|A001680. Number $\scriptstyle {\overline {p}}_{(}k,N_{3})\,$ can be explained as number of ways

of placing of k distiguishable objects into indefinite number of indistiguishable boxes with condition

that into each box can be placed at least 1 object but no more than 3 objects.

References

1. David Applegate and N. J. A. Sloane, The Gift Exchange Problem (arXiv:0907.0513, 2009)
2. R. A. Proctor, Let's Expand Rota's Twelvefold Way for Counting Partitions!, arXiv math.CO.0606404.
3. Sachkov, V.N. Introduction to combinatorial methods of discrete mathematics. (Vvedenie v kombinatornye

metody diskretnoj matematiki). Moskva: Nauka. 384 p. R. 1.00 (1982).