Another question on Permutation and Combination.

[cooldudeachyut]

Question - The number 3 can be written as 3, 2+1, 1+2, 1+1+1 in four ways. In how many ways can the number n be written as?

My attempt - I think that the solution should be the number of positive integral solutions of the equation x₁+x₂+x₃+ ..... + x_n = n

Where,
0<=x₁<=n
0<=x₂<=n
0<=x₃<=n
.
.
.
0<=x_n<=n

which is ^2n-1C_n(and obviously wrong because it doesn't work for 3, but why? ).

The answer in my textbook is given 2^n-1. Help.

 

[pka]

Question - The number 3 can be written as 3, 2+1, 1+2, 1+1+1 in four ways. In how many ways can the number n be written as?
The answer in my textbook is given 2^n-1. Help.

First some comments. This kind of problem is thoroughly discussed in Mathematics of Choice by Niven.
There is a chapter on Integer Partitions. Now as noted there it is usual not to consider order as a factor. That is, 2+1 & 1+2 are the same partition. BUT in your question order is considered.

In the positive integers the equation \(\displaystyle x_1+x_2+\cdots+x_j=K \) has \(\displaystyle \dbinom{(K-j)+(j-1)}{j-1} \) for \(\displaystyle 1\le j\le K \) solutions.
EXAMPLE: \(\displaystyle K=10~\&~j=4 \) means \(\displaystyle x_1+x_2+x_3+x_4=10 \) has \(\displaystyle \dbinom{9}{3} \)
positive integral solutions.
So to find the total number for \(\displaystyle 10 \) is \(\displaystyle \displaystyle\sum\limits_{k = 1}^{10} {\dbinom{9}{k-1}} \)

Look at this table. Your text book is correct.

Show that \(\displaystyle \displaystyle\sum\limits_{k = 1}^{N} {\dbinom{N-1}{N-k}}=2^{N-1} \)

 

[cooldudeachyut]

First some comments. This kind of problem is thoroughly discussed in Mathematics of Choice by Niven.
There is a chapter on Integer Partitions. Now as noted there it is usual not to consider order as a factor. That is, 2+1 & 1+2 are the same partition. BUT in your question order is considered.

In the positive integers the equation \(\displaystyle x_1+x_2+\cdots+x_j=K \) has \(\displaystyle \dbinom{(K-j)+(j-1)}{j-1} \) for \(\displaystyle 1\le j\le K \) solutions.
EXAMPLE: \(\displaystyle K=10~\&~j=4 \) means \(\displaystyle x_1+x_2+x_3+x_4=10 \) has \(\displaystyle \dbinom{9}{3} \)
positive integral solutions.
So to find the total number for \(\displaystyle 10 \) is \(\displaystyle \displaystyle\sum\limits_{k = 1}^{10} {\dbinom{9}{k-1}} \)

Look at this table. Your text book is correct.

Show that \(\displaystyle \displaystyle\sum\limits_{k = 1}^{N} {\dbinom{N-1}{N-k}}=2^{N-1} \)

Thanks. Also, I should have written "non-negative integral solutions" instead of "positive integral solutions"(my bad, and still wrong).