# Number of ways of take $m$ numbers from $\lbrace 1,\dots,n\rbrace$ such that the subsequences are of length $2^k-1$ for some $k$.

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.

• 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. Apr 25, 2023 at 9:03
• @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. Apr 25, 2023 at 9:58

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$$
• 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. Apr 25, 2023 at 10:02