Sewing Combinatorics

To begin, note that we can make horizontal stitches (ten Top, ten Bottom) or vertical stitches (ten Left, ten Right), so there are four different positions for the first stitch. WLOG, assume that the stitches are vertical and that our first stitch is Left.

One possible arrangement of stitches by position is then LLLRRRRLLLLLRRRRRRLL. Note that in this arrangement, we have two choices of how to make the first Left stitch (from top to bottom or from bottom to top); however the next two Left stitches have to follow the same choice as the first Left stitch. When we switch to the Right for the fourth stitch, we again can choose the direction for that stitch (top to bottom or bottom to top) but after that the next three Right stitches must follow the same direction as the first Right.

Following this reasoning, it should be clear that we have a choice of two directions for the first stitch in each run of consecutive Left or Right stitches, but no choice for any subsequent stitches in the same run. (To clarify, the above arrangement would consist of a run of three Lefts, a run of four Rights, a run of five Lefts, a run of six Rights and finally a run of two Lefts.)

Thus the number of ways of sewing any particular arrangements depends on the number of runs of consecutive stitches on the same side. For the above arrangement, which consists of five runs, there would be $2^5 = 32$ ways of stitching it; and in an arrangement with $k$ runs, there would be $2^k$ ways of stitching it. So we need to count the number of arrangements of Left and Right stitches for all possible number of runs of consecutive stitches.

Let $k$ be the number of runs of consecutive stitches. (In the above example, $k$ would be $5$ .) If $k$ is even, then we will have $\frac{k}{2}$ Left runs and $\frac{k}{2}$ Right runs; on the other hand, if $k$ is odd, we will have $\frac{k+1}{2}$ Left runs and $\frac{k-1}{2}$ Right runs (remember our initial assumption was we were starting with a Left stitch.) Using the floor function, we can write a single formula for each side: $\left\lfloor \frac{k+1}{2} \right\rfloor$ Left runs and $\left\lfloor \frac{k}{2} \right\rfloor$ Right runs.

Consider the ten Left stitches. We have to split them into $\left\lfloor \frac{k+1}{2} \right\rfloor$ non-empty groups. Recall that $n$ identical objects can be partitioned into $k$ non-empty groups in $\binom{n-1}{k-1}$ ways. [Quick explanation: we'd need $k-1$ dividers, each of which can be placed at one of the $n-1$ positions between the objects, no more than one divider per position.]

Then the ten Left stitches can be partitioned in

$\dbinom{10-1}{\left\lfloor \dfrac{k+1}{2} \right\rfloor-1}$

ways. Similarly the ten Right stitches can be partioned in

$\dbinom{10-1}{\left\lfloor \dfrac{k}{2} \right\rfloor-1}$

ways. These two binomials can be simplified to

$\dbinom{9}{\left\lfloor \dfrac{k-1}{2} \right\rfloor} \quad \text{and} \quad \dbinom{9}{\left\lfloor \dfrac{k-2}{2} \right\rfloor}$

respectively. Thus, again keeping in mind we're starting with Left, the total number of ways to stitch an arrangement with k runs of consecutive stitches is

$\dbinom{9}{\left\lfloor \dfrac{k-1}{2} \right\rfloor} \dbinom{9}{\left\lfloor \dfrac{k-2}{2} \right\rfloor} 2^k$

We need to sum this over all possible values of k; clearly the lowest number of runs is two (ten Left followed by ten Right) and the largest is twenty (alternating single Left and single Right stitches). Therefore the total number of ways of stitching vertical stitches starting with a Left is

$\displaystyle\sum_{k=2}^{20}\dbinom{9}{\left\lfloor \dfrac{k-1}{2} \right\rfloor} \dbinom{9}{\left\lfloor \dfrac{k-2}{2} \right\rfloor} 2^k$

Unfortunately I have no idea how to compute this in any simple way, so I had to resort to brute force. I used Excel (!), below is a screengrab of the result.

Finally, we have to account for the four different positions for the first stitch, so our final answer is $577309148 \times 4 = \boxed{2309236592}$

For the problem, visualize two parallel sets as two separate containers, containing a number of items (visualized as number of switches). Let

• $T$ denote the number of top stitches;
• $n_1$ denote the number of times inserted back at the same hole;
• $n_2$ denote the number of inserts from forming the diagonal stitch;
• $n_3$ denote the number of inserts from forming the orthogonal stitch; it is the stitch that is parallel to the previously formed parallel top stitch;
• $P_1$ denote the set, where the 1st top stitch is formed
• $P_2$ denote the second set
• $s_1$ denote the number of self-inserts in $P_1$ , whereas $s_2$ in $P_2$
• $n_{\text{sw}_1}$ denote the number of swapping times to $P_1$ , whereas $n_{\text{sw}_2}$ denotes the number of swapping times to $P_2$ (excluding the first swap to $P_2$ )

---

Without loss of generality, we can assume that the first stitch included in $P_2$ is either the diagonal or orthogonal stitch. Thus, $(T - 1)$ more inserts must occur each on both sets. In this case, $s_1 + n_{\text{sw}_1} = s_2 + n_{\text{sw}_2} = (T - 1)$

Since the total number of inserts is the total number of top stitches formed, excluding the 1st, this can be expressed as $n_1 + n_2 + n_3 = 2(T - 1) - 1 = 2T - 1$

Then, since there is at least $1$ swap-insert that must occur in $P_2$ , $\begin{array}{rrl} 1 &\leq n_2 + n_3 &\leq 2T - 1\\ 0 &\leq n_2 + n_3 - 1 &\leq 2T - 2 \end{array}$

Noting that $P_1$ is the first to receive an insert,

• $P_1$ contains $\left\lceil \dfrac{n_2 + n_3 + 1}{2}\right\rceil$ switch-inserts
• $P_2$ contains $\left\lfloor \dfrac{n_2 + n_3 + 1}{2}\right\rfloor$ switch-inserts

Parametrizing,

• For $n_2 + n_3 = 2k_1 - 1$ odd, where $k_1 \in \mathbb{N}$ , $n_{\text{sw}_1} = n_{\text{sw}_2} = (k_1 - 1)$
• For $n_2 + n_3 = 2k_2$ even, where $k_2 \in \mathbb{N}$ , $n_{\text{sw}_1} = k_2$ and $n_{\text{sw}_2} = (k_2 - 1)$

So since

• The inserts for both two top stacks can be arranged in any order, so for $P_1$ we have $\dbinom{T - 1}{n_{\text{sw}_1}}$ and for $P_2$ we have $\dbinom{T - 1}{n_{\text{sw}_2}}$
• There are two different ways to identify each switch-insert
• There are 4 different holes to insert and 2 different arrangements to sew in the beginning

The total different ways to stitch a button in terms of $T$ is $8 \cdot 2^{2T - 1} + 8 \sum_{\text{odd}} + 8 \sum_{\text{even}} = 4\left(2^{2T} + \sum\limits_{n = 1}^{T - 1} 2^{2n}\dbinom{T - 1}{n - 1}^2 \dfrac{2T - n}{n}\right)$

where the bounds of $k_1$ and $k_2$ are made to be consistent. For the answer, if $T = 10$ , then we have $\boxed{2309236592}$ different ways.