User:Adi Dani /Restricted compositions of natural numbers

Restricted compositions of natural numbers

Adi Dani, May-June 2011

KEYWORDS: Compositions of even natural numbers into parts over set
Compositions of odd natural numbers into parts over set.
Concerned with sequences: A000012, A000079, A007051, A004171, A034478, A081341, A034494, A092811, A083884, A093143, A191484, A171714, A036486, A000982, A004526, A191489, A191494, A191495, A191496

Compositions of natural number k into m parts over set I_s

Definition

Denote by $I_{m}\,$ the set of all natural numbers lesser than given natural number m (0 is included

in set of natural numbers N).

Each m-sequence $c=(c_{0},c_{1},...,c_{m-1})\,$  of natural numbers that fulfill the condition

$c_{0}+c_{1}+...+c_{m-1}=k,c_{i}\in I_{s},i\in I_{m},s>0\,$

is called composition of natural number k in m parts over set Is. Denote by

$C_{m}(k,I_{s})=\{(c_{0},c_{1},...,c_{m-1}):c_{0}+c_{1}+...+c_{m-1}=k,c_{i}\in I_{s},i\in I_{m}\}\,$

the set of compositions of natural number k into m parts over set Is and by

$c_{m}(k,I_{s})={\binom {m}{k}}_{s}=\sum _{\stackrel {c_{0}+c_{1}+...+c_{m-1}=k}{c_{i}\in I_{s},i\in I_{m}}}1\,$

number of compositions of natural number k in m parts over set I_s. The number

${\binom {m}{k}}_{s}\,$

is called s-nomial coefficient s>0. For s=2 we get binomial coefficients and in that case we write

${\binom {m}{k}}_{2}={\binom {m}{k}}\,$

these numbers play central role in combinatorics. There appears parameters m,k, both

natural numbers, from definition follow that for m>0

${\binom {m}{k}}_{s}=0,k\notin I_{m(s-1)+1}=\{0,1,2,...,m(s-1)\}\,$

with boundary values

${\binom {m}{0}}_{s}={\binom {m}{m(s-1)}}_{s}=1\,$

we extend the case and for m=0 use 

${\binom {0}{k}}_{s}=0,k>0,{\binom {0}{0}}_{s}=1\,$

Recurrent relation

From definition follow that

${\binom {m}{k}}_{s}=\sum _{\stackrel {c_{0}+c_{1}+...+c_{m-1}=k}{c_{i}\in I_{s},i\in I_{m}}}1=\sum _{c_{m-1}\in I_{s}}\sum _{\stackrel {c_{0}+c_{1}+...+c_{m-2}=k-c_{m-1}}{c_{i}\in I_{s},i\in I_{m-1}}}1=\,$

             $=\sum _{j\in I_{s}}\sum _{\stackrel {c_{0}+c_{1}+...+c_{m-2}=k-j}{c_{i}\in I_{s},i\in I_{m-1}}}1=\sum _{j\in I_{s}}{\binom {m-1}{k-j}}_{s}\,$

in this way we get recurrence

[R]      ${\binom {m}{k}}_{s}=\sum _{i=0}^{s-1}{\binom {m-1}{k-i}}_{s}\,$

Theorem of symmetry

Suppose that $(c_{0},c_{1},...,c_{m-1})\in C_{m}(k,I_{s})\,$ then from definition follow that

$c_{0}+c_{1}+...+c_{m-1}=k,c_{i}\in I_{s},i\in I_{m}\,$

then composition

      $(s-1-c_{0},s-1-c_{1},...,s-1-c_{m-1})\in C_{m}(m(s-1)-k,I_{s})\,$

because

       $(s-1-c_{0})+(s-1-c_{1})+...+(s-1-c_{m-1})=m(s-1)-k\,$ 

and   $s-1-c_{i}\in I_{s}\,$ for each $i\in I_{m}\,$

Conversely

suppose that $(c_{0},c_{1},...,c_{m-1})\in C_{m}(m(s-1)-k,I_{s})\,$ then from definition follow that

$c_{0}+c_{1}+...+c_{m-1}=m(s-1)-k,c_{i}\in I_{s},i\in I_{m}\,$

then composition

    $(s-1-c_{0},s-1-c_{1},...,s-1-c_{m-1})\in C_{m}(k,I_{s})\,$

because

     $(s-1-c_{0})+(s-1-c_{1})+...+(s-1-c_{m-1})=k\,$ 

and $s-1-c_{i}\in I_{s}\,$ for each $i\in I_{m}\,$

