Cardinality of ordered n-grams and subsets of those n-grams from a given set [closed]

Question

Given a set T={A,B,C}, I need to know the cardinality of all ordered sequential n-grams and the total cardinality of all subsets of those n-grams.

The ordered sequential n-grams of the set T above are {{A},{B},{C},{A,B},{B,C},{A,B,C}} and its cardinality is 6.
The total cardinality of all subsets for those n-grams is sum(1,1,1,2,2,3)=10

So, given set T, what are the formulae for #1 and #2?

Your "ordered sequential n-grams" appear to be simply "subsets". Is that what you intended? — j_random_hacker, Sep 21 '17 at 19:53
Yes! Some background: I use those terms because I am trying to solve this in the context of a lookup for full-text search. We have a string and break it into n-grams and then search those. We need to know the total number tokens that get searched when the number of terms in the query is high, and optimize. — binarymax, Sep 21 '17 at 21:39
@j_random_hacker, not exactly. If $ABC$ is a string then the asker considers only nonempty substrings of $ABC$, namely $A,B,C, AB, BC, $ and $ABC$. The problem statement of course needs better wording. — fade2black, Sep 22 '17 at 6:23
@evil - I find it strange that this question was closed, considering the commentary was clearly understood and the question answered. Please be specific on what further clarity you require. — binarymax, Oct 31 '17 at 20:45

fade2black · Accepted Answer · 2017-09-22 06:14:11Z

Let $|T| = n$. Then

the number of $n$-symbol sequences is $1$, the number of $(n-1)$-symbol sequences is $2$, $\dots$, the number of $1$-symbol sequences is $n$. Thus the number of all ordered sequential $n$-grams is $1+2+\dots + n = \frac{n(n+1)}{2}$.
The total cardinality of all subsets for those $n$-grams is $$\sum_{k=1}^nk(n-k+1) = (n+1)\sum_{k=1}^nk - \sum_{k=1}^n k^2 = \frac{n(n+1)^2}{2} - \frac{n(n+1)(2n+1)}{6}$$

For $n=3$ we have

1 Answer 1