How many different patterns to transport load with these condition?

Question

(I am not expert in English. I will write as well as I can.)

To transport load, you have to put load into trailer cart and transport it in rounds. (I will improve this part (if I can. I am not expert in English.) but I think you can under stand the question from an example.)

There are 5 sizes of carts which are 5,4,3,2,1 unit.

Conditions:

1.Each round must have at least one cart, for example (total load is 2 unit)

Round 1: 1/5 1/4

(mean "Round 1 : Use 5-unit cart with 1 unit of load , Use 4-unit cart with 1 unit of load")

/ , count as a pattern

Round 1: 1/5 Round 2: 1/4

/ , count as a pattern

Round 1: 1/5 1/4 Round 2:

x , doesn't count as one pattern

2.Load in each cart must be positive integer, for example (total load is 2 unit)

Round 1: 1.5/5 0.5/4

x , doesn't count as a pattern

Round 1: 2/5 0/4

x doesn't count as a pattern

3.Each round must't have 2 or more same size cart, for example (total load is 2 unit)

Round 1: 1/5 1/5

x , doesn't count as a pattern

4.Larger size cart must be in earier order, for example (total load is 2 unit)

Round 1: 1/4 1/5

x , doesn't count as a pattern

For total load is 5 unit, example of patterns

(1)

Round 1: 1/5 1/4

Round 2: 1/5 1/4

Round 3: 1/5

/ , count as one different pattern

(2)

Round 1: 1/5 1/4

Round 2: 2/5

Round 3: 1/5

/ , count as one different pattern

(3)

Round 1: 1/1

Round 2: 2/5

Round 3: 2/5

/ , count as one different pattern

(4)

Round 1: 3/5

Round 2: 2/5

/ , count as one different pattern

(5)

Round 1: 2/5

Round 2: 3/5

/ , count as one different pattern

...

If I give number of total load is 20 unit, how many patterns to transport load with these condition ?

