1.
Catalan number
–
In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects. They are named after the Belgian mathematician Eugène Charles Catalan, using zero-based numbering, the nth Catalan number is given directly in terms of binomial coefficients by C n =1 n +1 =. = ∏ k =2 n n + k k for n ≥0, an alternative expression for Cn is C n = − =1 n +1 for n ≥0, which is equivalent to the expression given above because = n n +1. This shows that Cn is an integer, which is not immediately obvious from the first formula given and this expression forms the basis for a proof of the correctness of the formula. They also satisfy, C0 =1 and C n +1 =2 n +2 C n, which can be a more efficient way to calculate them. Asymptotically, the Catalan numbers grow as C n ∼4 n n 3 /2 π in the sense that the quotient of the nth Catalan number, some sources use just C n ≈4 n n 3 /2. The only Catalan numbers Cn that are odd are those for which n = 2k −1, the only prime Catalan numbers are C2 =2 and C3 =5. The Catalan numbers have an integral representation C n = ∫04 x n ρ d x where ρ =12 π4 − x x and this means that the Catalan numbers are a solution of the Hausdorff moment problem on the interval instead of. The orthogonal polynomials having the weight function ρ on are H n = ∑ k =0 n k, there are many counting problems in combinatorics whose solution is given by the Catalan numbers. The book Enumerative Combinatorics, Volume 2 by combinatorialist Richard P. Stanley contains a set of exercises which describe 66 different interpretations of the Catalan numbers, following are some examples, with illustrations of the cases C3 =5 and C4 =14. Cn is the number of Dyck words of length 2n, a Dyck word is a string consisting of n Xs and n Ys such that no initial segment of the string has more Ys than Xs. For n =3, for example, we have the five different parenthesizations of four factors. It follows that Cn is the number of binary trees with n +1 leaves. Cn is the number of lattice paths along the edges of a grid with n × n square cells. A monotonic path is one which starts in the left corner, finishes in the upper right corner. Counting such paths is equivalent to counting Dyck words, X stands for move right, the following hexagons illustrate the case n =4, Cn is the number of stack-sortable permutations of. These are the permutations that avoid the pattern 231, Cn is the number of permutations of that avoid the pattern 123, that is, the number of permutations with no three-term increasing subsequence. For n =3, these permutations are 132,213,231,312 and 321
2.
Pascal's triangle
–
In mathematics, Pascals triangle is a triangular array of the binomial coefficients. In the Western world, it is named after French mathematician Blaise Pascal, although other mathematicians studied it centuries before him in India, Persia, China, Germany, the rows of Pascals triangle are conventionally enumerated starting with row n =0 at the top. The entries in each row are numbered from the beginning with k =0 and are usually staggered relative to the numbers in the adjacent rows. The triangle may be constructed in the manner, In row 0. Each entry of each subsequent row is constructed by adding the number above and to the left with the number above and to the right, treating blank entries as 0. For example, the number in the first row is 1. The entry in the nth row and kth column of Pascals triangle is denoted, for example, the unique nonzero entry in the topmost row is =1. With this notation, the construction of the previous paragraph may be written as follows, = +, for any integer n. This recurrence for the coefficients is known as Pascals rule. Pascals triangle has higher dimensional generalizations, the three-dimensional version is called Pascals pyramid or Pascals tetrahedron, while the general versions are called Pascals simplices. The pattern of numbers that forms Pascals triangle was known well before Pascals time, centuries before, discussion of the numbers had arisen in the context of Indian studies of combinatorics and of binomial numbers and Greeks study of figurate numbers. From later commentary, it appears that the coefficients and the additive formula for generating them. Halayudha also explained obscure references to Meru-prastaara, the Staircase of Mount Meru, in approximately 850, the Jain mathematician Mahāvīra gave a different formula for the binomial coefficients, using multiplication, equivalent to the modern formula = n. r. At around the time, it was discussed in Persia by the Persian mathematician. It was later repeated by the Persian poet-astronomer-mathematician Omar Khayyám, thus the triangle is referred to as the Khayyam triangle in Iran. Several theorems related to the triangle were known, including the binomial theorem, Khayyam used a method of finding nth roots based on the binomial expansion, and therefore on the binomial coefficients. Pascals triangle was known in China in the early 11th century through the work of the Chinese mathematician Jia Xian, in the 13th century, Yang Hui presented the triangle and hence it is still called Yang Huis triangle in China. In the west, the binomial coefficients were calculated by Gersonides in the early 14th century, petrus Apianus published the full triangle on the frontispiece of his book on business calculations in 1527
3.
Natural number
–
In mathematics, the natural numbers are those used for counting and ordering. In common language, words used for counting are cardinal numbers, texts that exclude zero from the natural numbers sometimes refer to the natural numbers together with zero as the whole numbers, but in other writings, that term is used instead for the integers. These chains of extensions make the natural numbers canonically embedded in the number systems. Properties of the numbers, such as divisibility and the distribution of prime numbers, are studied in number theory. Problems concerning counting and ordering, such as partitioning and enumerations, are studied in combinatorics, the most primitive method of representing a natural number is to put down a mark for each object. Later, a set of objects could be tested for equality, excess or shortage, by striking out a mark, the first major advance in abstraction was the use of numerals to represent numbers. This allowed systems to be developed for recording large numbers, the ancient Egyptians developed a powerful system of numerals with distinct hieroglyphs for 1,10, and all the powers of 10 up to over 1 million. A stone carving from Karnak, dating from around 1500 BC and now at the Louvre in Paris, depicts 276 as 2 hundreds,7 tens, and 6 ones, and similarly for the number 4,622. A much later advance was the development of the idea that 0 can be considered as a number, with its own numeral. The use of a 0 digit in place-value notation dates back as early as 700 BC by the Babylonians, the Olmec and Maya civilizations used 0 as a separate number as early as the 1st century BC, but this usage did not spread beyond Mesoamerica. The use of a numeral 0 in modern times originated with the Indian mathematician Brahmagupta in 628, the first systematic study of numbers as abstractions is usually credited to the Greek philosophers Pythagoras and Archimedes. Some Greek mathematicians treated the number 1 differently than larger numbers, independent studies also occurred at around the same time in India, China, and Mesoamerica. In 19th century Europe, there was mathematical and philosophical discussion about the nature of the natural numbers. A school of Naturalism stated that the numbers were a direct consequence of the human psyche. Henri Poincaré was one of its advocates, as was Leopold Kronecker who summarized God made the integers, in opposition to the Naturalists, the constructivists saw a need to improve the logical rigor in the foundations of mathematics. In the 1860s, Hermann Grassmann suggested a recursive definition for natural numbers thus stating they were not really natural, later, two classes of such formal definitions were constructed, later, they were shown to be equivalent in most practical applications. The second class of definitions was introduced by Giuseppe Peano and is now called Peano arithmetic and it is based on an axiomatization of the properties of ordinal numbers, each natural number has a successor and every non-zero natural number has a unique predecessor. Peano arithmetic is equiconsistent with several systems of set theory
4.
Combinatorics
–
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Many combinatorial questions have historically been considered in isolation, giving an ad hoc solution to a problem arising in some mathematical context. In the later twentieth century, however, powerful and general methods were developed. One of the oldest and most accessible parts of combinatorics is graph theory, Combinatorics is used frequently in computer science to obtain formulas and estimates in the analysis of algorithms. A mathematician who studies combinatorics is called a combinatorialist or a combinatorist, basic combinatorial concepts and enumerative results appeared throughout the ancient world. Greek historian Plutarch discusses an argument between Chrysippus and Hipparchus of a rather delicate enumerative problem, which was shown to be related to Schröder–Hipparchus numbers. In the Ostomachion, Archimedes considers a tiling puzzle, in the Middle Ages, combinatorics continued to be studied, largely outside of the European civilization. The Indian mathematician Mahāvīra provided formulae for the number of permutations and combinations, later, in Medieval England, campanology provided examples of what is now known as Hamiltonian cycles in certain Cayley graphs on permutations. During the Renaissance, together with the rest of mathematics and the sciences, works of Pascal, Newton, Jacob Bernoulli and Euler became foundational in the emerging field. In modern times, the works of J. J. Sylvester and Percy MacMahon helped lay the foundation for enumerative, graph theory also enjoyed an explosion of interest at the same time, especially in connection with the four color problem. In the second half of the 20th century, combinatorics enjoyed a rapid growth, in part, the growth was spurred by new connections and applications to other fields, ranging from algebra to probability, from functional analysis to number theory, etc. These connections shed the boundaries between combinatorics and parts of mathematics and theoretical science, but at the same time led to a partial fragmentation of the field. Enumerative combinatorics is the most classical area of combinatorics and concentrates on counting the number of combinatorial objects. Although counting the number of elements in a set is a rather broad mathematical problem, fibonacci numbers is the basic example of a problem in enumerative combinatorics. The twelvefold way provides a framework for counting permutations, combinations and partitions. Analytic combinatorics concerns the enumeration of combinatorial structures using tools from complex analysis, in contrast with enumerative combinatorics, which uses explicit combinatorial formulae and generating functions to describe the results, analytic combinatorics aims at obtaining asymptotic formulae. Partition theory studies various enumeration and asymptotic problems related to integer partitions, originally a part of number theory and analysis, it is now considered a part of combinatorics or an independent field. It incorporates the bijective approach and various tools in analysis and analytic number theory, graphs are basic objects in combinatorics
5.
Exponentiation
–
Exponentiation is a mathematical operation, written as bn, involving two numbers, the base b and the exponent n. The exponent is usually shown as a superscript to the right of the base, Some common exponents have their own names, the exponent 2 is called the square of b or b squared, the exponent 3 is called the cube of b or b cubed. The exponent −1 of b, or 1 / b, is called the reciprocal of b, when n is a positive integer and b is not zero, b−n is naturally defined as 1/bn, preserving the property bn × bm = bn + m. The definition of exponentiation can be extended to any real or complex exponent. Exponentiation by integer exponents can also be defined for a variety of algebraic structures. The term power was used by the Greek mathematician Euclid for the square of a line, archimedes discovered and proved the law of exponents, 10a 10b = 10a+b, necessary to manipulate powers of 10. In the late 16th century, Jost Bürgi used Roman numerals for exponents, early in the 17th century, the first form of our modern exponential notation was introduced by Rene Descartes in his text titled La Géométrie, there, the notation is introduced in Book I. Nicolas Chuquet used a form of notation in the 15th century. The word exponent was coined in 1544 by Michael Stifel, samuel Jeake introduced the term indices in 1696. In the 16th century Robert Recorde used the square, cube, zenzizenzic, sursolid, zenzicube, second sursolid. Biquadrate has been used to refer to the power as well. Some mathematicians used exponents only for greater than two, preferring to represent squares as repeated multiplication. Thus they would write polynomials, for example, as ax + bxx + cx3 + d, another historical synonym, involution, is now rare and should not be confused with its more common meaning. In 1748 Leonhard Euler wrote consider exponentials or powers in which the exponent itself is a variable and it is clear that quantities of this kind are not algebraic functions, since in those the exponents must be constant. With this introduction of transcendental functions, Euler laid the foundation for the introduction of natural logarithm as the inverse function for y = ex. The expression b2 = b ⋅ b is called the square of b because the area of a square with side-length b is b2, the expression b3 = b ⋅ b ⋅ b is called the cube of b because the volume of a cube with side-length b is b3. The exponent indicates how many copies of the base are multiplied together, for example,35 =3 ⋅3 ⋅3 ⋅3 ⋅3 =243. The base 3 appears 5 times in the multiplication, because the exponent is 5
6.
On-Line Encyclopedia of Integer Sequences
–
The On-Line Encyclopedia of Integer Sequences, also cited simply as Sloanes, is an online database of integer sequences. It was created and maintained by Neil Sloane while a researcher at AT&T Labs, Sloane continues to be involved in the OEIS in his role as President of the OEIS Foundation. OEIS records information on integer sequences of interest to professional mathematicians and amateurs, and is widely cited. As of 30 December 2016 it contains nearly 280,000 sequences, the database is searchable by keyword and by subsequence. Neil Sloane started collecting integer sequences as a student in 1965 to support his work in combinatorics. The database was at first stored on punched cards and he published selections from the database in book form twice, A Handbook of Integer Sequences, containing 2,372 sequences in lexicographic order and assigned numbers from 1 to 2372. The Encyclopedia of Integer Sequences with Simon Plouffe, containing 5,488 sequences and these books were well received and, especially after the second publication, mathematicians supplied Sloane with a steady flow of new sequences. The collection became unmanageable in book form, and when the database had reached 16,000 entries Sloane decided to go online—first as an e-mail service, as a spin-off from the database work, Sloane founded the Journal of Integer Sequences in 1998. The database continues to grow at a rate of some 10,000 entries a year, Sloane has personally managed his sequences for almost 40 years, but starting in 2002, a board of associate editors and volunteers has helped maintain the database. In 2004, Sloane celebrated the addition of the 100, 000th sequence to the database, A100000, in 2006, the user interface was overhauled and more advanced search capabilities were added. In 2010 an OEIS wiki at OEIS. org was created to simplify the collaboration of the OEIS editors and contributors, besides integer sequences, the OEIS also catalogs sequences of fractions, the digits of transcendental numbers, complex numbers and so on by transforming them into integer sequences. Sequences of rationals are represented by two sequences, the sequence of numerators and the sequence of denominators, important irrational numbers such as π =3.1415926535897. are catalogued under representative integer sequences such as decimal expansions, binary expansions, or continued fraction expansions. The OEIS was limited to plain ASCII text until 2011, yet it still uses a form of conventional mathematical notation. Greek letters are represented by their full names, e. g. mu for μ. Every sequence is identified by the letter A followed by six digits, sometimes referred to without the leading zeros, individual terms of sequences are separated by commas. Digit groups are not separated by commas, periods, or spaces, a represents the nth term of the sequence. Zero is often used to represent non-existent sequence elements, for example, A104157 enumerates the smallest prime of n² consecutive primes to form an n×n magic square of least magic constant, or 0 if no such magic square exists. The value of a is 2, a is 1480028129, but there is no such 2×2 magic square, so a is 0
7.
Square number
–
In mathematics, a square number or perfect square is an integer that is the square of an integer, in other words, it is the product of some integer with itself. For example,9 is a number, since it can be written as 3 × 3. The usual notation for the square of a n is not the product n × n. The name square number comes from the name of the shape, another way of saying that a integer is a square number, is that its square root is again an integer. For example, √9 =3, so 9 is a square number, a positive integer that has no perfect square divisors except 1 is called square-free. For a non-negative integer n, the nth square number is n2, the concept of square can be extended to some other number systems. If rational numbers are included, then a square is the ratio of two integers, and, conversely, the ratio of two square integers is a square, e. g.49 =2. Starting with 1, there are ⌊√m⌋ square numbers up to and including m, the squares smaller than 602 =3600 are, The difference between any perfect square and its predecessor is given by the identity n2 −2 = 2n −1. Equivalently, it is possible to count up square numbers by adding together the last square, the last squares root, and the current root, that is, n2 =2 + + n. The number m is a number if and only if one can compose a square of m equal squares. Hence, a square with side length n has area n2, the expression for the nth square number is n2. This is also equal to the sum of the first n odd numbers as can be seen in the above pictures, the formula follows, n 2 = ∑ k =1 n. So for example,52 =25 =1 +3 +5 +7 +9, there are several recursive methods for computing square numbers. For example, the nth square number can be computed from the square by n2 =2 + + n =2 +. Alternatively, the nth square number can be calculated from the two by doubling the th square, subtracting the th square number, and adding 2. For example, 2 × 52 −42 +2 = 2 × 25 −16 +2 =50 −16 +2 =36 =62, a square number is also the sum of two consecutive triangular numbers. The sum of two square numbers is a centered square number. Every odd square is also an octagonal number
8.
Cube (algebra)
–
In arithmetic and algebra, the cube of a number n is its third power, the result of the number multiplied by itself twice, n3 = n × n × n. It is also the number multiplied by its square, n3 = n × n2 and this is also the volume formula for a geometric cube with sides of length n, giving rise to the name. The inverse operation of finding a number whose cube is n is called extracting the cube root of n and it determines the side of the cube of a given volume. It is also n raised to the one-third power, both cube and cube root are odd functions,3 = −. The cube of a number or any other mathematical expression is denoted by a superscript 3, a cube number, or a perfect cube, or sometimes just a cube, is a number which is the cube of an integer. The perfect cubes up to 603 are, Geometrically speaking, an integer m is a perfect cube if and only if one can arrange m solid unit cubes into a larger. For example,27 small cubes can be arranged into one larger one with the appearance of a Rubiks Cube, the difference between the cubes of consecutive integers can be expressed as follows, n3 −3 = 3n +1. There is no minimum perfect cube, since the cube of an integer is negative. For example, −4 × −4 × −4 = −64, unlike perfect squares, perfect cubes do not have a small number of possibilities for the last two digits. Except for cubes divisible by 5, where only 25,75 and 00 can be the last two digits, any pair of digits with the last digit odd can be a perfect cube. With even cubes, there is considerable restriction, for only 00, o2, e4, o6, some cube numbers are also square numbers, for example,64 is a square number and a cube number. This happens if and only if the number is a perfect sixth power, the last digits of each 3rd power are, It is, however, easy to show that most numbers are not perfect cubes because all perfect cubes must have digital root 1,8 or 9. That is their values modulo 9 may be only −1,1 and 0, every positive integer can be written as the sum of nine positive cubes. The equation x3 + y3 = z3 has no solutions in integers. In fact, it has none in Eisenstein integers, both of these statements are also true for the equation x3 + y3 = 3z3. The sum of the first n cubes is the nth triangle number squared,13 +23 + ⋯ + n 3 =2 =2. Proofs Charles Wheatstone gives a simple derivation, by expanding each cube in the sum into a set of consecutive odd numbers. Indeed, he begins by giving the identity n 3 = + + + ⋯ + ⏟ n consecutive odd numbers, kanim provides a purely visual proof, Benjamin & Orrison provide two additional proofs, and Nelsen gives seven geometric proofs
9.
Binomial coefficient
–
In mathematics, any of the positive integers that occurs as a coefficient in the binomial theorem is a binomial coefficient. Commonly, a coefficient is indexed by a pair of integers n ≥ k ≥0 and is written. It is the coefficient of the xk term in the expansion of the binomial power n. The value of the coefficient is given by the expression n. k, arranging binomial coefficients into rows for successive values of n, and in which k ranges from 0 to n, gives a triangular array called Pascals triangle. The properties of binomial coefficients have led to extending the definition to beyond the case of integers n ≥ k ≥0. Andreas von Ettingshausen introduced the notation in 1826, although the numbers were known centuries earlier, the earliest known detailed discussion of binomial coefficients is in a tenth-century commentary, by Halayudha, on an ancient Sanskrit text, Pingalas Chandaḥśāstra. In about 1150, the Indian mathematician Bhaskaracharya gave an exposition of binomial coefficients in his book Līlāvatī, alternative notations include C, nCk, nCk, Ckn, Cnk, and Cn, k in all of which the C stands for combinations or choices. Many calculators use variants of the C notation because they can represent it on a single-line display, in this form the binomial coefficients are easily compared to k-permutations of n, written as P, etc. For natural numbers n and k, the binomial coefficient can be defined as the coefficient of the monomial Xk in the expansion of n, the same coefficient also occurs in the binomial formula, which explains the name binomial coefficient. This shows in particular that is a number for any natural numbers n and k. Most of these interpretations are easily seen to be equivalent to counting k-combinations, several methods exist to compute the value of without actually expanding a binomial power or counting k-combinations. It also follows from tracing the contributions to Xk in n−1, as there is zero Xn+1 or X−1 in n, one might extend the definition beyond the above boundaries to include =0 when either k > n or k <0. This recursive formula then allows the construction of Pascals triangle, surrounded by white spaces where the zeros, or the trivial coefficients, a more efficient method to compute individual binomial coefficients is given by the formula = n k _ k. = n ⋯ k ⋯1 = ∏ i =1 k n +1 − i i and this formula is easiest to understand for the combinatorial interpretation of binomial coefficients. The numerator gives the number of ways to select a sequence of k distinct objects, retaining the order of selection, the denominator counts the number of distinct sequences that define the same k-combination when order is disregarded. Due to the symmetry of the binomial coefficient with regard to k and n−k, calculation may be optimised by setting the limit of the product above to the smaller of k. This formula follows from the formula above by multiplying numerator and denominator by. As a consequence it involves many factors common to numerator and denominator and it is less practical for explicit computation unless common factors are first cancelled