that mean 

       $|C_{m}(k,I_{s})|=|C_{m}(m(s-1)-k,I_{s})|\,$

finally we get the theorem of symmetry

      ${\binom {m}{k}}_{s}={\binom {m}{m(s-1)-k}}_{s}$

Generating function

$\sum _{k=0}^{\infty }{\binom {m}{k}}_{s}x^{k}=\sum _{k=0}^{\infty }\sum _{\stackrel {c_{0}+c_{1}+...+c_{m-1}=k}{c_{i}\in I_{s},i\in I_{m}}}x^{k}=\sum _{c_{i}\in I_{s},i\in I_{m}}x^{c_{0}+c_{1}+...+c_{m-1}}=\,$

                            $=\sum _{c_{0}\in I_{s}}x^{c_{0}}\sum _{c_{1}\in I_{s}}x^{c_{1}}...\sum _{c_{m-1}\in I_{s}}x^{c_{m-1}}=(1+x+...+x^{s-1})^{m}\,$

Since  ${\binom {m}{k}}_{s}=0,k>m(s-1)$ definitively we get

[G] :$\sum _{k=0}^{m(s-1)}{\binom {m}{k}}_{s}x^{k}=(1+x+...+x^{s-1})^{m}\,$

Because of 

       $(1+x+...+x^{s-1})^{m}=\left({\frac {1-x^{s}}{1-x}}\right)^{m}\,$ 

for $x\neq 1$  we have. 

[G1]    $\sum _{k=0}^{m(s-1)}{\binom {m}{k}}_{s}x^{k}=\left({\frac {1-x^{s}}{1-x}}\right)^{m},x\neq {1}$

From [G] for s=2 we get binomial formula

$\sum _{k=0}^{m}{\binom {m}{k}}x^{k}=(1+x)^{m}\,$

Now using Taylor expansion we have

$(1+x)^{m}=\sum _{k=0}^{m}{\frac {m(m-1)...(m-k+1)}{k!}}x^{k}\,$

Is clear that

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

that can be rewriten as

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

This formula count the values of binomial coefficients. Can be deriveded also by induction from recurrent relation or by combinatorial methods.

Number of k-subsets of a m-set

We can find a bijection between set of compositions of natural number k into m parts over set $I_{2}\,$ and a k-subset of a m-set.

          Let be   $A_{m}=\{a_{0},a_{1},...,a_{m-1}\}\,$  a m-set denote by  $C^{k}(A_{m})\,$  the set of k-subsets of set $A_{m}\,$ 

and by  $C_{m}(k,I_{2})\,$ the set of compositions of number k into m parts over set $I_{2}\,$

Let's show that these two sets are equivalent.

Suppose that $B\in C^{k}(A_{m})\,$   then  for each   $i\in I_{m}$  we write $c_{i}=1\,$  if $a_{i}\in B$  and $c_{i}=0\,$ if $a_{i}\notin B$  

so we define the m sequence  $(c_{1},c_{2},...,c_{m})\,$  that is composition of number k into m parts  

        $(c_{0},c_{1},...,c_{m-1})\in C_{m}(k,I_{2})\,$

Contrary. If  $(c_{0},c_{1},...,c_{m-1})\in C_{m}(k,I_{2})\,$ then this composition contain k components equal to 1 we can define a

k-set $B=\{a_{i}:c_{i}=1,i\in I_{m}\}\,$ that mean $B\in C^{k}(A_{m})\,$ so from bijective principle we conclude that

            $|C^{k}(A_{m})|={\binom {m}{k}}\,$

Relation between s-nomial and binomial coefficients

