Composition

Author

Eric W. Weisstein
June 26, 2023

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Combinatorics/Composition.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Composition.html.

©2023 Wolfram Research, Inc. except for portions noted otherwise

Example

AllCompositions[n_Integer?Positive]:=Flatten[Permutations/@Partitions[n],1]

AllCompositions[4]

Standard compositions

A066099

StandardComposition[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse

Table[StandardComposition[n],{n,0,10}]

The number of compositions of  into  parts (where 0 is not allowed as a part) is given by Binomial[n - 1, k - 1]

Sum[Binomial[n-1,k-1],{k,n}]

Sum[(2^(k-1)),{k,n}]

AllCompositions[4]

Table[StandardComposition[n],{n,(2^3),(2^4)-1}]

pos={#,#2-1}&@@@Partition[Table[(2^(n-1)),{n,5}],2,1]

TextGrid[Take[std,#]&/@pos,Dividers->{{True,{False},True},All}]

std=Table[StandardComposition[n],{n,31}]

Length[std]

Flatten[Table[Reverse@LexicographicSort@Flatten[Permutations/@Partitions[n],1],{n,5}],1]

Length[data=Import["https://oeis.org/A066099/b066099.txt","Table"][[All,2]]]

Length[data2=Flatten[Table[Reverse@LexicographicSort@Flatten[Permutations/@Partitions[n],1],{n,10}]]]

data===data2

Table[FactorInteger[Times@@Prime/@Accumulate@IntegerDigits[n,2]][[All,-1]],{n,41}]

Counts

Table[2^(n-1),{n,6}]

Length/@AllCompositions/@Range[6]

k-Compositions

<<Combinatorica`

NumberOfCompositions[n,k]

Table[Compositions[4,k],{k,4}]