This site is supported by donations to The OEIS Foundation.

# Compositions of natural numbers over arithmetic progressions

KEYWORDS: Compositions of natural numbers.
Concerned with sequences:  A131577, A000045, A078012, A003269, A017899, A017900, A191818, A191819, A191820

## Overview

Denote by

${\displaystyle 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

${\displaystyle A_{1}^{0}=N,N-\{0\}=N_{+}\,}$
${\displaystyle A_{2}^{0}=E,E-\{0\}=E_{+}\,}$
${\displaystyle A_{2}^{1}=O\,}$
${\displaystyle A_{3}^{0}=\{0,3,6,...\}\,}$
${\displaystyle A_{3}^{1}=\{1,4,7,...\}}$
${\displaystyle A_{3}^{2}=\{2,5,8,...\}\,}$

Each m-sequence of natural numbers that fulfill the conditions.

${\displaystyle c_{0}+c_{1}+...+c_{m-1}=k\,}$, ${\displaystyle c_{i}\in A_{s}^{p},i\in I_{m}\,}$

is called composition of natural number k in m parts over set ${\displaystyle A_{s}^{p}\,}$ . Denote by

${\displaystyle 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 ${\displaystyle A_{s}^{p}\,}$  and by

${\displaystyle 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 ${\displaystyle A_{s}^{p}\,}$

## generating function

${\displaystyle \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}}=\,}$

${\displaystyle =\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}}=\,}$

${\displaystyle =\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

${\displaystyle \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}=\,}$

${\displaystyle =\sum _{i=0}^{\infty }{\binom {m+i-1}{i}}x^{pm+si}}$

if now substitute ${\displaystyle pm+si=k\,}$  thent  ${\displaystyle i=(k-pm)/s\,}$  taking in account that ${\displaystyle i\in N\,}$ follow

that ${\displaystyle k\in \{pm,pm+s,pm+2s,...\},}$

${\displaystyle \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

${\displaystyle \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 ${\displaystyle A_{s}^{p}\,}$

${\displaystyle 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

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

Denote by

${\displaystyle 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 ${\displaystyle A_{s}^{p}\,}$

### p=0

from last formula for p=0 we get that

${\displaystyle 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 ${\displaystyle A_{s}^{0}-\{0\}\,}$ is finite
from generating function we get

${\displaystyle \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}}=\,}$

${\displaystyle =\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}}=\,}$

${\displaystyle =\left(\sum _{i=1}^{\infty }x^{si}\right)^{m}=\left({\frac {x^{s}}{1-x^{s}}}\right)^{m}\,}$

From binomial theorem now we have

${\displaystyle \left({\frac {x^{s}}{1-x^{s}}}\right)^{m}=\sum _{i=0}^{\infty }{\binom {m+i-1}{i}}x^{sm+si}\,}$

writing ${\displaystyle sm+si=k\,}$ follow that ${\displaystyle i={\frac {k-sm}{s}}\,}$ finally we get

${\displaystyle c_{m}(k,A_{s}^{0}-\{0\})={\binom {m+(k-sm)/s-1}{(k-sm)/s}}\,}$

from last formula for s=1 we get

${\displaystyle c_{m}(k,A_{1}^{0}-\{0\})=c_{m}(k,N-\{0\})={\binom {k-1}{k-m}}\,}$

Denote by ${\displaystyle N-\{0\})=N_{+})\,}$ the set of positive natural numbers then we have

${\displaystyle 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 ${\displaystyle c(0,N_{+})=0\,}$
for k>0 we have

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

finally we have

${\displaystyle 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

${\displaystyle c_{m}(k,A_{2}^{0}-\{0\})={\binom {m+(k-2m)/2-1}{(k-2m)/2}}\,}$

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

### p=1

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

${\displaystyle 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

${\displaystyle c(k,A_{s}^{1})=\sum _{i\in N}{\binom {(k-si)+i-1}{(k-si)-1}}\,}$

taking in account that ${\displaystyle k-si-1\geq 0\,}$ follow that ${\displaystyle 0\leq i\leq \lfloor {\frac {k-1}{s}}\rfloor \,}$ definitly we get that

${\displaystyle 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 ${\displaystyle 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