Number of ways to riffle a list amongst an ordered list?

For starters this is similar to, but not a duplicate of Number of ways to split a list into consecutive parts and Expressing a positive integer as a sum of positive integers, as this question builds upon those questions.

Variables and Conventions

Let $$\mathscr{L}=\{l_1\prec l_2\prec \dots \prec l_{\lvert\mathscr{L}\rvert}\}$$ be an ordered list of $$L=\lvert\mathscr{L}\rvert$$ elements.

Let $$\mathscr{C}=\{c_1,c_2,\dots, c_{\lvert\mathscr{C}\rvert}\}$$ be the collection of $$C=\lvert\mathscr{C}\rvert$$ unordered elements we wish to place amongst the $$L$$ elements of $$\mathscr{L}$$.

Then there are $$L+1$$ slots to place these $$C$$ elements - one directly after each element of $$\mathscr{L}$$ and one prior to $$l_1$$.

Question

How many ways are there to place the elements of $$\mathscr{C}$$ amongst the ordered elements of $$\mathscr{L}$$?

Ideally, I would like to show that the number of ways to place the elements of $$\mathscr{C}$$ amongst those of $$\mathscr{L}$$ is less than or equal to $$(C+L)!$$ (which intuitively should be clear to see; you are ordering $$C+L$$ items, but such that the order of the items in $$L$$ are preserved.)

Example

Since the only parameter $$\mathscr{L}$$ affects is the number of slots in which to place the elements of $$\mathscr{C}$$, we can reframe our problem in either of the following ways:

1

How many ways can $$C$$ items be placed amongst $$n=L+1$$ containers (and then ordered)? Note that some of these containers may receive no items.

2

How many ways is there to split an ordered list into $$n=L+1$$ groups such that each group contains at least $$1$$ element?

To make this equivalent to 1, we must consider splitting the list into $$i$$ groups where $$1\leq i\leq n$$ and multiple it by the ways w can order the elements of $$\mathscr{C}$$: $$C!$$

I personally think 2 is easier to approach, although it may be more complicated than 1.

So there $$C!$$ ways to order our list. We can put the elements of $$\mathscr{C}$$ in either $$1$$ or $$2$$ up to min($$n$$,$$C$$) slots of the $$n$$ available slots. If we want to put all of these elements in $$1$$ slot, then there are $$\binom{n}{1}$$ ways to choose which slot to put those elements in.

What if we want to put them in $$2$$ slots? Then there are $$\binom{n}{2}$$ ways to choose which slots to use... but how many ways to split our ordered list amongst them such each slot gets at least one element? For $$2$$ slots it is simple, $$C-1$$ (as we can not split the list after the last element, or else the second slot would get zero elements).

So we can see a formula being built up as:

$$C! \cdot \sum\limits_{i=1}^{\text{min}(C-1,~~n)}\binom{n}{i} (n-i)$$

where $$n-i$$ represents the number of ways to cut a list into $$i$$ parts such that each part contains at least one element (check me on this, but I think this is correct).

The problem is that this idea might be very wrong!

Why?

Let $$\mathscr{L}=\{1\} \quad L=1, n=2$$ and $$\mathscr{C}=\{2,3,4\},\quad C=3$$, then the above formula spits out 30, which is wrong because there are at most 24 ways to linearly order a list of 4.

So what am I missing?

• Just to confirm: the set $\mathscr{C}$ must remain ordered whilst $\mathscr{L}$ does not? If this is the case then elements of $\mathscr{C}$ may as well be indistinguishable (let's label them A) and all we do is count arrangements of elements $\mathscr{L}$ and $|\mathscr{C}|$ "A"s. Mar 15, 2017 at 13:15
• @N.Shales vise-versa the elements of $\mathscr{L}$ must maintain their order (although elements of $\mathscr{C}$ can be injected between them) Mar 15, 2017 at 13:16
• Sorry , yes, that's what I meant (got sets mixed up). Well there are $\frac{(|\mathscr{L}|+|\mathscr{C}|)!}{|\mathscr{L}|!}$ arrangements of $|\mathscr{L}|$ "A"s and the $|\mathscr{C}|$ numbered elements of $\mathscr{C}$. Mar 15, 2017 at 13:21

Another equivalent framing is to look at all the $(C+L)!$ orderings of $\mathscr{L}+\mathscr{C}$ and ask what proportion are "valid", having the elements of $\mathscr{L}$ in the right order. Clearly we can convert any ordering into a valid ordering by sorting the elements of $\mathscr{L}$ in place, so there are a set of $L!$ orderings of which one is valid. Thus the answer to the headline question is $\frac{\large(C+L)!}{\large L!}$.

The equivalence to your first framing is to regard the elements of $\mathscr L$ as a set of dividers between the containers in a classic stars-and-bars (except with distinct stars), so $C!\binom {C+L}{L}$.

I can't quite see how the $L{+}1$ non-empty sections in the second framing are formed, especially if the elements of $\mathscr C$ are all interior to the list.

• in that framing it is much easier to see, could you derive equivalence from an alternative framing? Mar 15, 2017 at 13:20
• For the second framing, you could place 1, some, or all of the content of $\mathscr{C}$ after each element of $\mathscr{L}$ or before the first element. There are $L=\lvert\mathscr{L}\rvert$ spots in total (one for each element) and then the one prior to the first element of $\mathscr{L}$, so $L+1$. Mar 15, 2017 at 20:43
• Which would be OK except you specify that each group contains at least one element. When the first and last elements of the final list are both in $\mathscr L$, you definitely have an empty section. Mar 15, 2017 at 21:39
• My apologies, I was not precise enough in my language, if you were only choosing $n<=\text{min}(L+1,C)$ of the available $L+1$ slots, such that the chosen slots are not empty. Mar 15, 2017 at 21:42

We want to totally order the $L+C$ elements into a list, but keeping the existing order on the $L$ elements. That can be done in $(L+C)!\over L!$ ways, or $(L+C)^{\underline C}\overset{\rm def}=(L+C)(L+C-1)\ldots(L+1)$ (falling factorial).