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.

Let there be a set containing the following digits: {1,2,3,4,5,6,7,8,9}.

If I choose 5 digit blocks, where the digits are arrange in consecutive ascending order, then the following blocks are possible:

1) 12345
2) 23456
3) 34567
4) 45678
5) 56789

I can intuitively see the pattern, and come up with the following expression to get the number of blocks in a set of digits (where n is number of digits in the set, and k is the number of digits in a block): (n+1)-k.

How can I prove this general equation to be true for all sets and blocks, regardless of their size? In other words, how do I derive this expression analytically rather than intuitively?

share|improve this question
1  
Not meaning to be cute, but I think you derive it intuitively and prove it analytically. –  oks Apr 1 '13 at 18:19
    
Is there a formal name for this kind of problem -- searching online for "combination of increasing consecutive digits" hasn't yielded much? –  Vilhelm Gray Apr 23 '13 at 21:08
add comment

2 Answers

up vote 1 down vote accepted

Consider a set $\{a_0,a_1,a_2....,a_n\}$ to be grouped into $k$ digit ordered blocks where $k<n$.

The first trivial group is $\{a_0,a_1,a_2,...a_k\}$

Each successive group would remove an element from the previous group and add a new element from the residual group $\mathbb{R} = \{a_0,a_1,a_2....,a_n\} - \{a_0,a_1,a_2,...a_k\}$ whereas $|\mathbb{R}| = n-k$. For example, the next group would be

$$\{a_0,a_1,a_2,...a_k\} - \{a_0\} + \{a_{k+1}\}$$

As you can only add elements from the set $\mathbb{R}$, so you can only add $|\mathbb{R}| = n-k$ elements to create new blocks.

So no of blocks you can create is $|\mathbb{R}| + 1= n-k + 1 = (n+1) - k$, including the trivial starting block

share|improve this answer
add comment

To prove it analytically, you just spell out what you've already observed. E.g. you could introduce another symbol where $p$ is the position of the first element of the block, counting from position 1 to position $n$. You could call $l$ the position of the last element in the block.

Since the block has $k$ elements, $l = p + k -1$.

Since the right hand end of the block has to be contained in the set, $l \le n \Rightarrow p \le n + 1 - k$.

But also $p \ge 1$ since the left hand end of the block has to be contained in the set as well.

Apart from those two constraints, $p$ can be anything. So $p$ can be $1, 2, ... n + 1 -k$.

Since $p$ refers to the first element of the block, and the first block starts at position $1$, $p$ can serve as a counter for the number of blocks in the set; the last block in the set has $p = n + 1 - k$ and corresponds to the total number of blocks in the set.

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.