How many tuples are there that satisfy the conditions listed below?

72 Views Asked by At

I am looking for the number of tuples in the hypercube $[0,1]^n\subset\Bbb R^n$ such that all the components add up to one. For example, all the elements $e_i$ in the standard basis with the $i$-th component being 1 and all other components 0 clearly fit the description. Note that each dimension is constrained by $[0,1]$, so we can't have anything larger than 1 or smaller than 0. I guess we can imagine them as some weights in a probability space.

Furthermore, we can only partition each dimension into $p$ equally spaced segments. For example, when $p=3$, say, each component can only have values 0, $\frac{1}{3}$, $\frac{2}{3}$, or 1. In this case, permissive tuples in $\Bbb R^2$ are $$(0,1), \left( \frac{1}{3}, \frac{2}{3} \right), \left( \frac{2}{3}, \frac{1}{3} \right)\text{ and }(1,0).$$ Likewise, permissive tuples in $\Bbb R^3$ are $$(0,0,1), \left(0, \frac{1}{3}, \frac{2}{3} \right), \cdots, \left(\dfrac{1}{3},\dfrac{1}{3},\dfrac{1}{3}\right)\cdots, \left( \frac{2}{3}, \frac{1}{3},0 \right) \text{ and }(1,0,0).$$ Make sure all the components sum up to 1. You got the idea.

The problem is, how many tuples are there that satisfy my conditions given $n$, the number of dimensions, and $p$, the number of equidistant partitions. I am essentially looking for a counting function $f(n,p)=\left|\left\{v\in\Bbb R^n;\sum_iv_i=1, \forall v_i\exists z_i\left(z_i\in\Bbb Z\cap[0,p], v_i=\frac{z_i}{p}\right)\right\}\right|$.

Here are some of my thoughts (please correct me). In the 2D case, we are essentially counting the number of grid points on the diagonal plotted below for the case $p=3$.

The 2 dimensional case.

The answer apparently is 4. In $\Bbb R^3$, all the candidate tuples lie on the diagonal plane plotted here (stealing graphics from wikipedia).

The 3 dimensional case.

There should be $4!=10$ candidate tuples on this plane. Because of the extra constraint of summing up to 1, we are always working with $(n-1)$ dimensional hyperplanes in the hypercube.

I don't see very clearly for higher dimensions. But I coded a little simulation, and if I am not mistaken (which I might be), $f(10,10)=92378$ (please check!).

Any help is appreciated

1

There are 1 best solutions below

3
On BEST ANSWER

Your points are of the form $(\frac{z_1}{p}, ...,\frac{z_n}{p})$. Taking each $z_i$ in $\mathbb{N}_{\leq p} \cup \{0\}$ will suffice for the points to be in $[0,1]$, and is also necessary, so this is a matter of counting the amount of tuples $(z_1, ..., z_n)$ of numbers from zero to $p$ such that they sum $p$. This is like distributing $p$ indistinguishable coins in $n$ boxes, which is a classical combinatorial problem. In your notation,

$$ f(n,p) = {n+p-1 \choose p} $$