if n is a positive integer, how many 4-tuples can be created from integers 1 through n where the elements are in increasing order but not necessarily distinct

Question

in other words, how many 4-tuples of integers (i,j,k,m) are there with 1<=I<=j<=k<=m<=n?

I know I need r-combinations with repetition allowed.

Answer 1

 

suppose n=9

you are choosing from the digits 1,2,3,4,5,6,7,8,and 9

suppose the digits are distinct, meaning no repetitions

any four digits you choose can be written in increasing order in only one way

for example, if you choose 1,2,3,and 4, you can only write 1234; any other order will not have all the digits in increasing order                                                               

if this is the case then the answer is C(9 choose 4)

the formula is n!/r!(n-r)! where n=# of objects and r=# of objects chosen, in this case n=9 and r=4

this would be 9!/4!(9-4)!=9!/4!5!=9*8*7*6/4*3*2*1=9*2*7=126 ways after simplifying

if the number of digits is n, then the answer would be C(n choose 4)

n!/4!(n-4)!=n(n-1)(n-2)(n-3)/4*3*2*1

 

suppose n=9

suppose the digits can repeat

any four digits you choose can be written in increasing order in only one way

for example, if you choose 3,3,5,and 6, you can only write 3356; any other order will not have all the digits in increasing order

if this is the case then the answer is C(9+4-1 choose 4)

(9+4-1)!/4!(9+4-1-4)!=12!/4!8!=12*11*10*9/4*3*2*1=11*5*9=495 ways after simplifying

why are there 9+4-1 elements ?

there are 9 elements; 1,2,3,4,5,6,7,8, and 9 but there are repetitions, so each digit can be used 4 times

you have 9 digits, 1-9, plus using any one digit 4 times gives 9+4=13 digits to choose from; however, whichever digit you choose, that digit is already in the group of 1 through 9 one time so subtract 1 from 13 to get 12

9+4-1=12

 

in the problem you are using n instead of any specific number

the formula is therefore C([n+r-1] choose r)

C([n+r-1] choose r)=(n+r-1)!/r!(n+r-1-r)!=(n+r-1)!/r!(n-1)!

(n+r-1)!/r!(n-1)!=(n+r-1)(n+r-2)(n+r-3)(n+r-4)...(n)/r!

 

Answer 2

The formula for combinations with repetition allowed is:

C(n+r−1,r)

In your case, you want to find the number of 4-tuples, so 4r=4. Therefore, the formula becomes:

(4−1,4)Simplifying, this is equivalent to:

C(n+3,4)

This formula represents the number of ways you can choose 4 elements with repetition allowed from a set of size 3n+3. Using this formula, you can calculate the number of 4-tuples for any positive integer n.