0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – N. Shales
    Mar 15, 2017 at 13:15
  • 1
    $\begingroup$ @N.Shales vise-versa the elements of $\mathscr{L}$ must maintain their order (although elements of $\mathscr{C}$ can be injected between them) $\endgroup$
    – SumNeuron
    Mar 15, 2017 at 13:16
  • $\begingroup$ 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}$. $\endgroup$
    – N. Shales
    Mar 15, 2017 at 13:21

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ in that framing it is much easier to see, could you derive equivalence from an alternative framing? $\endgroup$
    – SumNeuron
    Mar 15, 2017 at 13:20
  • $\begingroup$ 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$. $\endgroup$
    – SumNeuron
    Mar 15, 2017 at 20:43
  • $\begingroup$ 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. $\endgroup$
    – Joffan
    Mar 15, 2017 at 21:39
  • $\begingroup$ 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. $\endgroup$
    – SumNeuron
    Mar 15, 2017 at 21:42
0
$\begingroup$

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).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .