Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I need to solve the problem,

How many sequence of integers ($j_1 , j_2 , . . . , j_k$) are there such that $0 ≤ j_1 ≤ j_2 ≤ . . . ≤ j_k ≤ n$?

I've been given a hint,

(Hint: Reduce the problem to $0 < j_1 < j_2 < . . . < j_k < n)$.

The answer will be in terms of k and n.

First of all, I don't see how to reduce the problem, or what to do when it's reduced. Secondly, I feel bad about not having much to show for my effort, but I have been working on this problem for some time and I'm not sure where to start. If someone could give me a general outline of what method to use or something like that, I'd appreciate it.

share|improve this question
    
See also math.stackexchange.com/questions/119144/…. –  joriki Mar 15 '12 at 13:14
add comment

4 Answers 4

up vote 4 down vote accepted

Consider

$y_i = j_i + i$.

Show that the $y_i$ are distinct and in the range $1$ to $n+k$.

How many ways can you choose the $y$?

share|improve this answer
    
While the other answers were explained nicely, this was concisely stated, clever, and left me enough room to think and truly understand the answer without being too vague. Thanks. –  gsingh2011 Mar 8 '12 at 17:04
    
@gsingh2011: You are welcome! Glad to have helped. –  Aryabhata Mar 8 '12 at 17:16
add comment

We have $k$ people lined up in a row, and $n$ identical candies. We will give away some or all of the candies to the people, perhaps giving no candies to some of them, or maybe even all of them. And we will eat any candies that are left over. Think of our representative as being at the end of the row; so (s)he is the $(k+1)$-th person.

Let $j_1$ be the number of candies given to the first person, $j_2$ the number of candies given to the first two people, $j_3$ the number of candies given to the first three people, and so on up to $j_k$. Then any sequence $j_1 \le j_2\le \cdots\le j_k\le n$ identifies uniquely a candy giveaway scheme, and conversely any candy giveaway scheme produces a sequence of the type we are interested in.

So we ask: how many ways are there to give away $n$ candies to $k+1$ people?

There is a standard argument for this, often called Stars and Bars. It is easier to visualize giving away $n+k+1$ candies to $k+1$ people, at least one to each, and then taking away a candy from everyone. So there are just as many ways to distribute $n$ candies among $k+1$ people, with some possibly getting nothing, as there are ways to distribute $n+k+1$ candies among $k+1$ people, with everybody getting at least $1$.

Line up the $n+k+1$ candies, with a little gap between successive candies. There are $n+k$ such gaps. Put $k$ separators between the candies, and give all the candies up to the first separator to the first person, then all the candies between the first separator and the next one to the second person, and so on. There are $$\binom{n+k}{k}$$ ways to choose where the separators will go.

share|improve this answer
    
I got lost when you went from n candies to n+k+1 candies. Can you explain that? –  gsingh2011 Mar 8 '12 at 16:58
    
We are trying to solve the problem of distributing $n$ candies to $k+1$ people, where some of the people might get no candies. It is easier to imagine giving out $n+k+1$ candies, at least one to each person, and then taking away $1$ candy from each person. There is thus a one to one correspondence between the distribution patterns for $n$ candies, with each person getting $\ge 0$ candies, and the distribution paterns for $n+k+1$ candies, with $\ge 1$ for each person. –  André Nicolas Mar 8 '12 at 17:12
add comment

Aryabhata’s already suggested an approach that uses the hint. I think that a somewhat different approach is simpler.

Let $d_0=j_1$, for $i=1,\dots,k-1$ let $d_i=j_{i+1}-j_i$, and let $d_k=n-j_k$. The numbers $d_0,\dots,d_k$ are non-negative, and $d_0+d_1+\dots+d_k=n$.

Conversely, if $\langle d_0,\dots,d_k\rangle$ is any $(k+1)$-tuple of non-negative integers whose sum is $n$, we can define $j_1=d_0$ and $j_{i+1}=d_i+j_i$ for $i=1,\dots,k-1$, and the $k$-tuple $\langle j_1,\dots,j_k\rangle$ clearly satisfies the condition $$0\le j_1\le j_2\le \dots\le j_k\le n\;.$$

Thus, you need only count the $(k+1)$-tuples $\langle d_0,\dots,d_k\rangle$ of non-negative integers such that $$\sum_{i=0}^kd_i=n\;,$$ which is a standard problem.

share|improve this answer
add comment

Consider paths from $(0,0)$ to $(k,n)$ that increase one of the two components on each step, so they make $n+k$ steps, among which $k$ horizontal (increasing $i$ in $(i,j)$) and $n$ vertical (increasing $j$).

There are $\binom{n+k}k$ such paths.

Let the first point with first coordinate $i$ be $(i,j_i)$ for $i=1,\ldots,k$, then clearly $0\leq j_1\leq\cdots\leq j_k\leq n$. Moreover all such sequences of values are allowed, and they determine the path: the horizontal steps are precisely those from $(i-1,j_i)$ to $(i,j_i)$ for $i=1,\ldots,k$.

Other points of view. If you take $y_i$ to be the index of the horizontal step to $(i,j_i)$ among all steps (which are numbered from $1$ to $n+k$), you'll get your $0<y_1<\cdots<y_k\leq n+k$. If you put a candy (star) at each point $(i,j)$ of the path and think of each horizontal step as a separation (bar), you'll have split your $n+k+1$ candies into $k+1$ vertical groups (for $i=0,1,\ldots,k$) the last group $i=k$ being the left-overs. But actually you want each group to have as many candies as it has vertical steps, not points, so you remove one from each group to correct this fencepost error, leaving groups of vertical steps of sizes $d_0,d_1,\ldots,d_k$ (each $d_i\geq0$), with $d_0+\cdots+d_k=n$. In the end you might just as well take $n+k$ steps, choose $k$ of them to be horizontal (bars) and the remaining $n$ to be vertical (stars). But I think I already said something similar at the beginning.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.