Set compositions

This article needs more work.

Please help by expanding it!

Set compositions are compositions of sets.

Number of set compositions over set N_p

Denote by

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

the set of all positive integers no greater than $\scriptstyle p\,$, and by

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

the number of set compositions of a $\scriptstyle k\,$-set ($\scriptstyle k\,$ elements set) in $\scriptstyle m\,$ parts of size $\scriptstyle 1,\,2,\,\ldots ,\,p\,$.

Recurrence and initial conditions

${\overline {c}}_{0}(0,N_{p})=1{\text{ and }}{\overline {c}}_{0}(k,N_{p})=0{\text{ if }}k>0;\,$

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

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

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{\text{ and }}{\overline {c}}_{0}(k,N_{2})=0{\text{ if }}k>0;\,$

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

${\overline {c}}_{m}(k,N_{2})=\sum _{s=1}^{2}{\binom {k}{s}}~{\overline {c}}_{m-1}(k-s,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 . .

Explicit formula

Lets now prove the equation

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

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

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

for $\scriptstyle k\,=\,m+i\,$ because $\scriptstyle i\,=\,0,\,1,\,\ldots ,\,m\,$ follow that $\scriptstyle k\,=\,m,\,m+1,\,\ldots ,\,2m\,$ and replace $\scriptstyle i\,=\,k-m\,$ we get

$\sum _{i=0}^{m}{\binom {m}{i}}~{\frac {x^{m+i}}{2^{i}}}=\sum _{k=m}^{2m}{\binom {m}{k-m}}~{\frac {x^{k}}{2^{k-m}}}=\sum _{k=m}^{2m}{\binom {m}{k-m}}~{\frac {k!}{2^{k-m}}}~{\frac {x^{k}}{k!}}\,$

from above finally we conclude that

$\sum _{k=m}^{2m}{\overline {c}}_{m}(k,N_{2})~{\frac {x^{k}}{k!}}=\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 above formula

However, since

${\binom {m}{k}}={\frac {m!}{k!(m-k)!}}\,$

we get

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

Associated sequences

First sequence

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

giving the sequence (Cf. A080599$\scriptstyle (m),\,m\,\geq \,0\,$)

{1, 1, 3, 12, 66, 450, 3690, 35280, 385560, 4740120, 64751400, 972972000, 15949256400, 283232149200, 5416632421200, 110988861984000, 2425817682288000, ...}

where this number can be better explained as number of placing of $\scriptstyle 2m\,$ 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 2 objects.

Second sequence

Denote by

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

the number of all compositions of a k-set in parts (subsets) of size 1 or 2. This number is sum of all numbers thats are placed in k-th column of above table. From table we can read that

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

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

${\overline {c}}(2,N_{2})=3\,$

${\overline {c}}(3,N_{2})=12\,$

${\overline {c}}(4,N_{2})=66\,$

${\overline {c}}(5,N_{2})=450\,$

For example: all compositions of a 3-set {a,b,c} are

({a},{b,c}),({b,c},{a}),({b},{a,c}),({a,c},{b}),({c},{a,b}),({a,b},{c})
({a},{b},{c}),({a},{c},{b}),({b},{a},{c}),({b},{c},{a}),({c},{a},{b}),({c},{b},{a})

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

giving the sequence (Cf. A105749$\scriptstyle (k),\,k\,\geq \,0\,$)

{1, 2, 14, 222, 6384, 291720, 19445040, 1781750880, 214899027840, 33007837322880, 6290830003852800, 1456812592995513600, 402910665227270323200, ...}

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{\text{ and }}{\overline {c}}_{0}(k,N_{3})=0{\text{ if }}k>0;\,$

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

${\overline {c}}_{m}(k,N_{3})=\sum _{s=1}^{3}{\binom {k}{s}}~{\overline {c}}_{m-1}(k-s,N_{3})=k~{\overline {c}}_{m-1}(k-1,N_{3})~+~{\frac {1}{2}}~k(k-1)~{\overline {c}}_{m-1}(k-2,N_{3})~+~{\frac {1}{6}}~k(k-1)(k-2)~{\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 third row is done, then for the element $\scriptstyle {\overline {c}}_{m}(k,N_{3})\,$ of the fourth row from the recurrence we have

${\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}=\left({\frac {x}{6}}\right)^{m}\left(6+3x+x^{2}\right)^{m}=\left({\frac {x}{6}}\right)^{m}\sum _{i=0}^{m}{\binom {m}{i}}(6+3x)^{i}~x^{2m-2i}\,$

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

$=\sum _{i=0}^{m}\left(\sum _{j=0}^{i}{\binom {m}{i}}~{\binom {i}{j}}~2^{i-m-j}~3^{i-m}~x^{3m-2i+j}\right)\,$

for $\scriptstyle k\,=\,3m-2i+j\,$ we have $\scriptstyle j\,=\,k+2i-3m\,$, because $\scriptstyle i\,=\,0,\,1,\,\ldots ,\,m\,$ and $\scriptstyle j\,=\,0,\,1,\,\ldots ,\,i\,$ follow that $\scriptstyle k\,=\,m,\,m+1,\,\ldots ,\,3m\,$

$\sum _{i=0}^{m}\left(\sum _{j=0}^{i}{\binom {m}{i}}~{\binom {i}{j}}~2^{i-m-j}~3^{i-m}~x^{3m-2i+j}\right)=\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!}}\,$

