search
Log In
23 votes
2.1k views
  1. In how many ways can a given positive integer $n \geq 2$ be expressed as the sum of $2$ positive integers (which are not necessarily distinct). For example, for $n=3$, the number of ways is $2$, i.e., $1+2, 2+1$. Give only the answer without any explanation.
  2. In how many ways can a given positive integer $n \geq 3$ be expressed as the sum of $3$ positive integers (which are not necessarily distinct). For example, for $n=4$, the number of ways is $3$, i.e., $1+2+1, 2+1+1$. Give only the answer without explanation.
  3. In how many ways can a given positive integer $n \geq k$ be expressed as the sum of $k$ positive integers (which are not necessarily distinct). Give only the answer without explanation.
in Combinatory
edited by
2.1k views

7 Answers

38 votes
 
Best answer
  1. $n= 2 \left(1+1\right),\;n=3\left(1+2, 2+1\right),\\n=4\left(1+3,3+1,2+2\right),\;n=5\left(1+4,4+1,2+3,3+2\right)$
    so $x_1+x_2=n\;\text{and}\;x_1,x_2>{0}$ (no.of integral sol)
    This is same as number of ways of putting $\left(n-2\right)$  (as we can't have $0$ for either $x_1$ or $x_2$) identical balls into two distinct bins, which is obtained by putting a divider across $\left(n-2\right)$ balls and taking all possible permutations with $\left(n-2\right)$ being identical. i.e., $\frac{(n-2 + 1)!}{(n-2)!} = (n-1).$
    We can also use the following formula ,
    $^{(n-2+2-1)}C_{(2-1)}=^{n-1}C_1.$
     
  2. $n=3\left(1+1+1\right),\;n=4\left(1+1+2,1+2+1,2+1+1\right),\\ n=5\left(1+1+3,1+3+1,3+1+1,2+2+1,2+1+2,1+2+2\right) $
    so $x_1+x_2+x_3=n\;\text{and}\;x_1,x_2,x_3>0$ (no.of integral sol) 
    Here, we can permute $\left(n-3\right)$ items with $2$ dividers which will give $\frac{(n-3 + 2)!}{(n-3)!2!}$
    $\begin{align}&=\frac{\left(n-1\right)!}{\left(n-1-2\right)!2!}\\\\&=\;^{n-1}C_2\end{align}$
     
  3. $^{(n-k+k-1)}C_{k-1}=^{n-1}C_{k-1}.$

edited by
15

reference :

Theorem one

Suppose one has n objects (to be represented as stars; in the example below n = 7) to be placed into k bins (in the example k = 3), such that all bins contain at least one object; one distinguishes the bins (say they are numbered 1 to k) but one does not wish to distinguish the n stars (so configurations are only distinguished by the number of stars present in each bin; in fact a configuration is represented by a k-tuple of positive integers as in the statement of the theorem). Instead of starting to place stars into bins, one starts by placing the stars on a line:

★ ★ ★ ★ ★ ★ ★

Fig. 1: seven objects represented by stars

where the stars for the first bin will be taken from the left, followed by the stars for the second bin, and so forth. Thus the configuration will be determined once one knows what is the first star going to the second bin, and the first star going to the third bin, and so on. One can indicate this by placing k − 1 separating bars at some places between two stars; since no bin is allowed to be empty, there can be at most one bar between a given pair of stars:

★ ★ ★ ★ | | ★ ★

Fig. 2: two bars give rise to three bins containing 4, 1, and 2 objects

Thus one views the n stars as fixed objects defining n − 1 gaps, in each of which there may or not be one bar (bin partition). One has to choose k − 1 of them to actually contain a bar; therefore there are $ \tbinom {n-1}{k-1}$ possible configurations (see combination).

0
nice & simple......
11
$x_{1}+x_{2}= n$ where $x_{1},x_{2}> 0$ or $x_{1},x_{2} \geq 1$

So $x_{1}+1+x_{2}+1= n$

or, $x_{1}+x_{2}= n-2$

For those who r getting confused with n-2 .... like me :p
0
*best explanation @ supromit roy*
10

In simple words, We can think of expressing an integer $n$ as a sum of $k$ positive integers as dividing a queue of stars using $k-1$ bars and the number of stars in any partition give that positive number. 

$Example-  \ n = 5 \ k =3$
$\star \star | \star \star | \star  \rightarrow 5= 2+2+1$

In general, $n$ stars create $n-1$ gaps between them and we have to choose $k-1$ gaps for placing bars. 
                                                     $\Large\star \_ \star\_  \star\_  \star\_  \star$

This can be done in $\binom{n-1}{k-1}$ ways.

0
I am trying to solve this using gen functions.

x1+x2=n . An integer is divided into two boxes where each box will contain a number.

LHS= $(x+x^{2}+x^{3}+x^{4}+x^{5}....)(x+x^{2}+x^{3}+x^{4}+x^{5}....)$

$x(1+x+x^{2}+x^{3}+x^{4}) \times x(1+x+x^{2}+x^{3}+x^{4})$

$x(1-x)^{^-1} \times x(1-x)^{^-1}$

$x{^2}(1-x)^{-2}$

$x^{2} \prod_{r=0}^{\propto }\binom{r+2-1}{2-1}x^{r}$

$x^{2} \prod_{r=0}^{\propto }(r+1)x^{r}$

$\prod_{r=0}^{\propto }(r+1)x^{r+2}$

RHS =$[x^{n}]$

 

solving r I get  r=n-2.

So  coefficient of x^{n} would be n-1

 Is this correct way to do it as I have a doubt when I expand the gen function? Kindly help!!
0

@Debashish Deka sir, can you please help me generating functions in this case.

3 votes

We know that the no. of +ve integral solution to the equation $x_{1} + x_{2} + x_{3}+ ... + x_{k} = n$ is given by $\binom{n-1}{k-1}$.

(a) Let, $x_{1}$ and $x_{2}$ be the two positive integers (not necessarily distinct) such that their sum is equal to $n\ (n≥2)$.

Therefore, $x_{1} + x_{2} = n$. 

Now, we have to find all such values of $x_{1}$ and $x_{2}$ that satisfy the above equation. In other words, the problem basically reduces to  finding the no. of +ve integral solution to the above equation.

Therefore, the req. no. of ways is $\binom{n-1}{2-1} = \binom{n-1}{1}$. 

(b) Let, $x_{1}$, $x_{2}$ and $x_{3}$ be the three positive integers (not necessarily distinct) such that their sum is equal to $n\ (n≥3)$.

Therefore, $x_{1} + x_{2} + x_{3} = n$. 

Now, we have to find all such values of $x_{1}$, $x_{2}$ and $x_{3}$ that satisfy the above equation. In other words, the problem basically reduces to  finding the no. of +ve integral solution to the above equation.

Therefore, the req. no. of ways is $\binom{n-1}{3-1} = \binom{n-1}{2}$.

(c) Let, $x_{1}$, $x_{2}$, $x_{3}$,...,$x_{k}$ be the $k$ positive integers (not necessarily distinct) such that their sum is equal to $n\ (n≥k)$.

Therefore, $x_{1} + x_{2} + x_{3}+ ... + x_{k} = n$. 

Now, we have to find all such values of $x_{1}$, $x_{2}$, $x_{3}$,...,$x_{k}$ that satisfy the above equation. In other words, the problem basically reduces to  finding the no. of +ve integral solution to the above equation.

Therefore, the req. no. of ways is $\binom{n-1}{k-1}$.

      

0 votes

(a) Total no of ways = C(n-1 ,1) = n-1

(b)Total no of ways = C(n-1 ,n-3) = C(n-1 ,2) = (n-1)⨉(n-2) /2

(c)Total no of ways = C(n-k+k-1 ,n-k) = C(n-1 , n-k) = C(n-1 , k-1)

0 votes
Here what we have to do is

a) Let the 2 numbers is x1 and x2

    Now it is given that $x1+x2 \ge n$

    x1 and x2 can be anything greater than 0 such that $x1+x2 \ge n$

    minimum value of x1 and x2 is 1 so 1 is a value which is mandatory for x1 and x2

    so, $x1+x2 \ge n $ can be expressed as 10000.... no. of 0s in n-2 times 1 acts as a partition between x1 and x2 . so, no. of   

    ways =   $^{n-2+1}C_1 = n-1$

