composition (number theory)

In mathematics, a composition of a positive integer n is a way of writing n as a sum of positive integers. Two sums which differ in the order of their summands are considered to be different compositions, while they would be considered to be the same partition.

Examples

The sixteen compositions of 5 are:

5
4+1
3+2
3+1+1
2+3
2+2+1
2+1+2
2+1+1+1
1+4
1+3+1
1+2+2
1+2+1+1
1+1+3
1+1+2+1
1+1+1+2
1+1+1+1+1.

Compare this with the seven partitions of 5:

5
4+1
3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1.

It is possible to put constraints on the parts of the compositions. For example the five compositions of 5 into distinct terms are:

5
4+1
3+2
2+3
1+4.

Compare this with the three partitions of 5 into distinct terms:

5
4+1
3+2.

Number of compositions

There are 2^n-1 compostitions of n; conventionally there is one composition of 0, and no compositions of negative integers. The number of compositions of n into exactly k parts is

{(n-1)! \over (k-1)!(n-k)!}

i.e. the combination "n-1 choose k-1".

External links

* Partition and composition calculator

<< Previous

Word Browser

Next >>

jeordie white
thomas burke
lusoga language
lock haven
acta diurna
siege of la rochelle
kerry burke
vian les bains
jean claude romand
ivo of kermartin
clara westhoff

commodification
prime geodesic
f8f bearcat
autistic spectrum
werner roth
villeneuve d'ascq
multisystem developmental disorder
basel dove
stade olympique
brian blessed
graydon creed

anastacia (singer)
aulus atilius caiatinus
volvo 160
b,c,k,w system
betty eadie
desnica radivojevic
punjabi cuisine
sawgrass
durant (automobile)
robert gascoyne cecil, 7th marquess of salisbury
shimla

hiccup
bundling (tradition)
xtort
wild arms
water law
ambrosius
franco alfano
national australia bank
richard abegg
bardot
sudanese air force