This site is supported by donations to The OEIS Foundation.

User:Adi Dani/Compositions of natural numbers over arithmetic progressions

From OeisWiki
Jump to: navigation, search

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


 
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A_{3}^{1}=\{1,4,7,...\}}

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A_{s}^{p}\,}

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle sm+si=k\,} 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  Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (k-mp)/s=i\in N\, } 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