This site is supported by donations to The OEIS Foundation.

User:Adi Dani /Restricted compositions of natural numbers

From OeisWiki

Jump to: navigation, search

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

Contents

Compositions of natural number k into m parts over set Is

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 Is. 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\ne 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\ne {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 Is

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 Is

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\ge 0}{\binom{m}{2k}}_{s}+\sum_{k\ge 0}{\binom{m}{2k+1}}_{s}\,


\sum_{k=0}^{m(s-1)}(-1)^{k}{\binom{m}{k}}_{s}=\sum_{k\ge 0}{\binom{m}{2k}}_{s}-\sum_{k\ge 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.

Generalized Fibonacci sequence

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

Denote by


E_{m}(s)=c_{m,E}(I_{s+1}),s\ge 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\ge 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
Personal tools