Breaking a set into continuous subsets such that number of $1$’s are greater than number of $0$’s

combinatoricscomputer sciencepermutations

You are given a list of $0$’s and $1$’s: $B[1], B[2],\ldots, B[N]$. A
sublist of this list is any contiguous segment of elements—i.e.,
$A[i], A[i + 1],\ldots , A[j]$, for some $i$ and $j$.

A sublist is said to be Heavy, if the number of $1$’s in it is at
least as much as the number of $0$’s in it.

We want to partition the entire list into Heavy sublists. That is, a
valid partition is a collection of Heavy sublists, such that each of
the $N$ elements is part of exactly one of the sublists. We want to
find the number of ways of doing so.

For example, suppose $N$ was $3$ and $B = [1, 0, 1]$. Then all the
sublists in this are Heavy, except for the sublist which contains only
the second element $([0])$. The various valid partitions are as
follows:

$( [1, 0, 1] )$

$( [1, 0], [1] )$

$( [1], [0, 1] )$

Since there are $3$ ways to do this, the answer for this would be $3$.

Compute the number of ways of partitioning the given list into Heavy
sublists for the following instances.

(a) $N = 8, B = [0, 1, 1, 0, 0, 1, 1, 1]—i.e., B[1] = 0, B[2] =
> 1,\ldots , B[8] = 1$

(b) $N = 9, B = [1, 1, 0, 0, 1, 0, 0, 1, 1]—i.e., B[1] = 1, B[2] =
> 1,\ldots , B[9] = 1$

(c) $N = 9, B = [1, 0, 1, 0, 1, 1, 0, 1, 1]—i.e., B[1] = 1, B[2] =
> 0,\ldots , B[9] = 1$

My Attempt:

I tried considering each $0$ to be $-1$ and tried calculating all the subsets that would give me a sum $\geq 0$. But we need to make sure all the partitions follow this rule. This makes my method too long and difficult to compute.

Can anyone give an idea for a better method.

Best Answer

I think you want to use a recursive algorithm. Call a sublists starting at $B[1]$ a "prefix" and a sublist ending at $B[N]$ a "suffix." For each possible way of diving the list into a suffix and a prefix, if the prefix is heavy, recursively count the number of ways of dividing the suffix into heavy sublists. (Remember to count the division into just the suffix itself.) Add up all of these, and add $1$, for the division consisting of just the original list.

Related Solutions

[Math] Number of ways to partition a set with $n$ elements to $k$ subsets where at least one subset has $r$ elements

The bivariate generating function of the Stirling numbers of the second kind is given by $$G(z,u) = \exp(u(\exp(z)-1))$$ so that $$n! [z^n][u^k] G(z, u) = {n \brace k}.$$ If you want to forbid subsets of $r$ elements, mark them and the generating function becomes $$H(z,u) = \exp\left(uv\frac{z^r}{r!} - u \frac{z^r}{r!} + u(\exp(z)-1)\right) = \exp\left(uv\frac{z^r}{r!} - u \frac{z^r}{r!}\right)G(z,u).$$ This has the property that the coefficient of $[v^0]$ is the generating function of the partitions with sets of size $r$ not allowed, which is $$[v^0] H(z, u) = [v^0] \exp\left(uv\frac{z^r}{r!} \right) \exp\left(-u\frac{z^r}{r!} \right) G(z,u) \\= \exp\left(-u\frac{z^r}{r!} \right) G(z,u) .$$ Now extracting the coefficient of $[z^n]$ from this we find $$n! \sum_{q=0}^{\lfloor n/r\rfloor} \frac{1}{q!} \left(-\frac{u}{r!}\right)^q [z^{n-qr}] G(z, u) .$$ We then obtain for the coefficient of $[u^k]$ the formula $$n! \sum_{q=0}^{\min(k, \lfloor n/r\rfloor)} \frac{(-1)^q}{q!\times (r!)^q} [u^{k-q}] [z^{n-qr}] G(z, u) \\= n! \sum_{q=0}^{\min(k, \lfloor n/r\rfloor)} \frac{1}{(n-qr)!} \frac{(-1)^q}{q!\times (r!)^q} [u^{k-q}] (n-qr)! [z^{n-qr}] G(z, u) \\ = n! \sum_{q=0}^{\min(k, \lfloor n/r\rfloor)} \frac{1}{(n-qr)!} \frac{(-1)^q}{q!\times(r!)^q} {n-qr \brace k-q}.$$ This formula gives the number of set partitions of $n$ elements into $k$ sets with subsets of size $r$ not allowed. Subtract this from ${n\brace k}$ to get the number of partitions where there is at least one subset of $r$ elements.

The OEIS has the case of $k=2$ and $r=1$, the case of $k=3$ and $r=1$ and the case of $k=4$ and $r=1$.

