Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Les principaux objectifs de ce travail sont de présenter les notions d’équivalence et de complexité k-binomiales, ainsi qu’étudier quelques problèmes qui y sont directement liés.

Rappelons tout d’abord que deux mots finis u et v sur un alphabet A sont k-binomialement équivalents si, pour tout mot w de longueur au plus k, le coefficient binomial de u et w (comptant le nombre d’occurrences de w comme sous-mot de u) est égal au coefficient binomial de v et w.

Après avoir introduit la notion d’équivalence k-binomiale et avoir donné une borne asymptotique sur le nombre maximal de classes d’équivalence parmi les facteurs de longueur n d’un mot donné, nous présentons la notion de complexité k-binomiale d’un mot infini. Il s’agit d’une application associant à chaque naturel n le nombre de facteurs de longueur n dans le mot x, à équivalence k-binomiale près. Ensuite, nous étudions cette complexité sur les mots sturmiens qui sont les mots apériodiques de complexité factorielle minimale. Nous montrons une définition équivalente des mots sturmiens : il s’agit de l’ensemble des mots infinis apériodiques et équilibrés. Utilisant cette seconde définition, nous pouvons montrer que les mots sturmiens ont une complexité k-binomiale égale à leur 
complexité factorielle : p(n)=n+1, pout tout k>1.

Dans ce travail sont également étudiés les mots infinis points fixes de morphismes Parikh-constants, c’est-à-dire de morphismes pour lesquels les images de chaque lettre sont égales à permutation près. Il est possible de montrer que la complexité k-binomiale de tels mots est bornée, pour tout naturel k. Nous essayons ensuite de calculer la complexité k-binomiale du mot de Thue-Morse. Ce travail n’a pas été mené auparavant et nous essayons, conjointement avec Michel Rigo et Julien Leroy, de prouver la conjecture 
affirmant que le nombre de facteurs de longueur n, à équivalence k-binomiale près, vaut 3.2^k-3 ou 3.2^k-4, en fonction de la valeur de n modulo 2^k.

Le chapitre suivant étudie la cardinalité minimale d’un alphabet permettant de construire un mot infini ne comportant pas de carré 2-binomial, c’est-à-dire de mot de la forme u.v où u et v sont 2-binomialement équivalents. Nous effectuons ensuite le même travail pour trouver un mot évitant les cubes 2-binomiaux.

Enfin, le dernier chapitre propose un algorithme polynomial testant si deux mots finis sont k-binomialement équivalents ou non. Cet algorithme associe à chaque mot u un automate à multiplicités qui accepte exactement les sous-mots de u. Il est ensuite possible de vérifier en temps polynomial si deux automates sont équivalents. The main goals of this work are to present the notions of k-binomial equivalence, k-binomial complexity and to study some problems directly connected. 

Let us recall that two finite words u and v over an alphabet A are k-binomially equivalent if, for all words w of length up to k, the binomial coefficient of u and w – counting the number of occurrences of w as a subword of u – equals the binomial coefficient of v and w.

After having introduced k-binomial equivalence and having established an asymptotic bound on the maximal number of k-binomial classes among factors of length n of an infinite word x, I present the notion of k-binomial complexity of an infinite word x which is a map that associates with each positive integer n the number of factors of length n in the word x, up to k-binomial equivalence. Then I study this complexity on Sturmian words which are aperiodic words with the least factor complexity. I show in this master thesis an equivalent definition for Sturmian words: these words are the set of aperiodic and balanced infinite words. Using that alternative definition, I am able to show that k-binomial complexity of Sturmian words equals their factor complexity p(n)=n+1, for all k>1. 

In this master thesis, I am also interested in infinite words that are fixed points of a Parikh-constant morphism, that is, a morphism for which images of all letters are equal, up to permutation. It is possible to show that for such words, their k-binomial complexity is bounded for every k>0. After that general fact, I try to compute the complexity for the Thue-Morse word t=0110100110010110…. That work has never been carried on before and, working in collaboration with Michel Rigo and Julien Leroy, we are trying to solve the conjecture stating that, for every k>1, the number of factors of length n in t, up to k-binomial equivalence, equals 3.2^k-3 or 3.2^k-4, depending on the value of n modulo 2^k.

