2
$\begingroup$

Consider the set of the first $n$ integers $\lbrace 1,\dots,n\rbrace$ and consider a subset $B\subset\lbrace 1,\dots,n\rbrace$ of $m\leq n$ elements. We say that $B$ is good if the partition of $B$ into subsets of consecutive integers are of lengths $2^k-1$ for some $k$. For example:

  • $\lbrace 1,3,6,9\rbrace$ is partitioned into $\lbrace 1\rbrace,\lbrace 3\rbrace,\lbrace 6\rbrace,\lbrace 9\rbrace$. Hence, it is good since all these subsets have $1=2^1-1$ elements.
  • $\lbrace 1,2,3,6,9\rbrace$ is partitioned into $\lbrace 1,2,3\rbrace,\lbrace 6\rbrace,\lbrace 9\rbrace$. Hence, it is good since all these subsets have length $3=2^2-1$ or $1=2^1-1$.
  • $\lbrace 1,2,6,9\rbrace$ is partitioned into $\lbrace 1,2\rbrace,\lbrace 6\rbrace,\lbrace 9\rbrace$. Hence, it is bad since there is a subset of length $2$.

Given $n\geq m$ I want to compute the number $S_{n,m}$ of good subsets of $m$ elements over a set of $n$ elements. I've tried to do a systematic approach to count all the cases:

  • First, count the numbers of good subsets such that all the subsets of the partition have length $1$
  • Second, count the numbers of good subsets such that all the subsets of the partition have length $1$ except for one of length $3$
  • Third, count the numbers of good subsets such that all the subsets of the partition have length $1$ except for two of length $3$ $\dots$
  • Now, count the numbers of good subsets such that all the subsets of the partition have length $3$ except for at most $2$ of length $1$ (this is the remainder of $m$ mod $3$)

And then go to the case where there is a subset of length $7$ and so on. I can compute the number of any of these subsets, but it is a very long task and there are a lot of possible combinations, so it doesn't seems the right approach. Perhaps we can find a reccursion that $S_{m,n}$ has to satisfy, but I am not able to do it.

Any help will be thanked.

$\endgroup$
2
  • $\begingroup$ Are you aware of stars and bars? And Inclusion/Exclusion principle? Because these tools will likely be helpful in making progress towards an answer. And I suspect you can get an answer in the form of sum(s) of binomial coefficients (due to stars and bars), but I doubt there will be a nice, simple, closed formula. $\endgroup$ Apr 25, 2023 at 9:03
  • $\begingroup$ @AdamRubinson A sum of binomial coefficients is ok, I dont think either that there will be a closed formula. Indeed it would be suprising to find a closed formula. $\endgroup$
    – Marcos
    Apr 25, 2023 at 9:58

1 Answer 1

1
$\begingroup$

Let $N(m,t)$ denote the number of solutions of the equation $$x_1+\cdots+x_t=m$$ where $x_1,\dots,x_t$ are integers of the form $2^k-1$.

For example, $N(10,4)=8$, since $$10=7+1+1+1=1+7+1+1=1+1+7+1=1+1+1+7=3+3+3+1=3+3+1+3=3+1+3+3=1+3+3+3;$$ also $N(10,2)=2$, $N(10,6)=15$, $N(10,8)=8$, $N(10,10)=1$, and $N(10,t)=0$ in all other cases.

For $n\ge m$ we have $$S_{n.m}=\sum_tN(m,t)\binom{n-m+1}t.$$ For example: $$S_{n,10}=2\binom{n-9}2+8\binom{n-9}4+15\binom{n-9}6+8\binom{n-9}8+\binom{n-9}{10}$$ $$S_{n,1}=\binom n1$$ $$S_{n,2}=\binom{n-1}2$$ $$S_{n,3}=\binom{n-2}1+\binom{n-2}3$$ $$S_{n,4}=2\binom{n-3}2+\binom{n-3}4$$

$\endgroup$
2
  • $\begingroup$ Thanks!!! Do you know if there is an explicit formula for $N(m,t)$? I want to use a compute to compute $S_{n,m}$ so anything, even if it is a realy complex formula, will help. $\endgroup$
    – Marcos
    Apr 25, 2023 at 10:02
  • $\begingroup$ No, I don't, sorry. $\endgroup$
    – bof
    Apr 25, 2023 at 10:30

You must log in to answer this question.

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