Composition writing

We do casework on how many parts the composition has. If it has 1 part, there is 1 composition. If it has 2 parts, we can think as follows:

1 1 1 1 1 1 1 1

Choose one of the spaces, and insert a divider.

1 1|1 1 1 1 1 1

This corresponds to the composition 2,6. Therefore, there are $\dbinom{7}{1}=7$ compositions of 2 parts.

We can similarly calculate the number of compositions of $n$ parts as $\dbinom{7}{8-n}$ . We choose $n-1$ dividers out of the 7 spaces possible for dividers. Note that the integers have to be positive, so the calculation isn't $\dbinom{7+n-2}{n-1}$ .

Therefore, the answer is $\begin{aligned}&1\dbinom{7}{0}+2\dbinom{7}{1}+3\dbinom{7}{2}+4\dbinom{7}{3} \\+&5\dbinom{7}{4}+6\dbinom{7}{5}+7\dbinom{7}{6}+8\dbinom{7}{7}=\boxed{576}\end{aligned}$

Let $S_n$ be the set of compositions of $n$ .

Let $\vert S_n \vert$ be the number of elements of $S_n$ , and $p(n)$ be the total number of parts in $S_n$ .

Now we will present an algorithm for generating elements of $S_{n+1}$ based on elements of $S_n$ . Define two operations: $\begin{aligned} A&: \mbox{Append a }1\mbox{ to the ordered sequence} \\ B&: \mbox{Add }1\mbox{ to the last part in the ordered sequence} \end{aligned}$

Since both operations add $1$ to the sum of parts, then $s \in S_n$ implies $A(s), B(s) \in S_{n+1}$ . Further, for any $s \in S_{n+1}$ we can subtract $1$ from its last digit (discarding zeroes) to give a member of $S$ .

Therefore we have a bijection from $S_n \times \{A,B\}$ to $S_{n+1}$ .

So $\vert S_{n+1} \vert = 2 \vert S_n \vert$ .

Further, the operation $A$ adds one part to each member of $S_n$ , and the operation $B$ adds no parts. Therefore we have $p(n+1) = (p(n) + \vert S_n \vert) + p(n)$

Since $S_1 = 1$ , we get $S_n = 2^{n-1}$ , so $p(n+1) = 2p(n) + 2^{n-1}$

Solving this recurrence relation gives $p(n) = 2^{n-2}(n+1)$

Proof by induction: $p(1) = 2^{-1}(2) = 1$ which is correct, and the induction step $\begin{aligned} p(n+1) &= 2p(n) + 2^{n-1}\\ &= 2(2^{n-2}(n+1)) + 2^{n-1} \\ &= 2^{n-1}n + 2^{n-1} + 2^{n-1} \\ &= 2^{n-1}(n+2)\\ &= 2^{(n+1)-2}((n+1)+1) \end{aligned}$

The solution we want is $p(8) = 2^6 \cdot 9 = \boxed{576}$

Lemma: There are $n-1\choose k-1$ compositions of $n$ that has $k$ parts.

Proof: Note that each part is at least $1$ . We remove $1$ from each part, so we end up having to partition $n-k$ into $k$ parts. The number of ways to do this is identical to the number of ways to partition $n-k$ balls into $k$ boxes. We line up the balls, and put $k-1$ walls collinear with the balls. The walls would then divide the balls into respective boxes. We then arrange the balls and walls. There are $n-1$ items: a set of $n-k$ balls and $k-1$ walls. Hence, there are $n-1\choose k-1$ ways to arrange, thus our lemma is proved.

There are:

$7\choose0$ $=1$ ways for $1$ part $\rightarrow$ $(1)(1)=1$ part.

$7 \choose1$ $=7$ ways for $2$ parts $\rightarrow$ $(7)(2)=14$ parts.

$7 \choose 2$ $=21$ ways for $3$ parts $\rightarrow$ $(21)(3)=63$ parts.

$7 \choose 3$ $=35$ ways for $4$ parts $\rightarrow$ $(35)(4)=140$ parts.

$7 \choose 4$ $=35$ ways for $5$ parts $\rightarrow$ $(35)(5)=175$ parts.

$7 \choose 5$ $=21$ ways for $6$ parts $\rightarrow$ $(21)(6)=126$ parts.

