This site is supported by donations to The OEIS Foundation.

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

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

$A_{s}^{p}=\{x:x=si+p,i\in N,p\in I_{s}\}\,$ 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

$A_{1}^{0}=N,N-\{0\}=N_{+}\,$ $A_{2}^{0}=E,E-\{0\}=E_{+}\,$ $A_{2}^{1}=O\,$ $A_{3}^{0}=\{0,3,6,...\}\,$ $A_{3}^{1}=\{1,4,7,...\}$ $A_{3}^{2}=\{2,5,8,...\}\,$ Each m-sequence of natural numbers that fulfill the conditions.

$c_{0}+c_{1}+...+c_{m-1}=k\,$ , $c_{i}\in A_{s}^{p},i\in I_{m}\,$ is called composition of natural number k in m parts over set $A_{s}^{p}\,$ . Denote by

$C_{m}(k,A_{s}^{p})=\{(c_{0},c_{1},...,c_{m-1}):c_{0}+c_{1}+...+c_{m-1}=k,c_{i}\in A_{s}^{p},i\in I_{m}\}\,$ ;

the set of compositions of natural number k in m parts over set $A_{s}^{p}\,$ and by

$c_{m}(k,A_{s}^{p})=\sum _{\stackrel {c_{0}+c_{1}+...+c_{m-1}=k}{c_{i}\in A_{s}^{p},i\in I_{m}}}1\,$ number of compositions of natural number k in m parts over set $A_{s}^{p}\,$ ## generating function

$\sum _{k=0}^{\infty }c_{m}(k,A_{s}^{p})x^{k}=\sum _{k=0}^{\infty }\sum _{\stackrel {c_{0}+c_{1}+...+c_{m-1}=k}{c_{i}\in A_{s}^{p},i\in I_{m}}}x^{k}=\sum _{c_{i}\in A_{s}^{p},i\in I_{m}}x^{c_{0}+c_{1}+...+c_{m-1}}=\,$ $=\sum _{c_{0}\in A_{s}^{p}}x^{c_{0}}\sum _{c_{1}\in A_{s}^{p}}x^{c_{1}}...\sum _{c_{m-1}\in A_{s}^{p}}x^{c_{m-1}}=\,$ $=\left(\sum _{i=0}^{\infty }x^{si+p}\right)^{m}=\left({\frac {x^{p}}{1-x^{s}}}\right)^{m}\,$ now from binomial formula we get

$\left({\frac {x^{p}}{1-x^{s}}}\right)^{m}=x^{pm}(1-x^{s})^{-m}=x^{pm}\sum _{i=0}^{\infty }{\binom {-m}{i}}(-x^{s})^{i}=\,$ $=\sum _{i=0}^{\infty }{\binom {m+i-1}{i}}x^{pm+si}$ if now substitute $pm+si=k\,$ thent  $i=(k-pm)/s\,$ taking in account that $i\in N\,$ follow

that $k\in \{pm,pm+s,pm+2s,...\},$ $\sum _{i=0}^{\infty }{\binom {m+i-1}{i}}x^{pm+si}=\sum _{k=0}^{\infty }{\binom {m+(k-pm)/s-1}{m-1}}x^{k}$ thats means

$\sum _{k=0}^{\infty }c_{m}(k,A_{s}^{p})x^{k}=\sum _{k=0}^{\infty }{\binom {m+(k-pm)/s-1}{m-1}}x^{k}$ 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 $A_{s}^{p}\,$ $c_{m}(k,A_{s}^{p})={\begin{cases}{\binom {m+(k-pm)/s-1}{m-1}},&{\mbox{if }}(k-pm)/s\in N,\\0,&{\mbox{if }}(k-pm)/s\notin N\end{cases}}$ Examples

$c_{m}(k,N)=c_{m}(2k,E)={\binom {m+k-1}{m-1}}$ Denote by

$c(k,A_{s}^{p})=\sum _{m=0}^{\infty }{\binom {m+(k-pm)/s-1}{m-1}}\,$ the number of all compositions of k into parts over $A_{s}^{p}\,$ ### p=0

from last formula for p=0 we get that

$c(k,A_{s}^{0})=\infty \,$ 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 $A_{s}^{0}-\{0\}\,$ is finite
from generating function we get

$\sum _{k=0}^{\infty }c_{m}(k,A_{s}^{0}-\{0\})x^{k}=\sum _{c_{i}\in A_{s}^{0}-\{0\},i\in I_{m}}x^{c_{0}+c_{1}+...+c_{m-1}}=\,$ $=\sum _{c_{0}\in A_{s}^{0}-\{0\}}x^{c_{0}}\sum _{c_{1}\in A_{s}^{0}-\{0\}}x^{c_{1}}...\sum _{c_{m-1}\in A_{s}^{0}-\{0\}}x^{c_{m-1}}=\,$ $=\left(\sum _{i=1}^{\infty }x^{si}\right)^{m}=\left({\frac {x^{s}}{1-x^{s}}}\right)^{m}\,$ From binomial theorem now we have

$\left({\frac {x^{s}}{1-x^{s}}}\right)^{m}=\sum _{i=0}^{\infty }{\binom {m+i-1}{i}}x^{sm+si}\,$ writing $sm+si=k\,$ follow that $i={\frac {k-sm}{s}}\,$ finally we get

$c_{m}(k,A_{s}^{0}-\{0\})={\binom {m+(k-sm)/s-1}{(k-sm)/s}}\,$ from last formula for s=1 we get

$c_{m}(k,A_{1}^{0}-\{0\})=c_{m}(k,N-\{0\})={\binom {k-1}{k-m}}\,$ Denote by $N-\{0\})=N_{+})\,$ the set of positive natural numbers then we have

$c_{m}(k,N_{+})={\binom {k-1}{k-m}}={\binom {k-1}{m-1}}\,$ for number of compositions of natural number k into positive parts is clear that $c(0,N_{+})=0\,$ for k>0 we have

$c(k,N_{+})=\sum _{m=1}^{k}{\binom {k-1}{m-1}}=2^{k-1}\,$ finally we have

$c(k,N_{+})=\lfloor 2^{k-1}\rfloor \,$ formula for number of compositions of natural number k into positive parts thats gives the sequence A131577

for s=2 we get

$c_{m}(k,A_{2}^{0}-\{0\})={\binom {m+(k-2m)/2-1}{(k-2m)/2}}\,$ $c_{m}(k,E_{+})={\binom {k/2-1}{k/2-m}}\,$ if $k\in E_{+}$ otherwise is 0

### p=1

If  $p\neq 0\,$ then from  $(k-mp)/s=i\in N\,$ follow that $m=(k-si)/p,i\in N\,$ or

$c(k,A_{s}^{p})=\sum _{i\in N}{\binom {(k-si)/p+i-1}{(k-si)/p-1}}\,$ from last formula for p=1 we have

$c(k,A_{s}^{1})=\sum _{i\in N}{\binom {(k-si)+i-1}{(k-si)-1}}\,$ taking in account that $k-si-1\geq 0\,$ follow that $0\leq i\leq \lfloor {\frac {k-1}{s}}\rfloor \,$ definitly we get that

$c(k,A_{s}^{1})=\sum _{i=0}^{\lfloor {\frac {k-1}{s}}\rfloor }{\binom {(k-(s-1)i-1}{i}}\,$ formula count the number of compositions of number k in parts over $A_{s}^{1}$ 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