find the number of possible ordered k-tuples of non negative integers (n1,n2,n3 ....) such that ∑ni =100 i=1 to k

To find the number of possible ordered k-tuples of non-negative integers \( (n_1, n_2, n_3, \ldots, n_k) \) such that the sum of these integers equals 100, we can use a combinatorial method known as the "stars and bars" theorem. This theorem is particularly useful for distributing indistinguishable objects (in this case, the total sum of 100) into distinguishable boxes (the k different variables). Let's break this down step by step.

Understanding the Problem

We want to determine how many ways we can assign values to \( n_1, n_2, \ldots, n_k \) such that:

• Each \( n_i \) is a non-negative integer.
• The sum \( n_1 + n_2 + n_3 + \ldots + n_k = 100 \).

Applying the Stars and Bars Theorem

The stars and bars theorem states that if we have \( n \) indistinguishable objects (stars) to place into \( k \) distinguishable boxes (the variables), the number of ways to do this is given by the formula:

C(n + k - 1, k - 1)

where \( C \) represents the binomial coefficient, which counts the number of ways to choose \( k - 1 \) dividers (bars) from \( n + k - 1 \) total positions (stars plus bars).

Setting Up Our Equation

In our case:

• The total number of stars is 100 (the total sum we want).
• The number of boxes is \( k \) (the number of variables).

Thus, we need to find:

C(100 + k - 1, k - 1)

Calculating the Binomial Coefficient

The binomial coefficient \( C(n, r) \) is calculated using the formula:

C(n, r) = n! / (r! * (n - r)!)

For our specific case, we substitute \( n = 100 + k - 1 \) and \( r = k - 1 \):

C(100 + k - 1, k - 1) = (100 + k - 1)! / ((k - 1)! * (100)!)

Example Calculation

Let’s say we want to find the number of ordered pairs (k = 2). We would compute:

C(100 + 2 - 1, 2 - 1) = C(101, 1) = 101

This means there are 101 different ways to assign non-negative integer values to \( n_1 \) and \( n_2 \) such that their sum equals 100.

Generalizing the Result

In summary, for any positive integer \( k \), the number of ordered k-tuples of non-negative integers that sum to 100 is:

C(100 + k - 1, k - 1)

This formula allows you to compute the number of combinations for any value of \( k \) you choose, providing a powerful tool for solving similar problems in combinatorics.