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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.