1
$\begingroup$

Let $T_n$ denote the set of $n$-tuples $\left(b_1, \ldots, b_n \right)$ of non-negative integers such that $$\sum_{i=1}^{n}ib_i=n.$$ I am trying to simplify the sum (whose indicies depend solely on $n, j$, and $k$)

\begin{align*} \sum_{\underset{b_{j}=k}{\left(b_{i}\right)_{i\le n}\in T_{n}}}\frac{n\left(n-1\right)\cdots\left(n-\sum_{i\le n}b_{i}+2\right)}{\prod_{l\le n}\left(b_l !\right)}. \end{align*}

where one of the components (component $b_j$) is equal to some number $k$ specified in advance.

How can I sum over all tuples in $T_n$ such that the $j$th component is fixed?

I am seeking a symbolic solution for general $n, k$, and $j$. In many cases, the sum will be zero (e.g., the largest $b_n$ can be is $1$ due to the weighted sum constraint on $T_n$.

Example For example, if $n=5$ and the second component is fixed to be $1$ ($b_2 = 1)$, then the sum above has two terms corresponding to the vectors $(3,1,0,0,0)$ and $(0,1,1,0, 0)$.

Improve this question
$\endgroup$
6
  • $\begingroup$ If the smallest $b_i$ can be is 1, then isn't $\sum_{i=1}^n i b_i$ always greater than $n$? $\endgroup$
    – JimB
    Dec 6, 2022 at 18:07
  • $\begingroup$ $b_i$ can be $0$. $\endgroup$
    – The Substitute
    Dec 6, 2022 at 18:13
  • $\begingroup$ Sorry. Don't know why I read "non-negative" as "positive". Need more coffee this morning. $\endgroup$
    – JimB
    Dec 6, 2022 at 18:14
  • 1
    $\begingroup$ What values of $n$ are you considering? Small integers? Large integers? A symbolic solution for general $n$ and $k$? $\endgroup$
    – JimB
    Dec 6, 2022 at 21:37
  • $\begingroup$ @JimB The latter, but I would settle for something that will allow me to plug in values of $n$ and $k$. $\endgroup$
    – The Substitute
    Dec 6, 2022 at 23:27

2 Answers 2

Reset to default
3
$\begingroup$

Assuming I've interpreted everything correctly, I have just brute-forced it as

sumB[{pos_, val_}, n_] /; pos <= n := Module[{bList},
  bList = Solve[n == Sum[i b[i] /. b[pos] -> val, {i, 1, n}], Delete[Array[b, n], pos], NonNegativeIntegers];
  If[bList != {}, bList = Array[b, n] /. bList /. b[pos] -> val];
  Sum[n!/(n - Total[bees] + 1)! 1/Times @@ Factorial[bees], {bees, bList}]
 ]

The first line generates the $n$-tuples $b_i$ satisfying $\sum_iib_i=n$ subject to $b_{\textrm{pos}}=\textrm{val}$. The second line then performs the sum.

NonNegativeIntegers was introduced in Version 12. Before that, one can use FrobeniusSolve and Select the relevant lists:

sumB[{pos_, val_}, n_] /; pos <= n := Module[{bList},
  bList = Select[FrobeniusSolve[Range[n], n], #[[pos]] == val &];
  Sum[n!/(n - Total[bees] + 1)! 1/Times @@ Factorial[bees], {bees, bList}]
]
Improve this answer
$\endgroup$
10
  • $\begingroup$ @TheSubstitute See if this does what you expect. $\endgroup$
    – march
    Dec 6, 2022 at 22:58
  • $\begingroup$ I haven't been able to obtain an output when I evaluate that. $\endgroup$
    – The Substitute
    Dec 7, 2022 at 4:08
  • $\begingroup$ @TheSubstitute. What version are you using? It might be the NonNegativeIntegers part, which was introduced in version 12. I've updated the code with something that should work pre-Version 12. $\endgroup$
    – march
    Dec 7, 2022 at 5:11
  • 1
    $\begingroup$ +1 Trying a few values of val and for specific pairs of n and pos and then plugging in the results of 'sumB` into oeis.org finds "the number of Dyck paths of semilength n having val ascents of length pos": sequence A102402 when pos = 2. $\endgroup$
    – JimB
    Dec 7, 2022 at 6:34
  • $\begingroup$ @march The second code is not defined at 'sumB[{2, 2}, 5]' whereas the first code gives the correct answer of 10. $\endgroup$
    – The Substitute
    Dec 7, 2022 at 16:45
3
$\begingroup$

  • T[n] is FrobeniusSolve[Range[n], n].

  • But I still don't understand the meaning of

How can I sum over all tuples in Tn such that the jth component is fixed?

so the code as below sum all the T[n] for fixed n.

Clear[T, n];
T[n_] := FrobeniusSolve[Range[n], n];
n = 8;
Product[m, {m, n, n - Plus @@ #+2, -1}]/Times @@ (#!) & /@ T[n] // Total
Improve this answer
$\endgroup$
3
  • $\begingroup$ I included an example to clarify. I want to be able to fix one of the entries in the vector (such as setting the 3rd entry equal to 2) and then sum over all of the vectors with this constraint. $\endgroup$
    – The Substitute
    Dec 7, 2022 at 4:10
  • 2
    $\begingroup$ Your code gives the Catalan numbers. $\endgroup$
    – JimB
    Dec 7, 2022 at 6:43
  • $\begingroup$ @JimB Thanks! Your comment enlightening me! $\endgroup$
    – cvgmt
    Dec 7, 2022 at 6:54

Your Answer

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

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