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

Compositions of natural number k into m parts over set Is

Definition

Denote by  the set of all natural numbers lesser than given natural number m (0 is included

in set of natural numbers N).


Each m-sequence   of natural numbers that fulfill the condition



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



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



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



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


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

natural numbers, from definition follow that for m>0



with boundary values



we extend the case and for m=0 use 


Recurrent relation

From definition follow that


             

in this way we get recurrence


[R]      

Theorem of symmetry


Suppose that  then from definition follow that



then composition


      


because


        


and    for each


Conversely

suppose that  then from definition follow that



then composition


    


because


      


and for each


that mean 


       


finally we get the theorem of symmetry


      

Generating function

                            


Since  definitively we get


[G] :


Because of 


        


for   we have. 


[G1]    


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



Now using Taylor expansion we have



Is clear that



that can be rewriten as



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 and a k-subset of a m-set.

          Let be     a m-set denote by    the set of k-subsets of set  

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

Let's show that these two sets are equivalent.

Suppose that   then  for each     we write   if  and if  

so we define the m sequence    that is composition of number k into m parts  


        


Contrary. If  then this composition contain k components equal to 1 we can define a

k-set  that mean  so from bijective principle we conclude that


            

Relation between s-nomial and binomial coefficients

From [G']   we have   


      


from binomial formula


       


from Taylor formula


     


now we have


      


                                  

                             

                                  



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


[SB]  


Vandermonde's identity of order s

From




follow Vandermonde's identity of order 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]:


that gives the sum of squares of numbers of compositions of natural numbers into m parts over set

Compositions of natural numbers into m parts over Is

Denote by


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

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


[S1]     


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




Denote by



the number of compositions of even natural numbers over


and by


the number of compositions of odd natural numbers over  from definition follow that for m=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]  :


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



solutions are


       

       


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


                    

          


and for m>0,s>1


        

        


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


[E]        

[O]        


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



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



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

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

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

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

Denote by



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



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

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

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

Remarks

Symbol 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