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

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.

1. 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.

2. 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

Let $|T| = n$. Then
1. 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}$.
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. $\frac{3\times 4}{2} = 6$
2. $\frac{3\times 4^2}{2} -\frac{3\times 4 \times 7}{6} = 24 - 14 = 10$