Lecture

Cyclic Sequences: Counting and Equivalence

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Description

This lecture covers the definition of linear sequences in an alphabet, the concept of equivalence relation for linear sequences, and the notion of cyclic sequences with periods. It explains how to count the number of linear and cyclic sequences of a certain length and period in an alphabet. The lecture also introduces the Mobius inversion formula for computing the total number of cyclic sequences. Examples and exercises are provided to illustrate the concepts and techniques discussed.

Official source

Related concepts (19)

Alphabet

An alphabet is a standardized set of basic written graphemes (called letters) representing phonemes, units of sounds that distinguish words, of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syllable, and logographic systems use characters to represent words, morphemes, or other semantic units. The Egyptians have created the first alphabet in a technical sense.

Möbius inversion formula

In mathematics, the classic Möbius inversion formula is a relation between pairs of arithmetic functions, each defined from the other by sums over divisors. It was introduced into number theory in 1832 by August Ferdinand Möbius. A large generalization of this formula applies to summation over an arbitrary locally finite partially ordered set, with Möbius' classical formula applying to the set of the natural numbers ordered by divisibility: see incidence algebra.

Latin alphabet

The Latin alphabet, also known as the Roman alphabet, is the collection of letters originally used by the ancient Romans to write the Latin language. Largely unaltered with the exception of extensions (such as diacritics), it forms the Latin script that is used to write many modern European languages, including English. With modifications, it is also used for other alphabets, such as the Vietnamese alphabet. Its modern repertoire is standardised as the ISO basic Latin alphabet.

Möbius function

The Möbius function μ(n) is a multiplicative function in number theory introduced by the German mathematician August Ferdinand Möbius (also transliterated Moebius) in 1832. It is ubiquitous in elementary and analytic number theory and most often appears as part of its namesake the Möbius inversion formula. Following work of Gian-Carlo Rota in the 1960s, generalizations of the Möbius function were introduced into combinatorics, and are similarly denoted μ(x). For any positive integer n, define μ(n) as the sum of the primitive nth roots of unity.

Phoenician alphabet

The Phoenician alphabet is an alphabet (more specifically, an abjad) known in modern times from the Canaanite and Aramaic inscriptions found across the Mediterranean region. The name comes from the Phoenician civilization. The Phoenician alphabet is also called the Early Linear script (in a Semitic context, not connected to Minoan writing systems), because it is an early development of the Proto- or Old Canaanite or Proto-Sinaitic script, into a linear, purely alphabetic script, also marking the transfer from a multi-directional writing system, where a variety of writing directions occurred, to a regulated horizontal, right-to-left script.

Related lectures (29)

Operations on Formal Languages

Explores formal language operations, including concatenation, union, intersection, and Kleene star for language repetition.

Möbius inversion formula

Covers the Möbius inversion formula and its proof, including the change of variables in summation.

Voristicand Characterization of KL Divergences

Explores exploration bias and generalization bound in KL divergences, emphasizing mathematical proofs and implications.

Möbius inversion: posets

Covers the Möbius inversion for posets, defining partially ordered sets and explaining the incidence algebra.

Arithmetic Functions: Multiplicative Functions and Dirichlet Convolution

Covers multiplicative functions, Dirichlet convolution, and the Mobius function in arithmetic functions.

Related concepts (19)

Alphabet

Möbius inversion formula

Latin alphabet

Möbius function

Phoenician alphabet