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
![{\displaystyle c_{0}+c_{1}+...+c_{m-1}=k,c_{i}\in I_{s},i\in I_{m},s>0\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/807206540d3e4c8f632a6018d89168841c35868d)
is called composition of natural number k in m parts over set Is. Denote by
![{\displaystyle 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}\}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/52d7acd9b7d9c10aad48a9bdb989459f0cadbae9)
the set of compositions of natural number k into m parts over set Is and by
![{\displaystyle 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\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/6b32a3b93a81e624194b0d667a67fdee99b05a36)
number of compositions of natural number k in m parts over set Is.
The number
![{\displaystyle {\binom {m}{k}}_{s}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/37542ced8eb1af39063ea18dddf9f20efea961cc)
is called s-nomial coefficient s>0. For s=2 we get binomial coefficients and in that case we write
![{\displaystyle {\binom {m}{k}}_{2}={\binom {m}{k}}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/61a2832e1842a740282cc322d629d053d41eca86)
these numbers play central role in combinatorics.
There appears parameters m,k, both
natural numbers, from definition follow that for m>0
![{\displaystyle {\binom {m}{k}}_{s}=0,k\notin I_{m(s-1)+1}=\{0,1,2,...,m(s-1)\}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/a4322ac968bc7d3a90334ee507eddb31a4691493)
with boundary values
![{\displaystyle {\binom {m}{0}}_{s}={\binom {m}{m(s-1)}}_{s}=1\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/d2d768d88426bad7267ab06fe1be46762b63688d)
we extend the case and for m=0 use
![{\displaystyle {\binom {0}{k}}_{s}=0,k>0,{\binom {0}{0}}_{s}=1\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/614202d956efa6649ffe451d6291a3bf5ca67fb1)
Recurrent relation
From definition follow that
![{\displaystyle {\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=\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/48baf90aaca5ec7d8ef9ae41539893c488b64d59)
-
![{\displaystyle =\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}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/255add549ece48ab1a3910cf72f17f798d1453b6)
in this way we get recurrence
- [R]
![{\displaystyle {\binom {m}{k}}_{s}=\sum _{i=0}^{s-1}{\binom {m-1}{k-i}}_{s}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/1c0f0694ddf9f32630ef313c1ac1dd799f0dede9)
Theorem of symmetry
Suppose that
then from definition follow that
![{\displaystyle c_{0}+c_{1}+...+c_{m-1}=k,c_{i}\in I_{s},i\in I_{m}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/5c985cfd95779c6ba9e6f7aa8319e34d6acf61b7)
then composition
because
and
for each
Conversely
suppose that
then from definition follow that
![{\displaystyle c_{0}+c_{1}+...+c_{m-1}=m(s-1)-k,c_{i}\in I_{s},i\in I_{m}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/1324decfd4575955325777b1779ef4ed3aafbf8e)
then composition
because
and
for each
that mean
finally we get the theorem of symmetry
Generating function
![{\displaystyle \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}}=\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/3db442221a84f2791af326464d3adfa7521a69b9)
-
![{\displaystyle =\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}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/6df9cd449544150eab74a22cbe41ad2eeaad663d)
Since
definitively we get
[G] :
Because of
for
we have.
[G1]
From [G] for s=2 we get binomial formula
![{\displaystyle \sum _{k=0}^{m}{\binom {m}{k}}x^{k}=(1+x)^{m}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/b3fc764f39d00a7af3dd21b667f55a1988659f26)
Now using Taylor expansion we have
![{\displaystyle (1+x)^{m}=\sum _{k=0}^{m}{\frac {m(m-1)...(m-k+1)}{k!}}x^{k}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/fad67a8020795272d4bbad61b52e9d2a8685f10f)
Is clear that
![{\displaystyle {\binom {m}{k}}={\frac {m(m-1)...(m-k+1)}{k!}}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/3dc6d8c0d32f848f4cd6d504546d4a71cedb57ac)
that can be rewriten as
![{\displaystyle {\binom {m}{k}}={\frac {m!}{k!(m-k)!}}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/6763b7c3db59a7d450ac4a86ac7221df4cc06509)
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
![{\displaystyle \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}=\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/09d99f360767accd7df7874d7af292796149a70c)
![{\displaystyle =\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}=\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/34d345090022218f41f7b30d754a472797ab9f53)
![{\displaystyle =\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}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/f5c47b1cf591bf20ae2961f329476d1575d7e152)
follow Vandermonde's identity of order s
![{\displaystyle {\binom {m+n}{k}}_{s}=\sum _{i=0}^{k}{\binom {m}{i}}_{s}{\binom {n}{k-i}}_{s}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/c4cf614e3a454f9d09ab5a87a602cd316db804c4)
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
![{\displaystyle c_{m}(I_{s})=\sum _{k=0}^{m(s-1)}{\binom {m}{k}}_{s}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/94596207b24fb3e04f5e220f2d8933d85491b8f0)
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
![{\displaystyle \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}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/83aa1ff02714b57ac520f3f3785f48e1f69fb2aa)
![{\displaystyle \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}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/f62770c42c263d3e90c7ff995e1aaa2c2023a545)
Denote by
![{\displaystyle c_{m,E}(I_{s})=\sum _{k=0}^{m(s-1)}{\binom {m}{2k}}_{s}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/16fd67c5298092cc5fc220a6009da39e86fa5515)
the number of compositions of even natural numbers over
and by
![{\displaystyle c_{m,O}(I_{s})=\sum _{k=0}^{m(s-1)}{\binom {m}{2k+1}}_{s}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/d05e48e6d87e7052a7c0096f7220c4e115fdea94)
the number of compositions of odd natural numbers over
from definition follow that for m=0
![{\displaystyle c_{0,E}(I_{s})=\sum _{k=0}^{0}{\binom {0}{2k}}_{s}={\binom {0}{0}}_{s}=1\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/090382fe019bbc209460b3a4a098c10f6b4f6495)
![{\displaystyle c_{0,O}(I_{s})=\sum _{k=0}^{0}{\binom {0}{2k+1}}_{s}={\binom {0}{1}}_{s}=0\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/d18fe3cefbdbd3007ce4eff31bac3da15cf554bc)
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
![{\displaystyle c_{m,E}(I_{s})-c_{m,O}(I_{s})={\frac {1-(-1)^{s}}{2}}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/17f06bc9c1c0df045cfa92607321dd45cc3891de)
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
![{\displaystyle E_{m}(s)=c_{m,E}(I_{s+1}),s\geq 0\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/a64ac2ca52840dbf0f6498689fe91e62e96094d3)
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
![{\displaystyle (2,2,2)\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/b4439565811d4d3bbab0359ae45cb891945bdd0c)
13 compositions of even natural numbers in 2 parts each part no greater than 4 and they are
![{\displaystyle (4,4)\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/ed86cc2a83bff461d5c093d46fbab7785db68c8f)
25 compositions of even natural numbers in 2 parts each part no greater than 6 and they are
![{\displaystyle (6,6)\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/651f00d6182f66df047c555a1c166bc638723ea4)
Compositions of odd natural numbers in m parts no greater than s
Denote by
![{\displaystyle O_{m}(s)=c_{m,O}(I_{s+1}),s\geq 0\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/057229d7ef5f582ebeb36afc83ecc71f938be5c5)
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
![{\displaystyle (5,6),(6,5)\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/53cdb78956a306a1034f95e8822d802c71ad4592)
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