Cyclic Sequences: Counting and Equivalence

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

https://mediaspace.epfl.ch/media/0_3wvvka89

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (57)

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.

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.

Dirichlet convolution

In mathematics, the Dirichlet convolution is a binary operation defined for arithmetic functions; it is important in number theory. It was developed by Peter Gustav Lejeune Dirichlet. If are two arithmetic functions from the positive integers to the complex numbers, the Dirichlet convolution f ∗ g is a new arithmetic function defined by: where the sum extends over all positive divisors d of n, or equivalently over all distinct pairs (a, b) of positive integers whose product is n.

Incidence algebra

In order theory, a field of mathematics, an incidence algebra is an associative algebra, defined for every locally finite partially ordered set and commutative ring with unity. Subalgebras called reduced incidence algebras give a natural construction of various types of generating functions used in combinatorics and number theory. A locally finite poset is one in which every closed interval [a, b] = {x : a ≤ x ≤ b} is finite.

Arithmetic function

In number theory, an arithmetic, arithmetical, or number-theoretic function is for most authors any function f(n) whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their definition the requirement that an arithmetical function "expresses some arithmetical property of n". An example of an arithmetic function is the divisor function whose value at a positive integer n is equal to the number of divisors of n.