Questions about combinatorics on languages of words, that is how many sequences of symbols with certain properties there are.

learn more… | top users | synonyms

3
votes
1answer
15 views

Lexicographical position of a string in its type class

I have the following problem: Given a string $x\in\{1,...,M\}^+$ of length $n$. Let $S$ be the set of all words with exactly the same numbers of occurences of smybols as in $x$. In fact, $S$ consists ...
2
votes
2answers
97 views

How Dynamic programming can be used for Coin Change problem?

As far as I can unserstand Dynamic programming stands simply for memoization (which is a fancy name for lazy evaluation or plain "caching"). Now, I read that there is we can reduce complexity of ...
1
vote
1answer
75 views

The language of all borderless words

Could anyone help me please to find who was the first person who has proved that the language of all borderless words is not regular and when was that? Could you mention the reference, please? A word ...
6
votes
4answers
191 views

What is the number of expressions containing n pairs of matching brackets with nesting limit?

I know the answer without nesting limit is the Catalan number. My question is, specifically, is there a recurrence relation that gives the number of expression containing $n$ pairs of matching ...
3
votes
2answers
2k views

Finding the number of distinct permutations of length N with n different symbols

I have one puzzle whose answer I have boiled down to finding the total number and which type of permutation they are. For example if the string is of length ten as $w = aabbbaabba$, the total number ...
7
votes
2answers
275 views

How many strings are close to a given set of strings?

This question has been prompted by Efficient data structures for building a fast spell checker. Given two strings $u,v$, we say they are $k$-close if their Damerau–Levenshtein distance¹ is small, ...
6
votes
1answer
175 views

What is a formula for the number of strings with no repeats?

I want to count the number of strings $s$ over a finite alphabet $A$, that contain no repeats, and by that I mean for any substring $t$ of $s$, $1< |t| < |s|$, there is no disjoint copy of $t$ ...
12
votes
2answers
458 views

Number of words of a given length in a regular language

Is there an algebraic characterization of the number of words of a given length in a regular language? Wikipedia states a result somewhat imprecisely: For any regular language $L$ there exist ...
10
votes
3answers
429 views

Number of words in the regular language $(00)^*$

According to Wikipedia, for any regular language $L$ there exist constants $\lambda_1,\ldots,\lambda_k$ and polynomials $p_1(x),\ldots,p_k(x)$ such that for every $n$ the number $s_L(n)$ of words of ...
14
votes
1answer
345 views

Does every large enough string have repeats?

Let $\Sigma$ be some finite set of characters of fixed size. Let $\alpha$ be some string over $\Sigma$. We say that a nonempty substring $\beta$ of $\alpha$ is a repeat if $\beta = \gamma \gamma$ for ...