$7 \choose 6$ $=7$ ways for $7$ parts $\rightarrow$ $(7)(7)=49$ parts.

$7 \choose 7$ $1$ way for $8$ parts $\rightarrow$ $(1)(8)=8$ parts.

Adding them together, there are $1+14+63+140+175+126+49+8=\boxed{576}$ total parts.

First, let's find the number of positive integer solutions to the equation $a_1 + a_2 + ... + a_n= 8$ , where $n$ is a positive integer $\leq 8$ . Since we are finding the number of positive integer solutions, a useful substitution would be $a_i= b_i+1$ , so $\sum \limits_{i=0}^{n} a_i = \sum \limits_{i=0}^{n} b_i + n$ The equation then reduces to $\sum \limits_{i=0}^{n} b_i= 8-n$ . According to the ball and bars method, this equation has ${(8-n+n-1) \choose 8-n} = {7 \choose 8-n}$ solutions. So we can conclude that the number of compositions of $8$ having $n$ parts is equal to ${7 \choose 8-n}$ . These ${7 \choose 8-n}$ compositions contribute $n {7 \choose 8-n}$ to our final count. Our desired answer will then be $\sum \limits_{n=1}^{8} n {7 \choose 8-n} = \boxed{576}$ This sum can be calculated manually. One can also show by induction that $\sum \limits_{n=1}^{k} n {k-1 \choose k-n} = 2^{k-2}(k+1)$ for all $k \in \mathbb{N}$ , which makes the calculation considerably easier.

Calculate the partitions of 8 then the partitions of these as multisets.

Start by defining p(n) to be the total number of parts in all compositions of n and f(n) to be the number of compositions of n.

f(n)=f(n-1)+f(n-2)+...f(1)+f(0) because we can simply subtract the first element and look at what remains. Since f(0)=1, f(n) simplifies to f(n) = 2^(n-1) for all integers n >0.

p(n) is a bit trickier, but you can still get a recurrence. p(n) equals p(n-1)+f(n-1)+p(n-2)+f(n-2)+...+p(0)+f(0). This is because the number parts in all of this is equal to the number of parts in all the ways you can get 1 plus the number of ways to get 1 (if the first part is n-1), plus the number of parts in all the ways to get 2 plus the number of ways to get 2 (if the first part is n-2), etc.

One can simply sum the f(n-1)+f(n-2)+...+f(1)+f(0) to f(n), and with a small number like 8 it is easy to do the calculations by hand.

The fact that order matters here makes the problem simpler.

Let the 8 be written as a row of 8 ones with 7 blank spots between them. $1 \_ 1\_ 1\_ 1\_ 1\_ 1\_ 1\_ 1$ .

Then the number of compositions with $k$ parts is basically the number of ways we can insert $k-1$ dividers into the distinct spots, with no spots allowed to be used twice. So the number of compositions with $k$ parts is ${ 7 \choose k-1}$

For example, the number of compositions with one part is ${ 7 \choose 0}$ , number of compositions with two parts is ${7 \choose 1}$ and so on.

The total number of parts is the given by the sum ${ 7 \choose 0} \times 1 + { 7 \choose 1} \times 2 +...+{ 7 \choose 7} \times 8$ .

While this sum is easy to do by hand, we can also evaluate using a little trick.

We can consider the sum to be the value of the power series $1+2\times {7 \choose 1} x + 3\times {7 \choose 2} x^2 +...+ 7\times {7 \choose 6} x^6 + 8 \times {7 \choose 7}x^7$ at $x=1$

You can regard this power series as the differential of $x(1+x)^7$ . Differentiating (using the chain rule) we get the differential to be $7x(1+x)^6+(1+x)^7$ . Substituting $x=1$ gives the answer $7\times 2^6 +2^7=576$

A composition with k-parts of 8 is { $x_{1}$ , $x_{2}$ , ..., $x_{k}$ }, which is satisfied: $x_{1}$ + $x_{2}$ + ...+ $x_{k}$ = 8 This equation has C(7, k - 1) positive integer roots, so the number of parts : k * C(7, k - 1) We easily know that k is from 1 to 8, so the number of parts: Sum (k * C(7, k - 1)), k = 1 -> 7, this is also the value of the integration of function $x(1 + x) ^ {7}$ at x = 1. So, the answer is 576