From [G']   we have   

      $\sum _{k=0}^{m(s-1)}{\binom {m}{k}}_{s}x^{k}=\sum _{k=0}^{\infty }{\binom {m}{k}}_{s}x^{k}=\left({\frac {1-x^{s}}{1-x}}\right)^{m}=(1-x^{s})^{m}(1-x)^{-m}\,$

from binomial formula

       $(1-x^{s})^{m}=\sum _{i=0}^{m}(-1)^{i}{\binom {m}{i}}x^{si}$

from Taylor formula

     $(1-x)^{-m}=\sum _{j=0}^{\infty }{\binom {m+j-1}{j}}x^{j}$

now we have

      $\sum _{k=0}^{\infty }{\binom {m}{k}}_{s}x^{k}=\sum _{i=0}^{m}(-1)^{i}{\binom {m}{i}}x^{si}\sum _{j=0}^{\infty }{\binom {m+j-1}{j}}x^{j}=$

                                  $=\sum _{j=0}^{\infty }\sum _{i=0}^{m}(-1)^{i}{\binom {m}{i}}{\binom {m+j-1}{j}}x^{si+j}=$

                             

                                  $=\sum _{k=0}^{\infty }\sum _{i=0}^{m}(-1)^{i}{\binom {m}{i}}{\binom {m+k-si-1}{k-si}}x^{k}\,$

for si+j=k follow that j=k-si  then equate the coefficients next to x follow formula

[SB]   ${\binom {m}{k}}_{s}=\sum _{i=0}^{m}(-1)^{i}{\binom {m}{i}}{\binom {m+k-si-1}{m-1}}\,$

Vandermonde's identity of order s

From

$\sum _{k=0}^{\infty }{\binom {m+n}{k}}_{s}x^{k}=(1+x+...+x^{s-1})^{m+n}=(1+x+...+x^{s-1})^{m}(1+x+...+x^{s-1})^{n}=\,$

$=\sum _{i=0}^{\infty }{\binom {m}{i}}_{s}x^{i}\sum _{j=0}^{\infty }{\binom {n}{k}}_{s}x^{j}=\sum _{i+j=0}^{\infty }{\binom {m}{i}}_{s}{\binom {n}{j}}_{s}x^{i+j}=\,$

$=\sum _{k=0}^{\infty }\sum _{i+j=k}{\binom {m}{i}}_{s}{\binom {n}{j}}_{s}x^{k}=\sum _{k=0}^{\infty }\sum _{i=0}^{k}{\binom {m}{i}}_{s}{\binom {n}{k-i}}_{s}x^{k}\,$

follow Vandermonde's identity of order s

${\binom {m+n}{k}}_{s}=\sum _{i=0}^{k}{\binom {m}{i}}_{s}{\binom {n}{k-i}}_{s}\,$

This identity for s=2 is usual Vandermonde's identity see [1]

From Vandermonde identity for m=n and k=m(s-1) considering theorem of symmetry we get formula

[V]:$\sum _{i=0}^{m(s-1)}\left({\binom {m}{i}}_{s}\right)^{2}=\sum _{i=0}^{m(s-1)}{\binom {m}{i}}_{s}^{2}={\binom {2m}{m(s-1)}}_{s}\,$

that gives the sum of squares of numbers of compositions of natural numbers into m parts over set $I_{s}\,$

Compositions of natural numbers into m parts over I_s

Denote by

$c_{m}(I_{s})=\sum _{k=0}^{m(s-1)}{\binom {m}{k}}_{s}\,$

the number of compositions of natural numbers in m parts over I_s

If in [G] we put x = 1 that give

[S1]     $c_{m}(I_{s})=s^{m}\,$

a simple formula that count the number of compositions of natural numbers over Is, is clear that

$\sum _{k=0}^{m(s-1)}{\binom {m}{k}}_{s}=\sum _{k\geq 0}{\binom {m}{2k}}_{s}+\sum _{k\geq 0}{\binom {m}{2k+1}}_{s}\,$

$\sum _{k=0}^{m(s-1)}(-1)^{k}{\binom {m}{k}}_{s}=\sum _{k\geq 0}{\binom {m}{2k}}_{s}-\sum _{k\geq 0}{\binom {m}{2k+1}}_{s}\,$

Denote by

$c_{m,E}(I_{s})=\sum _{k=0}^{m(s-1)}{\binom {m}{2k}}_{s}\,$

the number of compositions of even natural numbers over $I_{s}\,$

and by

$c_{m,O}(I_{s})=\sum _{k=0}^{m(s-1)}{\binom {m}{2k+1}}_{s}\,$

the number of compositions of odd natural numbers over $I_{s}\,$ from definition follow that for m=0

$c_{0,E}(I_{s})=\sum _{k=0}^{0}{\binom {0}{2k}}_{s}={\binom {0}{0}}_{s}=1\,$

$c_{0,O}(I_{s})=\sum _{k=0}^{0}{\binom {0}{2k+1}}_{s}={\binom {0}{1}}_{s}=0\,$

Suppose that in [G1] m=0,s-odd and x=-1 then we get indefinite form 0^0 in other hand this formula
for m>0,x=-1 since expression (1-(-1)^s)/2 is 0 for s-even and 1 for s-odd expression ((1-(-1)^s)/2)^m

do not deppend on m for m>0 and is eqqual at (1-(-1)^s)/2 that mean for m>0 is valid

[S2]  :$\sum _{k=0}^{m(s-1)}(-1)^{k}{\binom {m}{k}}_{s}={\frac {1-(-1)^{s}}{2}}\,$

Suppose that m>0 then from [S1] and [S2] we get the system

$c_{m,E}(I_{s})+c_{m,O}(I_{s})=s^{m}\,$

$c_{m,E}(I_{s})-c_{m,O}(I_{s})={\frac {1-(-1)^{s}}{2}}\,$

solutions are

       $c_{m,E}(I_{s})={\frac {1}{2}}\left(s^{m}+{\frac {1-(-1)^{s}}{2}}\right)\,$

       $c_{m,O}(I_{s})={\frac {1}{2}}\left(s^{m}-{\frac {1-(-1)^{s}}{2}}\right)\,$

Finally  if we use ceiling and floor functions since for m=0,s>1 we have

          $c_{0,E}(I_{s})={\Bigg \lceil }{\frac {1}{2}}\left(s^{0}+{\frac {1-(-1)^{s}}{2}}\right){\Bigg \rceil }=1\,$          

          $c_{0,O}(I_{s})={\Bigg \lfloor }{\frac {1}{2}}\left(s^{0}-{\frac {1-(-1)^{s}}{2}}\right){\Bigg \rfloor }=0\,$

and for m>0,s>1

        $c_{m,E}(I_{s})={\Bigg \lceil }{\frac {1}{2}}\left(s^{m}+{\frac {1-(-1)^{s}}{2}}\right){\Bigg \rceil }={\frac {1}{2}}\left(s^{m}+{\frac {1-(-1)^{s}}{2}}\right)\,$

        $c_{m,O}(I_{s})={\Bigg \lfloor }{\frac {1}{2}}\left(s^{m}-{\frac {1-(-1)^{s}}{2}}\right){\Bigg \rfloor }={\frac {1}{2}}\left(s^{m}-{\frac {1-(-1)^{s}}{2}}\right)\,$

for m>=0, s>1 we get following compact formulas

[E]        $c_{m,E}(I_{s})={\Bigg \lceil }{\frac {1}{2}}\left(s^{m}+{\frac {1-(-1)^{s}}{2}}\right){\Bigg \rceil }\,$

[O]        $c_{m,O}(I_{s})={\Bigg \lfloor }{\frac {1}{2}}\left(s^{m}-{\frac {1-(-1)^{s}}{2}}\right){\Bigg \rfloor }\,$

First formula gives the number of compositions of even natural numbers into m parts over set Is and second

formula gives  the number of compositions of odd natural numbers into m parts over set Is.

Compositions of even natural numbers in m parts no greater than s

Denote by

$E_{m}(s)=c_{m,E}(I_{s+1}),s\geq 0\,$

the number of compositions of even natural numbers into m parts no greater than s. From [E] for m,s>=0 we get

$E_{m}(s)={\Bigg \lceil }{\frac {1}{2}}\left((s+1)^{m}+{\frac {1+(-1)^{s}}{2}}\right){\Bigg \rceil }\,$

Using this formula now we can construct a table by rows m,m>=0 and columns s,s>=0 in common cell of row m

and column s of table we place the number of compositions of even natural numbers into m parts over set Is.

Mathematica code:TableForm[Table[Ceiling[1/2*((k+1)^n+(1+(-1)^k)/2)],{n,0,9},{k,0,9}]]

m\s	0	1	2	3	4	5	6	7	8	9	..
0	1	1	1	1	1	1	1	1	1	1		A000012
1	1	1	2	2	3	3	4	4	5	5		A004526
2	1	2	5	8	13	18	25	32	41	50	.	A000982
3	1	4	14	32	63	108	172	256	365	500		A036486
4	1	8	41	128	313	648	1201	2048	3281	5000		A171714
5	1	16	122	512	1563	3888	8404	16384	29525	50000		A191484
6	1	32	365	2048	7813	23328	58825	131072	265721	500000		A191489
7	1	64	1094	8192	39063	139968	411772	1048576	2391485	5000000		A191494
8	1	128	3281	32768	195313	839808	2882401	8388608	21523361	50000000		A191495
9	1	256	9842	131072	976563	5038848	20176804	67108864	193710245	500000000		A191496
...	...	...	...	...	...	...	...	...	...	...	...
...	A000012	A000079	A007051	A004171	A034478	A081341	A034494	A092811	A083884	A093143	..	A191687

From table we can see that in common cell of of row m and column s is placed number ... that
means exists ... compositions of even natural numbers in m parts each part no greater than s and they are

14 compositions of even natural numbers in 3 parts each part no greater than 2 and they are

$(0,0,0)\,$

$(0,1,1),(1,0,1),(1,1,0),0,0,2),(0,2,0),(2,0,0)\,$