(I think I don't forgot some condition.)

Answer 1

Let's start with a simpler problem by considering just a single round rather than multiple. In a slightly more generalized form, this easier problem can be stated as:

You have $N$ identical items and you want to place them into bins of capacity $K, (K-1), \ldots, 1$. How many different ways can you do so?

It is not too difficult to see that different ways of placing items into bins correspond (almost) exactly to different ways of distributing load into carts according to the rules of the original problem: empty bins just need to be thrown away and the remaining ones to be ordered by size. The sole exception is if we have no items at all (i.e. $N=0$); this would be impossible in the original problem due to rule #1 (no "empty" rounds).

Let $A_K(N)$ denote the count we are seeking. We will consider a few distinct cases:

• $A_K(0)=1$: there is just one way of placing "nothing" into any number of bins.
• $A_0(N)=0$ for $N\geq 1$: if we have some items but no bins, we cannot place them according to the rules.
• Now, if both $N$ and $K$ are positive, we can determine $A_K(N)$ in recursive fashion: After deciding how many items $i$ do we place into the largest bin (which is of size $K$) we are left with $(N-i)$ items to be placed into bins of size $(K-1)$ or smaller. Of course, the number $i$ is non-negative and cannot exceed the bin capacity $K$, nor the total number of items $N$. Thus, we have $$A_K(N)=\sum_{i=0}^{\min(K,N)} A_{K-1}(N-i)$$

Clearly, $A_K(N)=0$ if $N$ is greater than $1+2+\ldots+K=K(K-1)/2$. In the original problem, we will only need to look at $K\leq 5$ and $N\leq (1+2+3+4+5)=15$ (the maximum we can transport in one round), so we can simply fill a table (where rows correspond to $0\leq K\leq 5$ and columns are $0\leq N\leq 15$): $$\begin{array}{|l|l|} \hline 1 & \\ \hline 1 & 1 \\ \hline 1 & 2 & 2 & 1 \\ \hline 1 & 3 & 5 & 6 & 5 & 3 & 1 \\ \hline 1 & 4 & 9 & 15 & 20 & 22 & 20 & 15 & 9 & 4 & 1 \\ \hline 1 & 5 & 14 & 29 & 49 & 71 & 90 & 101 & 101 & 90 & 71 & 49 & 29 & 14 & 5 & 1\\ \hline \end{array}$$ (as you can see, $A_5(5)=71$, in agreement with @Niing's answer).

Now we are ready to tackle the original problem where we are allowed multiple rounds. As is turns out, it is not that much different from the problem we just solved!

Let $B_K(N)$ denote the number of ways of transporting load of $N$ using carts of capacity $1,2,\ldots,K$ using any number of rounds:

• Just as before, the case of $N=0$ is very easy: Since there is nothing to be transported, there is exactly one way of doing so (rule #1 requires at least one cart and rule #2 tells us this cart cannot be empty).
• Otherwise, $N\geq 1$, and we can proceed recursively too: We choose the number of items to be transported in the first round ($l$), distribute them in the carts (which we already know to be doable in $A_K(l)$ ways) and for each "first round", we will be left with with the same problem, but with just $(N-l)$ items. We also know that we need to transport at least one item in every round and the total capacity of carts in a round is $K(K+1)/2$ (and we obviously cannot transport more than $N$), so we can express it as follows:

$$B_K(N) = \sum_{l=1}^{\min(K(K+1)/2,N)} A_K(l)\times B_K(N-l)$$

As expected, this sum grows quite fast; mainly due to the multiplicative factor in it. The table below lists values of $B_5(N)$ with $0\leq N\leq 20$: $$\begin{array}{|r|r|} \hline N & B_5(N)\\ \hline 0 & 1\\ \hline 1 & 5\\ \hline 2 & 39\\ \hline 3 & 294\\ \hline 4 & 2210\\ \hline 5 & 16613\\ \hline 6 & 124887\\ \hline 7 & 938833\\ \hline 8 & 7057640\\ \hline 9 & 53055526\\ \hline 10 & 398842787\\ \hline 11 & 2998284641\\ \hline 12 & 22539484436\\ \hline 13 & 169439669505\\ \hline 14 & 1273755914139\\ \hline \hline 15 & 9575408955549\\ \hline 16 & 71982752463197\\ \hline 17 & 541127452230138\\ \hline 18 & 4067903901101749\\ \hline 19 & 30580304289498773\\ \hline 20 & 229886209992586147\\ \hline \end{array}$$

Thus, the answer to the original question is $229886209992586147$.

In general, the growth of $B(N)$ in relation to $N$ is approximately exponential; with multiplicative constant of roughly $7.52$ (for the specific case of $K=5$).

Answer 2

I'll try to brute force it. Since there is no restriction on the number of the total rounds.

---

#twenty rounds $$5^{20}$$

#nineteen rounds
1 round two cart + 1 cart two loads $${19\choose1}5^{18}\left[{5\choose2}+4\right]$$

#eighteen rounds
one stack $(2,)$
(1,1,1)+(2,1)+(3,) $${18\choose1}5^{17}\left[{5\choose3}+4\cdot4+3\right]$$

two stacks $(1,1)$
(2,)+(1,1) $${18\choose2}5^{16}\left[{(4+{5\choose2})\cdot(4+{5\choose2})}\right]$$

... but I think we should use as small rounds as possible so I stop here.

# two rounds(least)
strategy: first round full load(5 carts, 15 loads) for every cart then consider second round

(5,)+(4,1)+(3,2)+(3,1,1)+(2,2,1)+(2,1,1,1)+(1,1,1,1,1) $$1\cdot\left[1+\\2\cdot4+\\3\cdot3+\\3\cdot{4\choose2}+\\{4\choose2}\cdot3+\\{4\choose1}{4\choose3}+\\1\right],$$

which is 1+8+9+18+18+16+1=$71$.

For this question to be more realistic you should add more restrictions on so you won't waste resources, because for other cases the number will be, as I just show above, astronomical figures.