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}]]
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}]]
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
-
-
-
-
-
Symbol do not confuse with Gaussian binomial coefficient
References
- 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.
- 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 225-238