# Formula for partitions of integers with no subpartition being a partition of $t$

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.

• 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. Commented Mar 21 at 17:14
• 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? Commented Mar 21 at 17:15
• @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. Commented Mar 22 at 11:44

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 $$, 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}}$$

• And presumably, one could write a similar (triple?) sum for 3-forcing, etc. Commented Mar 22 at 11:45
• @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$. Commented Mar 22 at 12:04
• I've added a general formula for $\sigma$-forcing partitions for $t$. Commented Mar 22 at 21:04