Suppose $A$ is a finite alphabet. Let's call a word $w \in A^*$ $n$ -universal iff it contains every word from $A^n$ as a subword. What is the minimal possible length of an $n$-universal word over $A$? $|A| = m$.  It is definitely $\geq m^n + n - 1$ , because a word of length $m \geq n$ has $m - n + 1$ subwords of length $n$.   I think, that $|A|^n + n - 1$ is quite likely to be the exact answer, but do not know how to prove it.   It holds, however, for the following particular cases:  $m = 1$: $a^n$  $n = 2, m = 2$: $abbaa$  $n = 3, m = 2$: $abbbaaabab$  $n = 2, m = 3$: $ccacaabbcba$
2528
Suppose you have a computer with a password of length $k$ in an alphabet of $n$ letters.  You can write an arbitrarly long word and the computer will try all the subwords of $k$ consecutive letters. What is the smallest word that contains all combinations of $k$ letters as subword? (i.e. the fastest way to hack the computer :) )  The smallest word that contains $n^k$ subwords of size $k$ has length $k-1+n^k$ and based on some easy cases, we would like to prove that it is in fact possible to find a word of such length that contains all possible passwords. The problem can be translated into a problem in graph theory, by taking as vertices all words of length $k$.  We tried $k=2$, where you can prove the conjecture by induction. For $n=2$ and small $k$ it also works.
115815
Given a finite sequence of decimal digits $a_1,a_2,...,a_n$ prove that there exists a natural number $m$ such that decimal representation of $2^m$ starts with that sequence of digits.  Thanks for your help :)
90501
As the title suggests, could anyone either provide me with or direct me to a proof that affine n-space $\mathbb{A}^n$ is irreducible, without using the Nullstellensatz?   This is an exercise in a second course on representation theory, so if there is a reasonably palatable representation-theoretic proof then that's probably what's expected but on the other hand it may just be totally unrelated but presented for the reader's enjoyment. (I'm under no obligation to do it so I wouldn't class it as 'homework'.)  I have spent some time banging my head against the exercise but to no avail, I keep just coming back to the Nullstellensatz proof I already know. As well as a representation-theoretic proof if one exists, any alternative, particularly beautiful proofs would be welcomed for their own sake. Many thanks for the help!
12430
Let $\mathbb{F}_{27}$ denote the finite field of size 27. For each $\alpha\in\mathbb{F}_{27}$ , define $ A_{\alpha}$ $=$ { $ 1, 1+\alpha , 1+\alpha+{\alpha}^2 , 1+\alpha+{\alpha}^2+{\alpha}^3 , .... $} . Then  prove that  the number of  $\alpha\in\mathbb{F}_{27}$ such that $|A_\alpha|$=26 equals 12.  $ 0\in A_\alpha $ if and only if $\alpha\neq 0$ For the first proof , the multiplicative group of the field $\mathbb{F}_{27}$ is cyclic and its order is 26  , so there are 12 generators in that group.   Now  I need  to  show  that  $ 1+\alpha+{\alpha}^2+.. {\alpha}^{25} $ =0  , where order of $\alpha$=26 . Since   $\alpha ^{26}$ =1 ($\alpha$-1)(1+$\alpha$+${\alpha}^2$+...+${\alpha}^{25}$)=0 , since $\alpha\neq 1$  , So $ 1+\alpha+...+{\alpha}^{25} $ =0 My question is , can I write these last two  lines?  I mean are those two lines alright to write? If those two lines are invalid then I need some help to show  $ 1+\alpha+{\alpha}^2+..+{\alpha}^{25} $=0  .Thanks
99462
Ten different letters of alphabet are given, words with $5$ letters are formed from these given letters. Then, what is the number of words which have at least one letter repeated?    Well I do understand some part of the question. The only confusing thing is that if we had chosen different letters of alphabet, how can we form words which have the letters repeated.  For the record, I am new to permutation and combination, so please put the explanation to the most basic level.
104423
We consider strings of $n$ characters, each character being $a$, $b$, $c$, or $d$, that contain an even number of $a$'s. (Recall that $0$ is even.) Let $E_n$ be the number of such strings.      Prove that for any integer $n \ge1$,      $$E_{n+1} = 2  E_n + 4^n.$$   I tried to do induction. I got stuck.  $$\begin{align}E_{n+2} &amp;= 2  E_{n+1} + 4^{n+1}\\ &amp;       = 2  (2E_n + 4^n) + 4^{n+1}\\ &amp;        = 4E_n + 2\cdot 4^n + 4^{n+1}\end{align}$$ Then I got lost.
91440
How many words can be formed from the word 'alpha'? The letter 'a' may be used twice but the other letters may only be used once.  There are no restrictions on whether or not they're real words, just combinations of letters. So, I need to add together:  $5$ letter words $+$ $4$ letter words $+$ $3$ letter words $+$ $2$ letter words $+$ $1$ letter words  There are, $(5!/2!)=60$, 5 letter words. 120 total but then we divide out by duplicate words because we have two a's.  $1$ letter words $=4$  The part I am having trouble with is the duplication of 'a'. I can't seem to figure out how to find $2,3,$ and $4$ letter words. For 2 letter words, there were so few examples I just wrote them out and saw that there were 13. So,  $(5!/3!)-[(2!)3+1]=13$  20 possibilities and then we need to subtract out the ones that contain 2 of p,l, and h, as well as the second aa.  I'm having a hard time believing my work for 2 letter words is accurate and attempting to do 3 and 4 letter words suggests that it isn't. Let me know if there is anything I can to do clear up what is being asked. Thanks in advanced.
109177
Say a sequence $\{X_1, X_2,\ldots ,X_n\}$ is given, where $X_p$ is either one or zero ($0 &lt; p &lt; n$). How can I determine the number of strings, which do contain at least one occurrence of consequent $1$'s of length $k$ ($0 &lt; k &lt; n$).   For example, a string $\{1, 0, 1, 1, 1, 0\}$ is such a string for $n = 6$ and $k = 3$.   I have found an answer for arbitrary $n$ and $k = 2$, ($k = 1$ is trivial), but I need a more general answer for any natural number  $k$ smaller than $n$.
106353
I am very confused about how to interpret the following.  If we write $\{0,1\}^{+}$=$\cup_{n \in \mathbb{N}} \{0,1\}^{n}$  then I am told that elements  of $\{0,1\}^{+}$ are called words and subsists of it are called languages,  Then I was asked,   if we consider $$g: P( \{0,1\}^{+}) \to P( \{0,1\}^{+})$$ defined as  $g(X)=X \cup \{w01:w \in X\} \cup \{\tau\}$  where $\tau$ represents the word of zero length, then find the least fixed point of g ordered by inclusion.  I have been trying to make sense of it but cant make progress. I know that a fixed point is an element $X$ such that $g(X)=X$  I know that since we want the least, the fixed point has to be less then any other fixed points ordered by inclusion to.  Can anyone help to make sense of this? Thank you
44337
Firstly I pick a language $xyz$ where $x = \epsilon$, $y = (abb)^{k}$, $z = (bba)^{k}$ where $|y| \ge$ the number of states in the automaton representing my language. Then $xyz = (abb)^k(bba)^k$ is a palindrome.  Now I split $y$ into $uvw$, where $v \ne \epsilon$ contains a state visited more  than once. If the language is regular then $xuv^iwz$ is within the language $\forall i \ge 0$.  I choose $i = 2$, then $uv^2w = (abb)^n$ where $n &gt; k$.  Then $xuv^2wz = (abb)^n(bba)^k$ where $n &gt; k$, which is not a palindrome.   Firstly, is my reasoning for this particular proof correct?  I'm unsure about how to properly apply the pumping lemma to this problem. And secondly the question asks me to state a proof for palindromes in general, whereas I only attempted to prove it for a single case. Is there an example I can choose which proves the conjecture for all palindromes? I assume not, seeing as I can't think of how that could be represented using regular expressions.
24436
Today in Coding/Cryptography class, we were talking about basic definitions, and the professor mentioned that for a set $A=\left \{ \left. a, b, \dots, z \right \} \right.$ (the alphabet) we can define a set $A^{*}=\left \{ \left. a, ksdjf, blocks, coffee, maskdj, \dots, asdlkajsdksjfs \right \} \right.$ (words) as a set that consists of all finite sequences of the elements/letters from our $A$/alphabet. My question is, is this set $A^{*}$ countably or uncountably infinite? Does it matter how many letters there are in your alphabet? If it was, say, $A=\left \{ \left. a \right \} \right.$, then the words in $A^{*}$ would be of form $a, aa, aaa, \dots$ which, I think, would allow a bijection $\mathbb{N} \to A^{*}$ where an integer would signify the number of a's in a word. Can something analogous be done with an alphabet that consists of 26 letters (Latin alphabet), or can countability/uncountability be proved otherwise? And as mentioned before, I am wondering if the number of elements in the alphabet matters, or if all it does is change the formula for a bijection.   P.S. Now that I think of it, maybe we could biject from $\underset{n}{\underbrace{\mathbb{N}\times\mathbb{N}\times\mathbb{N}\times\dots\times\mathbb{N}}}$ to some set of words $A^{*}$ whose alphabet $A$ has $n$ elements? Thanks!
8584
Given a string:  $AABBC=A^2B^2C^1$   I am trying to find the Total Permutations (this may be incorrect):  $\dfrac{5!}{2!\cdot2!}=30$  My question is how would I find the partial sums (perhaps the wrong choice in words) when added together would give an index such that:   $AABBC=1$ $ABABC=2$ $CBABA=29$ $CBBAA=30$   (30 might be the wrong number here but is suppose to be the last)   I have tried to draw out a tree structure to get an idea and thought with as the minimum:  $CAABB$  $4(\dfrac{4!}{2!\cdot2!})$ + 1  And:  $CABAB$  I would get something like:  $4(\dfrac{4!}{2!\cdot2!}) + 0 + 1(\dfrac{2!}{2!}) + 0 + 0$  But I am missing something here. How would I find the sums needed for $BACAB$ ?  More specifically I am trying to find the index of a word that is arbitrarily long in alphanumeric.  So the string may also be something like:  $AAAAABBBBDDEEFFFGGGGGHIIIIJJJJKLMOOOPZZZZZ$
76774
How many words can be formed, each of $2$ vowels and $3$ consonants from letters of the word "DAUGHTER"  What my textbook has done: it has first taken combinations of vowels and then consonants then multiplied them altogether. Now for each combination of words they can be shuffled in $5!$ ways, so multipliying by $5!$ we get the required answer.   My question is: why has the book  used combinations instead of permutations while selecting vowels and consonants?  Thanks.
42272
Q: How many arrangements of a,a,a,b,b,b,c,c,c are there such that  $\hspace{5mm}$ (i). no three consecutive letters are the same?  $\hspace{5mm}$ (ii). no two consecutive letters are the same?  A:(i). 1314. ${\hspace{5mm}}$ (ii). 174.  I thought of using the General Principle of Inclusion and Exclusion along with letting $p_i$ denote a property that.. , and doing so, I will evaluate $E(0)$, which gives us the number of arrangements without any of the properties.   How do I go about doing that? I am trying to use the method stated above in solving this question, but I am unable to generalize the properties $p_i$.
59822
What is the number of automorphisms (including identity) for permutation group $S_3$ on 3 letters?  I believe the answer for this is 6. As we can write the group elements as below   (a)(b)(C) (ab)(c) (ac)(b) (bc)(a) (abc) (bac)   Can we generalize that for any $S_n$ onto $n$ the number of automorphisms will be $n!$ Also I cannot find this anywhere in my text, can we have a permutation $S_n$ onto $m$ where $n\neq m$? (for eg: is it possible to have a permutation group say $S_5$ on say 2 elements?)
113586
The answer is 2454, apparently. I am getting 1446, however. Can anyone point out my error ?  We need to partition the solution into the mutually exclusive cases of choices of 4 letters where we have no repetitions (e.g. MATH), where we have one repetition (e,g, MATT) and where we have two repetitions (e.g. MMTT). Then we compute the corresponding number of perms of each case, and add, thus:  We have 8 unique letters, so we can make 8C4 selections with no repetitions.  We have 3 pairs of repetitions {MM, AA, TT} which gives us 3 * 7C2 choices with one repetition, since having chosen, say, MM, we need to select 2 more letters from the remaining 7 unique letters.  We have 3C2 choices with 2 repetitions taken from the set {MM, AA, TT}  So our total number of perms is:  (#choices of 4, no reps * 4!) + (#choices of 4, 1 rep * 4!/2!) + (#choices of 4, 2 reps * 4!/(2!2!) ) = (8C4 * 24) + (3 * 7C2 * 12) + (3C2 * 6) = 672 + 756 + 18 = 1446  Where did I go wrong ?
95877
I have no clue how to begin these problems. How do I start? I don't think I should pound em out...Thanks.  Let P be the set of $42^{\text{nd}}$ roots of unity, and let Q be the set of $70^{\text{th}} $ roots of unity. How many elements do P and Q have in common?  Let P be the set of $42^{\text{nd}} $roots of unity, and let Q be the set of $70^{\text{th}} $roots of unity. What is the smallest positive integer n for which all the elements in P and all the elements in Q are $n^{\text{th}}$ roots of unity?