Number of contiguous set partitions of $\{1,\dots,N\}$ is same as number of ordered arithmetic partitions of $N$? (Because of stars and bars?)

455 Views Asked by At

Note: This question is more of a sanity check than anything, and is probably a duplicate, so if you find the original question (I was unable to), please link to it and close this question.

Question: Given fixed natural numbers $N,k \ge 1$, is the number of contiguous set partitions of the set $\{1, 2, \dots, N\}$ into exactly $k$ blocks equal to the number of ordered arithmetic partitions of the integer $N$ into $k$ summands?

Namely the number for both is $\binom{N-1}{k-1}$, the number given by using stars and bars? (See definitions below)

Definitions: When talking about the number of contiguous set partitions of a finite set with cardinality $N$, I assume that some well order has been imposed on its elements, so that it is both bijective and order-isomorphic with the set of the first $N$ natural numbers $\{1, \dots, N\}$, which it therefore from now on will be assumed to be without loss of generality. Then:

A contiguous set partition of $\{1, \dots, N\}$ is a set partition of $\{1, \dots, N\}$ such that $n_1 \sim n_2$ (the two integers $n_1, n_2$ belong to the same block of the set partition) implies that there does not exist any $n_3$ such that $n_1 < n_3 < n_2$ but $n_1 \not\sim n_3$ (and thus also $n_2 \not\sim n_3$) (i.e. $n_3$ does not belong to the same block as $n_1$ and $n_2$).

For example, the set partitions $\{ \{1\}, \{2,3\} \}$ and $\{ \{1,2\}, \{3\} \}$ of $\{1,2,3\}$ are contiguous set partitions of $\{1,2,3\}$ into two blocks, whereas $\{ \{1,3\}, \{2\} \}$ is not a contiguous set partition of $\{1,2,3\}$ into two blocks.

In particular, one should always have in general that:

$$ \# \text{ contiguous set partitions of }\{1,\dots,N\}\text{ into }k\text{ blocks} \quad \le \quad \# \text{ set partitions of }\{1,\dots,N\}\text{ into }k\text{ blocks}\,.$$

Meanwhile, an ordered arithmetic partition of the integer $N$ is similar to what I will call an arithmetic partition of an integer $N$, except that two ways of writing $N$ as the sum of the same integers will be considered different if the summands occur in different orders between the two summations (i.e. what the number of sums would be if addition were counterfactually non-commutative). For example, while $1+2$ and $2+1$ would be considered the same arithmetic partition, they would be considered distinct as ordered arithmetic partitions.

Miscellaneous: I think I read somewhere that "ordered arithmetic partitions" are also called compositions, but I find the Wikipedia article difficult to understand, so I am not sure.

It would make sense if that's true, since there are apparently $2^{N-1}$ total compositions of $N$, and one has that

$$ \sum_{k=1}^N \binom{N-1}{k-1} = \sum_{k=0}^{N-1} \binom{N-1}{k} = 2^{N-1} \,.$$

Anyway, one should in particular have in general that:

$$\text{# of arithmetic partitions of $N$ into $k$ summands} \quad \le \quad \text{# of ordered arithmetic partitions of $N$ into $k$ summands} \,.$$

Proof attempt: It seems like these are actually the same problem when one tries to solve them using stars and bars, although to be perfectly honest I don't know how to phrase any reasoning for this rigorously.

I guess basically we have a function from contiguous set partitions of $\{1,2,\dots, N\}$ to ordered arithmetic partitions of $N$ given by sending each block in the contiguous set partition to the integer which is its cardinality, and then summing those numbers together in the order of the blocks of the set partition when those blocks are (arbitrarily) ordered lexicographically.

It seems like there is also an inverse function, namely given an ordered arithmetic partition of $N$, send each summand $n_i$ to the set of natural numbers (defining $N_i = \sum_{j=1}^{n-1} n_j$) to the block $\{N_i + 1, \dots, N_i + n_i \}$, such a set partition is by construction contiguous. Moreover, applying this function to the result of applying the first function seems to return the original value, although I don't feel comfortable arguing that part rigorously. But the stars and bars mental picture makes it seem pretty obviously true.

Anyway if there is an invertible function between these two finite sets, then they are in bijective correspondence, and thus have the same cardinality, concluding the argument.

Conjecture: This is somewhat unrelated, but it seems like one has the following relationships:

$$ \begin{array}{rcl} \text{# of arithmetic partitions of $N$ into $k$ summands} & \le & \text{# of ordered arithmetic partitions of $N$ into $k$ summands} \\ & = & \# \text{ contiguous set partitions of }\{1,\dots,N\}\text{ into }k\text{ blocks} \\ &\le & \# \text{ (unordered) set partitions of }\{1,\dots,N\}\text{ into }k\text{ blocks} \\ & \le & \# \text{ ordered set partitions of }\{1,\dots,N\}\text{ into }k\text{ blocks} \end{array} \,.$$

These numbers seem to be $p_k(N) \le \binom{N-1}{k-1} \le S(N,k) \le k!S(n,k)$, where $p_k(N)$ represents the function giving the number of arithmetic partitions of the integer $N$ into $k$ summands, and $S(N,k)$ represents a Stirling number of the second kind.

(According to Wikipedia $p_k(N)$ apparently has no closed form expression, since if it did then the partition function $p(N) = \sum_{k=1}^N p_k(N)$ would have a closed form expression, and it apparently doesn't.)

It seems like the truth of this conjecture might just be a special case of the twelvefold way or twentyfold way, but to be honest I don't understand that Wikipedia article either, so I'm not sure.