total number of unique collection of n-element each where each element can be any number from 1 to k. elements in the collection need not be distinct

Question

example let n = 2 and k = 4 then unique sets are {1,1}, {1,2}, {1,3}, {1,4}, {2,2}, {2,3}, {2,4}, {3,3}, {3,4}, {4,4} here {1,2} and {2,1} would be considered same.

if n were 3 {0,0,1}, {1,0,0}, {0,1,0} would be same similarly {1,2,3}, {1,3,2}, {2,1,3}, {3,1,2}, {1,3,2}, {2,3,1} would be same.

I've tried by assuming every collection as a n digit number in base k and trying to find the total number of such numbers that have their digits in ascending order{not strictly ascending} but i get stuck with a weird summation which can only be solved using dynamic programming using a computer

i think the answer is (n+k)!/(n!*k!) but i have no idea why how and why?

for context I arrived at this problem while finding the number of unique paths a person can take while walking on a grid of n x k where he can only go down and right.

Answer 1

As alluded to in my first comment above, this is a very well known counting problem which can be counted using the technique of Stars-and-Bars.

It does not in fact matter what flavor you use to describe the objects you are counting, whether you are calling them ordered $n$-tuples who appear in non-strictly increasing order, or as functions, or as multi-sets or whatever other terminology you decide to use, so long as whichever you call it is one of the many appropriate ways of referring to the objects.

For now, I will refer to the objects you are counting as multisets. Like you desire, reordering of the elements in their representation do not make them distinct.

Now... take one of your multisets and associate it with an ordered $k$-tuple whose entries are the number of occurrences of the corresponding index in the multiset. For example with $n=3,k=4$ you have the multiset $\{1,1,1\}$ corresponds to the $4$-tuple $(3,0,0,0)$ while $\{2,2,3\}$ corresponds to $(0,2,1,0)$ and so on. It is clear to see that this is a bijection.

Now, counting the number of these objects is just what stars-and-bars is commonly described as doing (which you could have skipped the middle-man and described the original problem as being an application for stars-and-bars without insisting that we go through the effort of describing the problem explicitly as ordered $k$-tuples whose entries sum to $n$ like @amWhy appears to require in order to understand). A fuller description of the technique is provided in the link above, but the short hadwavey description is to arrange $n$ dots and $k-1$ bars in a line and interpret the arrangement as such a $k$-tuple in the obvious way. Note that we only require the use of $k-1$ bars, not a full $k$ number of bars, just as in the $k$-tuple we only use $k-1$ commas. The arrangement $\cdot\cdot\cdot\mid\mid\mid$ corresponds to $(3,0,0,0)$ for instance while $\mid\cdot\cdot\mid\cdot\mid$ corresponds to $(0,2,1,0)$ and so on. Counting the number of such arrangements of stars and bars is performed using binomial coefficients and will be:

$$\binom{n+k-1}{k-1}$$

---

In your edit you talk about an unrelated problem of counting lattice paths on a 2-d lattice using only downs and rights on a grid of size $n\times k$. Depending on whether you are positioned in the center of each square or whether you position yourself only on vertices, you will get a different answer. If you position on vertices, recognize that there are $n$ downs total and $k$ rights total that will be performed and the order in which they occur is relevant. There will be $\binom{n+k}{k}$ such orders, again a routine application of binomial coefficients.

Answer 2

For enrichment here are two combinatorial proofs which are actually equivalent. The first is the OGF of these multisets by their sum, with the number of elements marked. We obtain analogously to the OGF of integer partitions the closed form:

$$[z^m] [u^n] \prod_{q=1}^k \frac{1}{1-uz^q}.$$

Now we actually don't require the classification by the total $m$ so we may set $z=1$ and collapse the OGF to one variable. We obtain

$$[u^n] \prod_{q=1}^k \frac{1}{1-u} = [u^n] \frac{1}{(1-u)^k} = {n+k-1\choose k-1}.$$

This concludes the first proof.

The second uses the unlabeled multiset operator from the analytic combinatorics method. We get the following combinatorial class:

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{MSET_{=n}} \left(\sum_{q=1}^k \mathcal{Z}^q\right).$$

Now the multiset operator here is just the cycle index of the symmetric group, so we get the OGF

$$Z(S_n; z+z^2+z^3+\cdots+z^k).$$

The OGF of the $Z(S_n)$ is given by

$$Z(S_n) = [w^n] \exp\left(\sum_{\ell \ge 1} a_\ell \frac{w^\ell}{\ell}\right).$$

We thus get for the multisets classified by total sum $m$ that it is

$$[z^m] [w^n] \exp\left(\sum_{\ell \ge 1} \frac{w^\ell}{\ell} \sum_{q=1}^k z^{\ell q} \right).$$

We may dispense with $z$ as the variable for the total sum as before and obtain

$$[w^n] \exp\left(\sum_{\ell \ge 1} k \frac{w^\ell}{\ell} \right) = [w^n] \exp\left(k \log\frac{1}{1-w}\right) \\ = [w^n] \frac{1}{(1-w)^k} = {n+k-1\choose k-1}.$$

This concludes the second proof.