0
$\begingroup$

When it comes to partitions, I know we can impose some modest restrictions (maybe even a couple) on the partitions and obtain counting formula, but I would like to impose some more serious constraints and still be able to produce a formula, generating function, or recurrence in order to count how many partitions there are that satisfy my constraints. In particular, I've come across the following scenario in some non-mathematical research.

Let $M$ and $N$ be positive integers and let $1\leq t\leq M$. I will call a partition $\lambda$ of $M$ into $N$ nonnegative parts "$s-$forcing for $t$" if the following condition holds: $$\text{$\forall A\subset \lambda,$ $\left(\sum\limits_{a\in A}a \geq t\implies |A|\geq s\right)$}$$

I will call a partition $\lambda$ of $M$ into $N$ nonnegative parts "maximally $s-$forcing for $t$" if $\lambda$ is $s-$forcing but not $(s+1)-$forcing.

In general, if we denote the set of $s-$forcing partitions by $\Lambda_s$, then we have the containment $$\Lambda_1\supseteq \Lambda_2\supseteq \cdots \supseteq \Lambda_N$$

Question 1: For a given $t$, how many partitions of $M$ into $N$ nonnegative parts are $2-$forcing for $t$?

Answer 1: This is the number of partitions of $M$ into $N$ parts with each part having size less than $t$.

Question 1.5: For a given $t$, how many partitions of $M$ into $N$ nonnegative parts are maximally $2-$forcing for $t$?

Question 2: For each $t$, there is a minimal positive integer $\sigma$ so that no partition is $\sigma-$forcing. How many partitions of $M$ into $N$ nonnegative parts are maximally $(\sigma-1)-$forcing?

If people have relevant references (maybe these have been studied before under a different name), I would love to do some reading. Otherwise, any mathematical help toward solutions would be greatly appreciated. Note: I am not assuming here that $M\geq N$, but that additional premise may be helpful for the time being.

Edit: This question is seemingly related to the question here.

$\endgroup$
3
  • 1
    $\begingroup$ It's slightly unusual to talk about a partition of a number into "nonnegative" parts. Generally the parts of a partition are positive (i.e., we do not count the zero parts), so your partitions of $M$ into $N$ nonnegative parts would really be described as partitions of $M$ into at most $N$ (positive) parts. $\endgroup$ Commented Mar 21, 2024 at 17:14
  • 1
    $\begingroup$ Furthermore the body text of your question does not really seem to match the title (but I guess it's hard to describe your condition in a snappy way). Does this condition come from somewhere? $\endgroup$ Commented Mar 21, 2024 at 17:15
  • $\begingroup$ @SamHopkins The condition comes from a desire to "spread out" $M$ so that there aren't too many big chunks. The idea of "forcing" is simply trying to capture how spread out $M$ is, but this is a term I came up with. If you think about the partition rather as placing some indistinguishable objects into indistinguishable boxes, then a partition is $s-$forcing for $t$ if you have to open at least $s$ boxes to acquire $t$ objects. The reason for the nonnegative condition is that I might want to leave a box empty, but I don't want to talk about (weak) compositions. $\endgroup$ Commented Mar 22, 2024 at 11:44

1 Answer 1

1
$\begingroup$

Let $t$ be fixed.

Per Answer 1, the number of 2-forcing (nonnegative) partitions equals the coefficient of $q^M$ in Gaussian binomial coefficient $\binom{N+t-1}{N}_q$.

To answer Question 1.5, it is enough to note that a 2-forcing partition is maximally 2-forcing iff the sum of its two largest parts $\geq t$. It follows that the number of maximally 2-forcing partitions is given by $$\sum_{s=t}^{2t-2} \sum_{k=s-t+1}^{\lfloor s/2\rfloor} [q^{M-s}] \binom{N-2+k}{N-2}_q = [q^M]\sum_{k=0}^{t-1} \frac{q^{\max(2k,t)}-q^{k+t}}{1-q} \binom{N-2+k}{N-2}_q,$$ where $s$ stands for the sum of two largest parts, and $k$ stands for the second largest part.


In general, a partition is $\sigma$-forcing for $t$ if the sum of its $\sigma-1$ largest parts is $<t$, which leads to the following answer to Question 2:

No partition can be $t+1$-forcing for $t$, while there exists only one $t$-focing partition - entirely composed of parts $0$ and $1$.

ADDED. Here is a formula for the number of $\sigma$-forcing partitions for $t$ in a form of generting function:

$$[q^{M-1+t}z^{t-1}] \binom{\sigma-2+M}{\sigma-2}_z (1-\frac{z}{q})^{-1} \prod_{i=0}^{N-\sigma+1} \frac1{1-q^iz^{\sigma-1}} $$

$\endgroup$
3
  • $\begingroup$ And presumably, one could write a similar (triple?) sum for 3-forcing, etc. $\endgroup$ Commented Mar 22, 2024 at 11:45
  • $\begingroup$ @Makenzie: Yes, I've added a note about the general case. The formula would involve $s$-fold summation (or summation over partitions of length $s$) similar to the one given for $s=2$. $\endgroup$ Commented Mar 22, 2024 at 12:04
  • $\begingroup$ I've added a general formula for $\sigma$-forcing partitions for $t$. $\endgroup$ Commented Mar 22, 2024 at 21:04

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.