The next chapter of my master thesis presents the minimal cardinality of an alphabet allowing the explicit construction of an infinite word avoiding 2-binomial squares, that is, factors of the form u.v such that u and v are 2-binomially equivalent. Then I carry on the same work trying this time to avoid 2-binomial cubes.

Finally, the last chapter gives a polynomial-time algorithm testing if two finite words are k-binomially equivalent or not. This algorithm builds, for every word u, an automaton with multiplicities for which accepting paths are exactly labelled by subwords of u. The remaining problem is to decide if two automata with multiplicities are equivalent. I show that this problem is solvable in polynomial-time.

combinatoire --- mots --- complexité --- coefficient binomial --- combinatorics --- words --- complexity --- binomial coefficient --- Physique, chimie, mathématiques & sciences de la terre > Mathématiques

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

We use addition on a daily basis-yet how many of us stop to truly consider the enormous and remarkable ramifications of this mathematical activity? Summing It Up uses addition as a springboard to present a fascinating and accessible look at numbers and number theory, and how we apply beautiful numerical properties to answer math problems. Mathematicians Avner Ash and Robert Gross explore addition's most basic characteristics as well as the addition of squares and other powers before moving onward to infinite series, modular forms, and issues at the forefront of current mathematical research.Ash and Gross tailor their succinct and engaging investigations for math enthusiasts of all backgrounds. Employing college algebra, the first part of the book examines such questions as, can all positive numbers be written as a sum of four perfect squares? The second section of the book incorporates calculus and examines infinite series-long sums that can only be defined by the concept of limit, as in the example of 1+1/2+1/4+. . .=? With the help of some group theory and geometry, the third section ties together the first two parts of the book through a discussion of modular forms-the analytic functions on the upper half-plane of the complex numbers that have growth and transformation properties. Ash and Gross show how modular forms are indispensable in modern number theory, for example in the proof of Fermat's Last Theorem.Appropriate for numbers novices as well as college math majors, Summing It Up delves into mathematics that will enlighten anyone fascinated by numbers.

Number theory. --- Mathematics --- Number study --- Numbers, Theory of --- Algebra --- Absolute value. --- Addition. --- Analytic continuation. --- Analytic function. --- Automorphic form. --- Axiom. --- Bernoulli number. --- Big O notation. --- Binomial coefficient. --- Binomial theorem. --- Book. --- Calculation. --- Chain rule. --- Coefficient. --- Complex analysis. --- Complex number. --- Complex plane. --- Computation. --- Congruence subgroup. --- Conjecture. --- Constant function. --- Constant term. --- Convergent series. --- Coprime integers. --- Counting. --- Cusp form. --- Determinant. --- Diagram (category theory). --- Dirichlet series. --- Division by zero. --- Divisor. --- Elementary proof. --- Elliptic curve. --- Equation. --- Euclidean geometry. --- Existential quantification. --- Exponential function. --- Factorization. --- Fourier series. --- Function composition. --- Fundamental domain. --- Gaussian integer. --- Generating function. --- Geometric series. --- Geometry. --- Group theory. --- Hecke operator. --- Hexagonal number. --- Hyperbolic geometry. --- Integer factorization. --- Integer. --- Line segment. --- Linear combination. --- Logarithm. --- Mathematical induction. --- Mathematician. --- Mathematics. --- Matrix group. --- Modular form. --- Modular group. --- Natural number. --- Non-Euclidean geometry. --- Parity (mathematics). --- Pentagonal number. --- Periodic function. --- Polynomial. --- Power series. --- Prime factor. --- Prime number theorem. --- Prime number. --- Pythagorean theorem. --- Quadratic residue. --- Quantity. --- Radius of convergence. --- Rational number. --- Real number. --- Remainder. --- Riemann surface. --- Root of unity. --- Scientific notation. --- Semicircle. --- Series (mathematics). --- Sign (mathematics). --- Square number. --- Square root. --- Subgroup. --- Subset. --- Sum of squares. --- Summation. --- Taylor series. --- Theorem. --- Theory. --- Transfinite number. --- Triangular number. --- Two-dimensional space. --- Unique factorization domain. --- Upper half-plane. --- Variable (mathematics). --- Vector space.

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

