This page is under construction!
Compositions of natural numbers over arithmetic progressions
Adi Dani, june 2011
KEYWORDS: Compositions of natural numbers.
Concerned with sequences: A131577, A000045, A078012, A003269, A017899, A017900, A191818, A191819, A191820
Overview
Denote by
the set of natural numbers thats divided by s gives residue p, or the set of terms of
an arithmetic progression
with first term p and difference s. Examples
-
Each m-sequence of natural numbers that fulfill the conditions.
- ,
is called composition of natural number k in m parts over set . Denote by
;
the set of compositions of natural number k in m parts over set and by
number of compositions of natural number k in m parts over set
generating function
now from binomial formula we get
if now substitute thent taking in account that follow
that
thats means
from last identity after equalizing the coefficients next to same powers of x we get the formula for counting
the number of compositions of natural number k over set
Examples
Denote by
the number of all compositions of k into parts over
p=0
from last formula for p=0 we get that
because 0 appear as part of compositions of k number m of parts goes to infinite
But number of compositions of number k over set is finite
from generating function we get
From binomial theorem now we have
-
writing follow that finally we get
from last formula for s=1 we get
Denote by the set of positive natural numbers then we have
for number of compositions of natural number k into positive parts is clear that
for k>0 we have
finally we have
formula for number of compositions of natural number k into positive parts thats gives the sequence A131577
for s=2 we get
- if otherwise is 0
p=1
If then from follow that or
from last formula for p=1 we have
taking in account that follow that definitly we get that
formula count the number of compositions of number k in parts over
from this formula for s=2 we get the number of compositions of number k into odd parts.
These numbers give the sequence A000045 or Fibonacci sequence, for s=3 we get the
sequence A078012,for s=4 we get the sequence A003269, for s=5 we have sequence
A017899
for s=6 the sequence
A017900 next sequence
A191818 for s=7, s=8
A191819,
and for s=9 we get
A191820, etc