$(0,2,2),(2,0,2),(2,2,0),(1,1,2),(1,2,1),(2,1,1)\,$

$(2,2,2)\,$

13 compositions of even natural numbers in 2 parts each part no greater than 4 and they are

$(0,0)\,$

$(0,2),(2,0),(1,1)\,$

$(0,4),(4,0),(1,3),(3,1),(2,2)\,$

$(2,4),(4,2),(3,3)\,$

$(4,4)\,$

25 compositions of even natural numbers in 2 parts each part no greater than 6 and they are

$(0,0)\,$

$(0,2),(2,0),(1,1)\,$

$(0,4),(4,0),(1,3),(3,1),(2,2)\,$

$(0,6),(6,0),(1,5),(5,1),(2,4),(4,2),(3,3)\,$

$(2,6),(6,2),(3,5),(5,3),(4,4)\,$

$(4,6),(6,4),(5,5)\,$

$(6,6)\,$

Compositions of odd natural numbers in m parts no greater than s

Denote by

$O_{m}(s)=c_{m,O}(I_{s+1}),s\geq 0\,$

the number of compositions of even natural numbers in m parts no greater than s, then from [E] for m,s>=0 we get

$O_{m}(s)={\Bigg \lfloor }{\frac {1}{2}}\left((s+1)^{m}-{\frac {1+(-1)^{s}}{2}}\right){\Bigg \rfloor }\,$

