[Math] 5-tuples of n integers

combinatorics

If n is a positive integer, how many 5-tuples of integers from 1 through n can be formed in which the elements of the 5-tuple are written in decreasing order but are not necessarily distinct? In other words, how many 5-tuples of integers (h,i, j,k,m) are there with n ≥h ≥i ≥ j ≥k ≥ m ≥1?

I thought in consider this 5-tuple as a r-combination with repetition allowed. But I'm not 100% sure about that.

Best Answer

Let $a_1$ be the number of $1$'s that we use, and $a_2$ the number of $2$'s, and so on. Then our $5$-tuple is completely determined once we know $(a_1,a_2,\dots,a_n)$. So we want to count the number of solutions of $a_1+a_2+\cdots+a_n=5$ in non-negative integers.

By Stars and Bars (please see Wikipedia if the term is unfamiliar) the number of solutions is $\dbinom{5+n-1}{n-1}$ or equivalently $\dbinom{n+4}{5}$.