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.

$\endgroup$

1 Answer 1

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$.)

$\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 at 3:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.