This site is supported by donations to The OEIS Foundation.
User:Adi Dani /Restricted compositions of natural numbers
From OeisWiki
Restricted compositions of natural numbers
Adi Dani, MayJune 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 the set of all natural numbers lesser than given natural number m (0 is included
in set of natural numbers N).
 Each msequence 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 I_{s}. The number
is called snomial 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 ksubsets of a mset
We can find a bijection between set of compositions of natural number k into m parts over set and a ksubset of a mset.
Let be a mset denote by the set of ksubsets 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
kset that mean so from bijective principle we conclude that
Relation between snomial and binomial coefficients
From [G'] we have
from binomial formula
from Taylor formula
now we have
for si+j=k follow that j=ksi 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(s1) 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 I_{s}
Denote by
the number of compositions of natural numbers in m parts over I_{s}
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,sodd 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 seven and 1 for sodd 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
 B. A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5648007388. English translation published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993.
 V. N. Sachkov, Probablistic Methods in Combinatorial Analysis, Cambridge, 1997.
 Adi Dani, Quasicompositions of natural numbers, Proceedings of III congress of mathematicians of Macedonia, Struga Macedonia 29 IX 2 X 2005 pages 225238