b) $x1+x2+x3\ge n$ for this it will be $^{n-3+2}C_{2} \implies ^{n-1}C_{2}$

c) similarly for k variables it will be $^{n-1}C_{k-1}$
0 votes
SIMPLY APPLY THE LOGIC:

x1+x2+x3+x4+...........xn=r   where x1,x2.....xn>=0    apply c(n+r-1,r)  

make similarly all the 3 cases in order that it satisfies the equation

a-  x1+x2=n where x1,x2>=1 so make it x1+x2=n-2 now x1,x2>=0 so c(n-2+2-1,1)=n-1

b-x1+x2+x3=n where x1,x2,x3>=1 so x1+x2+x3=n-3 so c(n-3+3-1,2)=c(n-1,2)

c-x1+x2+.....xk=n where x1,x2,x3....xk>=n so x1+x2+x3+....xk=n-k=c(n-k+k-1,k-1)=c(n-1,k-1)
0 votes

For Distinct  k positive integers : (n+k-1)C(k-1)

For Non-Distinct  k positive integers : (n-1)C(k-1)

0 votes

Here, i solved for the generalized case i.e. part c of the question.

 

 

 

 

 

 

 

ago

Related questions

17 votes
3 answers
1
1.5k views
How many distinct ways are there to split $50$ identical coins among three people so that each person gets at least $5$ coins? $3^{35}$ $3^{50}-2^{50}$ $\binom{35}{2}$ $\binom{50}{15} \cdot 3^{35}$ $\binom{37}{2}$
asked Dec 21, 2016 in Combinatory jothee 1.5k views
23 votes
3 answers
2
1.4k views
There is a set of $2n$ people: $n$ male and $n$ female. A good party is one with equal number of males and females (including the one where none are invited). The total number of good parties is. $2^{n}$ $n^{2}$ $\binom{n}{⌊n/2⌋}^{2}$ $\binom{2n}{n}$ None of the above.
asked Dec 5, 2015 in Combinatory makhdoom ghaya 1.4k views
20 votes
5 answers
3
1.3k views
There are $n$ kingdoms and $2n$ champions. Each kingdom gets $2$ champions. The number of ways in which this can be done is: $\frac{\left ( 2n \right )!}{2^{n}}$ $\frac{\left ( 2n \right )!}{n!}$ $\frac{\left ( 2n \right )!}{2^{n} . n!}$ $\frac{n!}{2}$ None of the above.
asked Nov 4, 2015 in Combinatory makhdoom ghaya 1.3k views
30 votes
11 answers
4
4.1k views
In how many ways can we distribute $5$ distinct balls, $B_1, B_2, \ldots, B_5$ in $5$ distinct cells, $C_1, C_2, \ldots, C_5$ such that Ball $B_i$ is not in cell $C_i$, $\forall i= 1,2,\ldots 5$ and each cell contains exactly one ball? $44$ $96$ $120$ $3125$
asked Nov 2, 2014 in Combinatory Ishrat Jahan 4.1k views
...