1
$\begingroup$

Let $\beta = (\beta_1, \beta_2, \ldots)$ be any given sequence of non-negative integers with all but finitely many $\beta_i$ zero. I want to collect all possible tuples $\beta^{\prime}= (\beta_1^{\prime}, \beta_2^{\prime}, \ldots)$ that satisfies the following two conditions:

(1) $\beta^{\prime} \geq \beta$, that is $\beta^{\prime}_i \geq \beta_i$ for all $i$

(2) $\beta^{\prime}$ can have more entries than $\beta$, in that case $\beta^{\prime}_i$ satisfies the condition $\sum i\cdot\beta^{\prime}_i = d$, where $n$ is a positive integer (for instance, if $\beta = (1), \text{and}~ d = 3$ then all possible $\beta^{\prime}$ will be the following list of tuples $\{ (1), (2), (3), (1,1) \}$).

Any suggestions on how to implement this in Mathematica would be great.

So, I tried to Use Module[{n}, n== Length[b], Table[ IF[conditions, betaprime ] range ] but it only gives me a nested lists out of which I couldn't able to list all possible $\beta^{\prime}$s.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

I believe the following works. It generates all$^1$ candidate lists $\beta'$ such that $\sum_i i\beta_i' \leq d$ and then compares them element-wise to $\beta$.

generateTuples[beta_, d_] := Module[{lst = PadRight[beta, d], candidates}, candidates = Flatten[FrobeniusSolve[Range[d], #] & /@ Range[d], 1]; Select[candidates, And @@ Thread[lst <= #] &] /. {a__Integer, 0 ..} :> {a} ]

So:

generateTuples[{1}, 3] (* {{1}, {2}, {1, 1}, {3}} *)

$^1$ I'm not entirely sure that I'm capturing all the possibilities or that I'm understanding the OP's requirement. The OP should check my assumptions and test this with lots of example lists.

Explanation

The list $\beta$ is assumed to terminate at the last non-zero entry $i_{\mathrm{max}}$. (This can be fixed to chop off trailing zeroes if necessary.) It is then padded with zeros up to length $d$ so that it can be directly compared with the generated candidates. Since a candidate $\beta'$ must satisfy $\sum_i i\beta_i' \leq d$, and $\beta$ consists of non-negative integers, the longest that $\beta$ can be is of length $d$, since $(0,0,\dots,0,\beta_d = 1)$ makes the sum equal to $d$.

We then generate all lists of non-negative integers satisfying the condition $\sum_i i\beta_i' \leq d$ using FrobeniusSolve, compare each of these candidates to $\beta$ element-wise, and keep those that satisfy $\beta_i \leq \beta_i'$.

(The last little bit /. {a__Integer, 0 ..} :> {a} of code chops off the trailing zeroes in each $\beta_i$.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you very much for your explanation and your code. I have checked for a lot of examples, and it gives me the correct list that I was looking for. $\endgroup$ Commented May 16, 2024 at 3:57

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.