Using this formula now we can construct a table by rows m,m>=0 and columns s,s>=0 in common cell of row m

and column s of table we place the number of compositions of odd natural numbers into m parts over set Is.

Mathematica code: TableForm[Table[Floor[1/2*((k+1)^n-(1+(-1)^k)/2)],{n,0,9},{k,0,9}]]

m\s	0	1	2	3	4	5	6	7	8	9	..
0	0	0	0	0	0	0	0	0	0	0		A000004
1	0	1	1	2	2	3	3	4	4	5		A004526
2	0	2	4	8	12	18	24	32	40	50	.	A007590
3	0	4	13	32	62	108	171	256	364	500		A036487
4	0	8	40	128	312	648	1200	2048	3280	5000		A191903
5	0	16	121	512	1562	3888	8403	16384	29524	50000		A191902
6	0	32	364	2048	7812	23328	58824	131072	265720	500000		A191901
7	0	64	1093	8192	39062	139968	411771	1048576	2391484	5000000		A191900
8	0	128	3280	32768	195312	839808	2882400	8388608	21523360	50000000		A191899
9	0	256	9841	131072	976562	5038848	20176803	67108864	193710244	500000000		A191680
...	...	...	...	...	...	...	...	...	...	...	...
...	A000004	A000079	A003462	A004171	A128531	A081341	A191680	A092811	A191681	A093143	..	A192396

From table we can read that there exists:

13 compositions of odd natural numbers in 3 parts each part no greater than 2 and they are

$(0,0,1),(0,1,0),(1,0,0)\,$

$(1,1,1),(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0)\,$

$(1,2,2),(2,1,2),(2,2,1)\,$

12 compositions of odd natural numbers in 2 parts each part no greater than 4 and they are

$(0,1),(1,0)\,$

$(0,3),(3,0),(1,2),(2,1)\,$

$(1,4),(4,1),(2,3),(3,2)\,$

$(3,4),(4,3)\,$

24 compositions of odd natural numbers in 2 parts each part no greater than 6 and they are

$(0,1),(1,0)\,$

$(0,3),(3,0),(1,2),(2,1)\,$

$(0,5),(5,0),(1,4),(4,1),(2,3),(3,2)\,$

$(1,6),(6,1),(2,5),(5,2),(3,4),(4,3)\,$

$(3,6),(6,3),(4,5),(5,4)\,$

$(5,6),(6,5)\,$

Remarks

Symbol ${\binom {m}{k}}_{s}\,$ do not confuse with Gaussian binomial coefficient

References

1. B. A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8. English translation published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993.
2. V. N. Sachkov, Probablistic Methods in Combinatorial Analysis, Cambridge, 1997.
3. Adi Dani, Quasicompositions of natural numbers, Proceedings of III congress of mathematicians of Macedonia, Struga Macedonia 29 IX -2 X 2005 pages 225-238