An engaging collection of intriguing problems that shows you how to think like a mathematical physicistPaul Nahin is a master at explaining odd phenomena through straightforward mathematics. In this collection of twenty-six intriguing problems, he explores how mathematical physicists think. Always entertaining, the problems range from ancient catapult conundrums to the puzzling physics of a very peculiar kind of glass called NASTYGLASS-and from dodging trucks to why raindrops fall slower than the rate of gravity. The questions raised may seem impossible to answer at first and may require an unexpected twist in reasoning, but sometimes their solutions are surprisingly simple. Nahin's goal, however, is always to guide readers-who will need only to have studied advanced high school math and physics-in expanding their mathematical thinking to make sense of the curiosities of the physical world.The problems are in the first part of the book and the solutions are in the second, so that readers may challenge themselves to solve the questions on their own before looking at the explanations. The problems show how mathematics-including algebra, trigonometry, geometry, and calculus-can be united with physical laws to solve both real and theoretical problems. Historical anecdotes woven throughout the book bring alive the circumstances and people involved in some amazing discoveries and achievements.More than a puzzle book, this work will immerse you in the delights of scientific history while honing your math skills.

Mathematics --- Almost surely. --- Ambiguity. --- Antiderivative. --- Approximation error. --- Arthur C. Clarke. --- Binomial coefficient. --- Binomial theorem. --- Birthday problem. --- Calculation. --- Cauchy–Schwarz inequality. --- Center of mass (relativistic). --- Centrifugal force. --- Closed-form expression. --- Coefficient. --- Combination. --- Computational problem. --- Conjecture. --- Continued fraction. --- Contradiction. --- Coprime integers. --- Counterexample. --- Crossover distortion. --- Cubic function. --- Derivative. --- Detonation. --- Diameter. --- Dimensional analysis. --- Dirac delta function. --- Disquisitiones Arithmeticae. --- Dissipation. --- Energy level. --- Enola Gay. --- Equation. --- Error. --- Expected value. --- Fermat's Last Theorem. --- Fictitious force. --- G. H. Hardy. --- Geometry. --- Googol. --- Gravitational constant. --- Gravity. --- Grayscale. --- Harmonic series (mathematics). --- Hypotenuse. --- Instant. --- Integer. --- Inverse-square law. --- Irrational number. --- MATLAB. --- Mass ratio. --- Mathematical joke. --- Mathematical physics. --- Mathematical problem. --- Mathematician. --- Mathematics. --- Mean value theorem. --- Metric system. --- Minicomputer. --- Monte Carlo method. --- Natural number. --- Oliver Heaviside. --- Paul J. Nahin. --- Pauli exclusion principle. --- Periodic function. --- Phase transition. --- Prime factor. --- Prime number. --- Probability theory. --- Probability. --- Projectile. --- Pure mathematics. --- Quadratic equation. --- Quadratic formula. --- Quantity. --- Quantum mechanics. --- Quintic function. --- Random number. --- Random search. --- Random walk. --- Remainder. --- Resistor. --- Richard Feynman. --- Right angle. --- Second derivative. --- Simulation. --- Slant range. --- Small number. --- Special case. --- Square root. --- Summation. --- The Drunkard's Walk. --- Theorem. --- Thermodynamic equilibrium. --- Thought experiment. --- Trepidation (astronomy). --- Uniform distribution (discrete). --- Upper and lower bounds. --- Weightlessness. --- Zero of a function.