Observation. There is an interesting sanity check here, namely what happens when $r>n$. In this case the formula should produce ordinary Stirling numbers because forbidding subsets of a size larger than the total count of available elements does not affect the statistic. And indeed we have $\lfloor n/r \rfloor = 0$ so that only $q=0$ contributes, giving $$n! \frac{1}{n!} \frac{1}{1\times(r!)^0} {n\brace k} = {n\brace k},$$ so the check goes through and we get the correct value.

[Math] How to partition a set into k subsets, given minimum subset size is limited by some constant

You're looking for triples of three numbers (which I'm going to list in nondecreasing order) that sum to 36, and where each one is at least 5.

Instead you can look for triples of three numbers $p \le q \le r$ that sum to $36 - 15 = 21$, where each is nonnegative, and then the numbers you originally sought were $p+5, q+5, r+5$. (i.e., there's a 1-1 correspondence between the collection of partition-sizes that you seek and the collection of $(p, q, r)$ with $0 \le p \le q \le r$ and $p+q+r = 21$.)

These latter triples can be divided into those with $p = 0$, where the remaining numbers sum to 21; those where $p = 1$, and the remaining numbers sum to $20$...but both are at least $1$, those where $p = 2$, and the remaining numbers sum to $19$, but both are at least $2$, etc.

But the same trick applies to those: pairs of numbers, in nondecreasing order, summing to to $19$, but both being at least $2$ have the same count as pairs of (nondecreasing) numbers, summing to $15$, but both being at least $0$.

Let's write $$ C(n, k) $$ for the number of $n$-element sets of nonnegative numbers, in increasing order, that sum to exactly $k$. Then what I've said above shows that the number you're looking for is $C(3, 21)$, and that

$$ C(3, 21) = C(2, 21) + C(2, 21-3\cdot 1) + C(2, 21-3\cdot 2) + \ldots + C(2, 21-3\cdot 7) $$

Now how large is $C(2, k)$? It, too, satisfies a recurrence: the first number is either $0$ (in which case the remaining number must sum to 21), or it's 1, in which case the remaining number must be at least 1 and sum to 20, i.e., the count of which is the same as numbers that are at least 0 and sum to 19, etc. $$ C(2, k) = C(1, k) + C(1, k-2 \cdot 1) + C(1, k-2 \cdot 2) + \ldots + C(1, k-2 \cdot (k/2)) $$ where the $k/2$ in the last term should be rounded down [i.e., if $k$ is odd, then we end with $C(1, 1)$ rather than $C(1, -1)$. ]

Now how large is $C(1, s)$ for any nonnegative $s$? It's exactly $1$.

That means that $C(2, k)$ is exactly $\lfloor \frac{k+1}{2} \rfloor$.

So $$ C(3, 21) = \lfloor \frac{22}{2} \rfloor + \lfloor \frac{19}{2} \rfloor + \lfloor \frac{16}{2} \rfloor + \lfloor \frac{13}{2} \rfloor + \lfloor \frac{10}{2} \rfloor + \lfloor \frac{7}{2} \rfloor + \lfloor \frac{4}{2} \rfloor + \lfloor \frac{1}{2} \rfloor \\ = 11+9 + 8 + 7 + 5 + 3 + 2 = 45. $$

This seems surprisingly low to me, but I don't see any obvious error (except that my "round down $(k+1)/2$" answer for $C(1, k)$ could be off by one), so I'm going to go ahead and submit it as an answer, and if not an answer, at least a suggested path for you to follow in getting to the correct answer.

Let me just sanity check by writing them down...there aren't that many.

12, 12, 12
11, 12, 13
11, 11, 14
10, 13, 13
10, 12, 14
10, 11, 15
10, 10, 16
9, 13, 14
9, 12, 15
9, 11, 16
9, 10, 17
9, 9, 18
8, 14, 14
8, 13, 15
8, 12, 16
8, 11, 17
8, 10, 18
8, 9, 19
8, 8, 20
7, 14, 15
7, 13, 16
7, 12, 17
7, 11, 18
7, 10, 19
7, 9, 20
7, 8, 21
7, 7, 22
6, 15, 15
6, 14, 16
6, 13, 17
6, 12, 18
6, 11, 19
6, 10, 20
6, 9, 21
6, 8, 22
6, 7, 23
6, 6, 24

Hunh. I seem to get 38. So I probably DID have an off-by-one error in my formula for $C(2, k)$. Anyhow, the answer is 38, and you can work out my off-by-one error by back-tracing, if it pleases you do to so.

Best Answer

Related Solutions

[Math] Number of ways to partition a set with $n$ elements to $k$ subsets where at least one subset has $r$ elements

[Math] How to partition a set into k subsets, given minimum subset size is limited by some constant

Related Question