finally we get

$\sum _{k=m}^{3m}{\overline {c}}_{m}(k,N_{3})~{\frac {x^{k}}{k!}}=\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 formula after equalizing of coefficients next to $\scriptstyle x\,$ we get

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

because $\scriptstyle {\binom {i}{k+2i-3m}}\,=\,0\,$ for $\scriptstyle i<k+2i-3m\,$ follow that only for $\scriptstyle i\,\leq \,3m-k\,$ expression $\scriptstyle {\binom {i}{k+2i-3m}}\,$ is not equal at 0 that means

${\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}}}\,$

$k+2i-3m\leq \,i\leq \,m\,$

using property

${\binom {m}{k}}={\frac {m!}{k!~(m-k)!}}\,$

we can show that

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

Associated sequences

First sequence

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

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

{1, 3, 62, 5052, 1087104, 487424520, 393702654960, 519740602925040, 1046019551260199040, 3046052768591313895680, 12322848899623787148556800, ...}

Second sequence

Denote by

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

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. From table we can read that

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

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

${\overline {c}}(2,N_{3})=3\,$

${\overline {c}}(3,N_{3})=13\,$

${\overline {c}}(4,N_{3})=74\,$

${\overline {c}}(5,N_{3})=530\,$

For example: all compositions of a 3-set {a,b,c} are

({a,b,c})
({a},{b,c}),({b,c},{a}),({b},{a,c}),({a,c},{b}),({c},{a,b}),({a,b},{c})
({a},{b},{c}),({a},{c},{b}),({b},{a},{c}),({b},{c},{a}),({c},{a},{b}),({c},{b},{a})

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

$i\leq \,3m-k\,$, $i\leq {\frac {k-3m}{2}}$

giving the sequence (Cf. A189886$\scriptstyle (k),\,k\,\geq \,0\,$)

{, ...}

Using Mathematica and the formula above we can find for sequence ${\overline {c}}(k,N_{3})$ following terms

$1,1,3,13,74,\,$

$530,4550,45570,521640,6717480,\,$

$96117000,1512819000,25975395600,483169486800,9678799930800,\,$

$207733600074000,4755768505488000,115681418156304000,2979408725813520000,80998627977002736000,\,$

$2317937034142810080000,69649003197501567840000,2192459412316607834400000,72152830779716793506400000,477756318984329979756160000\,$

See also

• Sets
  • Set partitions
  • Restricted set partitions
  • Restricted set compositions

• Multisets
  • Multiset partitions
  • Restricted multiset partitions
  • Multiset compositions
  • Restricted multiset compositions