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.

Say I have a sentence consisting of n words.

That word can be

I like horse and I also like cats and kitten.

I want to compute the number of sequential words.

For example,

I, Like, Horse, are phrases with one word.

I Like, Like Horse, Horse and, are phrases with two words.

The total number of such phrases should be

n + (n-1) + (n-2) + ... +1

There are n phrases with 1 word, (n-1) phrases with 2 words, and 1 phrase with n words. So there are n sets and each set contain on average (n+1)/2 words.

So total there is n(n+1)/2 such phrases.

Say I want to limit the number of such sequences.

For example, do not compute every such sequences but only sequences less or equal to k.

For example, k =2 we got

I, Like, Horse, are phrases with one word.

I Like, Like Horse, Horse and, are phrases with one word.

I like Horse, like horse and, and everything else doesn't count.

So we got k sets and the number of element in each sets are n, n-1, n-2, ... n-k+1

When k=2, for example, we stop at n-1.

Hence the total number of such phrases are

k*(n+n-k+1)/2 = k*(2n-k+1)/2

I think my math so far is correct. When n is equal to k, it reduces to our previous formula of (n)(n+1)/2, when k is equal to 1, it reduces to simply n.

Now works on the formula we got

k*(2n-k+1)/2 = (2nk - k^2 +k)/2 = nk - .5*(k^2 +k)

Now this gets a little unintuitive.

Naturally we will think that the higher the k, the more phrases we have.

Yet the coefficient of k^2 is negative. It seems to me at some point, the higher the k, the less phrases we get.

How do we reconcile this problem?

share|improve this question
1  
First, in your last formula, the $k$ should be $-k$. Second, in context, $k$ can't be any bigger than $n$, and it's only when $k$ exceeds $n$ that your (corrected) formula starts giving smaller answers. –  Gerry Myerson Feb 11 '13 at 4:57
add comment

1 Answer

Notice that $nk > k^2$ since $n>k$, this is the principal term and it is increasing in $k$.

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.