# How to determine the number of 5 consecutive digit blocks in a set of digits?

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?

-
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

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

-

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.

-