0

Consider a distinct set $S = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ from which we want to take three elements in strictly ascending order. These are the possibilities:

  • $(1, 2, 3)$
  • $(2, 3, 4)$
  • $(3, 4, 5)$
  • $(4, 5, 6)$
  • $(5, 6, 7)$
  • $(6, 7, 8)$
  • $(7, 8, 9)$

So in total there are six possible combinations.

How would you get to this result without brute force?

I already checked the search for similar questions but only find ones which just check for ascending order (e.g. $(1, 2, 4)$ is allowed too) but leave a note if I missed one.

bodokaiser
  • 575

2 Answers2

2

Look at the lowest digit: your list goes from $(1,2,3)$ to $(7,8,9)$ so there should be $7$ possibilities.

Generalising this slightly to selection of $k$ consecutive terms from the first $n$ positive integers, there are $n-k+1$ possibilities. In this particular example $n=9$ and $k=3$.

Henry
  • 157,058
  • did you derive this solution from the Stars and Bars mentioned by John? If not from where did you derive it? – bodokaiser Mar 16 '15 at 12:39
  • 2
    @bodokaiser Observe that if you have a string of $k$ consecutive digits in a set of $n$ digits, the first digit can be at most $n + 1 - k$. In your example, since you have a string of $3$ consecutive digits in a set of $9$ digits, the largest number with which your string can begin is $9 + 1 - 3 = 7$. Since the smallest string begins with $1$, there are $n + 1 - k$ possible strings. I think John Hughes was trying to solve a more general problem. – N. F. Taussig Mar 16 '15 at 12:46
1

The usual name for such problems is "stars and bars": think of a list like this:

**|**|**

where each bar means "select this element" and each star means "omit this one", and you apply this rule to the sorted sequence of elements. What you do is look at "runs" of stars. Write down the length of each run, and when you're done, you have a sequence of nonnegative numbers that adds up to $k$.

See Stars and Bars Combinatorics for detailed answers on how to solve such problems.

As requested, a detailed example: Let's look at four items, in ascending order, and we pick two. The possible picks, represented with stars and bars, are

**||
*|*|
*||*
|**| 
|*|*
||**

There are six of these. You can see, from this picture, that this also corresponds to a typical "put items in bins" problem by treating the bars as sides of the bins. In the first situation, two stars are in the left bin; in the next, there's a star in the left and middle bin, and so on.

The "second stars and bars theorem" tells us that for $n$ objects in $k$ bins, some of which may be empty, the number of choices is $n+k-1 \choose k-1$. In our case, we have 2 objects in 3 bins, and get $4 \choose 2 = 6$.

Now see if you can apply this to your problem.

John Hughes
  • 93,729
  • doesn't Stars and Bars only apply to permutations? Could you give a calculation example? – bodokaiser Mar 16 '15 at 12:04
  • shouldn't the answer set of your example be **||, |**|, ||** if considering consecutive order? – bodokaiser Mar 16 '15 at 12:41
  • @bodokaiser: those correspond to the selections 12, 23, and 34, and my answer also allows 13, 14, and 24, which were allowed by your original question as asked (although your example suggested you either hadn't thought of them, or didn't want to allow them). – John Hughes Mar 16 '15 at 13:01