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 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 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$
    – Makenzie
    Commented Mar 22 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$
    – Makenzie
    Commented Mar 22 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 at 12:04
  • $\begingroup$ I've added a general formula for $\sigma$-forcing partitions for $t$. $\endgroup$ Commented Mar 22 at 21:04

You must log in to answer this question.

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