Combinatorics

Math Topics A - Z listing

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Combinatorics Topics

Sort by:

Schur's partition theorem

Schur's partition theorem lets denote the number of partitions of into parts congruent to (mod 6), denote the number of partitions of into distinct parts congruent to (mod 3), and the number of partitions of into parts that differ by at least 3, with the added constraint that the difference between multiples of three is at least 6. Then (Schur 1926; Bressoud 1980; Andrews 1986, p. 53).The values of for , 2, ... are 1, 1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, ... (OEIS A003105). For example, for , there are nine partitions satisfying these conditions, as summarized in the following table (Andrews 1986, p. 54).15The identity can be established using the identity(1)(2)(3)(4)(5)(Andrews 1986, p. 54). The identity is significantly trickier.

Polyhex tiling

There are no tilings of the equilateral triangle of side length 7 by all the polyhexes of order . There are nine distinct solutions of all the polyhexes of order which tile a parallelogram of base length 7 and side length 4, one of which is illustrated above (Beeler 1972).

Restricted growth string

For a set partition of elements, the -character string in which each character gives the set block (, , ...) in which the corresponding element belongs is called the restricted growth string (or sometimes the restricted growth function). For example, for the set partition , the restricted growth string would be 0122. If the set blocks are "sorted" so that , then the restricted growth string satisfies the inequality for , 2, ..., .

Bell number

The number of ways a set of elements can be partitioned into nonempty subsets is called a Bell number and is denoted (not to be confused with the Bernoulli number, which is also commonly denoted ).For example, there are five ways the numbers can be partitioned: , , , , and , so ., and the first few Bell numbers for , 2, ... are 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, ... (OEIS A000110). The numbers of digits in for , 1, ... are given by 1, 6, 116, 1928, 27665, ... (OEIS A113015).Bell numbers are implemented in the WolframLanguage as BellB[n].Though Bell numbers have traditionally been attributed to E. T. Bell as a result of the general theory he developed in his 1934 paper (Bell 1934), the first systematic study of Bell numbers was made by Ramanujan in chapter 3 of his second notebook approximately 25-30 years prior to Bell's work (B. C. Berndt, pers. comm., Jan. 4 and 13, 2010).The first few prime Bell numbers occur at indices..

Antimagic square

An antimagic square is an array of integers from 1 to such that each row, column, and main diagonal produces a different sum such that these sums form a sequence of consecutive integers. It is therefore a special case of a heterosquare. It was defined by Lindon (1962) and appeared in Madachy's collection of puzzles (Madachy 1979, p. 103), originally published in 1966. Antimagic squares of orders 4-9 are illustrated above (Madachy 1979). For the square, the sums are 30, 31, 32, ..., 39; for the square they are 59, 60, 61, ..., 70; and so on.Let an antimagic square of order have entries 0, 1, ..., , , and letbe the magic constant. Then if an antimagic square of order exists, it is either positive with sums , or negative with sums (Madachy 1979).Antimagic squares of orders one, two, and three are impossible. In the case of the square, there is no known method of proof of this fact except by case analysis or enumeration by computer. There are 18 families of..

Social golfer problem

Twenty golfers wish to play in foursomes for 5 days. Is it possible for each golfer to play no more than once with any other golfer? The answer is yes, and the following table gives a solution.MonABCDEFGHIJKLMNOPQRSTTueAEIMBJOQCHNTDGLSFKPRWedAGKOBIPTCFMSDHJRELNQThuAHLPBKNSCEORDFIQGJMTFriAFJNBLMRCGPQDEKTHIOSEvent organizers for bowling, golf, bridge, or tennis frequently tackle problems of this sort, unaware of the problem complexity. In general, it is an unsolved problem. A table of known results is maintained by Harvey.

Kirkman's schoolgirl problem

In a boarding school there are fifteen schoolgirls who always take their daily walks in rows of threes. How can it be arranged so that each schoolgirl walks in the same row with every other schoolgirl exactly once a week? Solution of this problem is equivalent to constructing a Kirkman triple system of order . A visualization is shown above. Falcone and Pavone (2011) give a number of attractive visualizations together with a visual proof of the problem.The following table gives one of the 7 distinct (up to permutations of letters) solutions to the problem. SunABCDEFGHIJKLMNOMonADHBEKCIOFLNGJMTueAEMBHNCGKDILFJOWedAFIBLOCHJDKMEGNThuAGLBDJCFMEHOIKNFriAJNBIMCELDOGFHKSatAKOBFGCDNEIJHLM(The table of Dörrie 1965 contains four omissions in which the and entries for Wednesday and Thursday are written simply as .)..

Katona's problem

Find the minimum number of subsets in a separating family for a set of elements, where a separating family is a set of subsets in which each pair of adjacent elements is found separated, each in one of two disjoint subsets. For example, the 26 letters of the alphabet can be separated by a family of nine:The problem was posed by Katona (1973) and solved by C. Mao-Cheng in 1982,where is the ceiling function. is nondecreasing, and the values for , 2, ... are 0, 2, 3, 4, 5, 5, 6, 6, 6, 7, ... (OEIS A007600). The values at which increases are 1, 2, 3, 4, 5, 7, 10, 13, 19, 28, 37, ... (OEIS A007601), so , as illustrated in the preceding example.

Separating family

A separating family is a set of subsets in which each pair of adjacent elements are found separated, each in one of two disjoint subsets. The 26 letters of the alphabet can be separated by a family of 9,The minimal size of the separating family for an -set is 0, 2, 3, 4, 5, 5, 6, 6, 6, 7, 7, 7, ... (OEIS A007600).

Room square

A Room square (named after T. G. Room) of order (for even) is an arrangement in an square matrix of objects such that each cell is either empty or holds exactly two different objects. Furthermore, each object appears once in each row and column and each unordered pair occupies exactly one cell. The Room square of order 2 is shown below.1,2The Room square of order 8 is given in the following table.1,85,73,42,63,72,86,14,55,64,13,87,26,75,24,81,32,47,16,35,83,51,27,46,84,62,31,57,8

Affine plane

A two-dimensional affine geometry constructed over a finite field. For a field of size , the affine plane consists of the set of points which are ordered pairs of elements in and a set of lines which are themselves a set of points. Adding a point at infinity and line at infinity allows a projective plane to be constructed from an affine plane. An affine plane of order is a block design of the form (, , 1). An affine plane of order exists iff a projective plane of order exists.

Resolvable

A balanced incomplete block design is called resolvable if there exists a partition of its set of blocks into parallel classes, each of which in turn partitions the set . The partition is called a resolution.

Heterosquare

A heterosquare is an array of the integers from 1 to such that the rows, columns, and diagonals have different sums. (By contrast, in a magic square, they have the same sum.) There are no heterosquares of order two, but heterosquares of every odd order exist. They can be constructed by placing consecutive integers in a spiral pattern (Fults 1974, Madachy 1979).An antimagic square is a special case of a heterosquare for which the sums of rows, columns, and main diagonals form a sequence of consecutive integers.

Refinement

A refinement of a cover is a cover such that every element is a subset of an element .

Proper cover

Proper covers are defined as covers of a set which do not contain the entire set itself as a subset (Macula 1994). Of the five covers of , namely , , , , and , only does not contain the subset and so is the unique proper cover of two elements. In general, the number of proper covers for a set of elements is(1)(2)the first few of which are 0, 1, 45, 15913, 1073579193, ... (OEIS A007537).

Minimal cover

A minimal cover is a cover for which removal of any single member destroys the covering property. For example, of the five covers of , namely , , , , and , only and are minimal covers.Similarly, the minimal covers of are given by , , , , , , , and . The numbers of minimal covers of members for , 2, ..., are 1, 2, 8, 49, 462, 6424, 129425, ... (OEIS A046165).Let be the number of minimal covers of with members. Thenwhere is a binomial coefficient, is a Stirling number of the second kind, andSpecial cases include and . The table below gives the a triangle of (OEIS A035348).SloaneA000392A003468A016111A046166A046167A057668112113161412522151903056516130134102540171171966336217735017066420181302530538220229511298346100814988

Fano plane

The two-dimensional finite projective plane over ("of order two"), illustrated above. It is a block design with , , , , and , the Steiner triple system , and the unique configuration. The incidence graph of the Fano plane is the Heawood graph.The connectivity of the Fano plane corresponds to the order-2 two-dimensional Apollonian network.The Fano plane also solves the transylvania lottery, which picks three numbers from the integers 1-14. Using two Fano planes we can guarantee matching two by playing just 14 times as follows. Label the graph vertices of one Fano plane by the integers 1-7, the other plane by the integers 8-14. The 14 tickets to play are the 14 lines of the two planes. Then if is the winning ticket, at least two of are either in the interval [1, 7] or [8, 14]. These two numbers are on exactly one line of the corresponding plane, so one of our tickets matches them.The Lehmers (1974) found an application of the Fano plane for factoring..

Thomson problem

The Thomson problem is to determine the stable equilibrium positions of classical electrons constrained to move on the surface of a sphere and repelling each other by an inverse square law. Exact solutions for to 8 are known, but and 11 are still unknown.This problem is related to spherical codes, which are arrangements of points on a sphere such the the minimum distance between any pair of points is maximized.The Thomson problem has been solved exactly for only a few values of such as , 4, 6, and 12, where the equilibrium distributions are the vertices of an equilateral triangle circumscribed about a great circle, a regular tetrahedron, a regular octahedron, and a regular icosahedron, respectively.In reality, Earnshaw's theorem guarantees that no system of discrete electric charges can be held in stable equilibrium under the influence of their electrical interaction alone (Aspden 1987)...

Match problem

Given matches (i.e., rigid unit line segments), find the number of topologically distinct planar arrangements which can be made (Gardner 1991). In this problem, two matches laid end-to-end with no third match at their meeting point are considered equivalent to a single match, so triangles are equivalent to squares, -match tails are equivalent to 1-match tails, etc.Solutions to the match problem are planar topological graphs on edges, and the first few values for , 1, 3, 5, 10, 19, 39, ... (OEIS A003055).

Stable marriage problem

Given a set of men and women, marry them off in pairs after each man has ranked the women in order of preference from 1 to , and each women has done likewise, . If the resulting set of marriages contains no pairs of the form , such that prefers to and prefers to , the marriage is said to be stable. Gale and Shapley (1962) showed that a stable marriage exists for any choice of rankings (Skiena 1990, p. 245). In the United States, the algorithm of Gale and Shapley (1962) is used to match hospitals to medical interns (Skiena 1990, p. 245).In the rankings illustrated above, the male-optimal stable marriage is 4, 2, 6, 5, 3, 1, 7, 9, 8, and the female-optimal stable marriage is 1, 2, 8, 9, 3, 4, 7, 6, 5. A stable marriage can be found using StableMarriage[m, w] in the Wolfram Language package Combinatorica` ...

Incidence graph

Let denote a configuration with points and lines ("blocks") . Then the incidence graph , also called the Levi graph, of a configuration is a bipartite graph with "black" vertices , "white" vertices , and an edge between and iff (Coxeter 1950, Pisanski and Randić 2000).The following table summarizes the incidence graphs of some common configurations.nameconfigurationincidence graphCox configuration-hypercube graphCoxeter configurationNauru graphCremona-Richmond configurationLevi graphDesargues configurationDesargues graphdouble sixesSchläfli double sixes graphFano planeHeawood graphGray configurationGray graphKummer configurationKummer graphMiquel configurationrhombic dodecahedral graphMöbius-Kantor configurationMöbius-Kantor graphPappus configurationPappus graphPasch configurationPasch graphReye configurationReye graphDual configurations..

Desargues configuration

The configuration of ten lines intersecting three at a time in 10 points which arises in Desargues' theorem.Its incidence graph is the Desarguesgraph.

Reye configuration

A configuration of 12 planes and 12 points such that six points lie in every plane and six planes pass through every point. Alternatively, the configuration consists of 16 lines and the same 12 points such that four lines pass through every point and three points lie on every line.The points consist of the eight vertices of a cube together with its center and the three points at infinity where parallel edges of the cube meet. The 12 planes are the six faces of the cube and the six planes passing through diagonally opposite edges. The 16 lines consist of the 12 edges and four space diagonals of the cube.The Reye configuration can be realized without any points at infinity by squashing the cube and bringing the points at infinity to finite positions, as illustrated above.

Perfect ruler

A perfect ruler also called a complete ruler, is type of ruler considered by Guy (1994) which has distinct marks spaced such that the distances between marks can be used to measure all the distances 1, 2, 3, 4, ... up to some maximum distance . Such a ruler can be constructed from a perfect difference set by subtracting one from each element. For example, the perfect difference set gives 0, 1, 4, 6, which can be used to measure , , , , , (so we get 6 distances with only four marks).Perfect rulers can be used to generate graceful graphs.

Configuration

The word configuration is sometimes used to describe a finite collection of points , , where is a Euclidean space.The term "configuration" also is used to describe a finite incidence structure with the following properties (Gropp 1992). 1. There are points and lines. 2. There are points on each line and lines through each point. 3. Two different lines intersect each other at mostonce and two different points are connected by a line at most once. The conditionsare necessary for the existence of a configuration. For , these conditions are also sufficient, and for this is probably also the case (Gropp 1992). The necessary conditions hold, but there is no . For and 7, the above conditions are not sufficient, as illustrated by the affine projective plane of order 6 (, ) and the projective plane .Configurations are among the oldest combinatorial structures, having been defined by T. Reye in 1876. An -regular graph can be regarded as a configuration..

Pappus configuration

The Pappus configuration is the configuration illustrated above that appears in Pappus's hexagon theorem. It is one of the three configurations.The incidence graph of the Pappus configurationis known as the Pappus graph.

Ball picking

Consider an infinite repository containing balls of different types. Then the following table summarizes the number of distinct ways in which balls can be picked for four common definitions of "distinct."type of pickingnamesymbol namesymbolordered samples with replacementstringpowerordered sample without replacementpermutationunordered samples with replacementmultisetmultichooseunordered samples without replacementcombinationbinomial coefficient, choose

Catalan's problem

The problem of finding the number of different ways in which a product of different ordered factors can be calculated by pairs (i.e., the number of binary bracketings of letters). For example, for the four factors , , , and , there are five possibilities: , , , , and .The solution was given by Catalan in 1838 as(1)(2)(3)where is a multifactorial, is the usual factorial, and is a so-called Catalan number.

Bracketing

Take itself to be a bracketing, then recursively define a bracketing as a sequence where and each is a bracketing. A bracketing can be represented as a parenthesized string of s, with parentheses removed from any single letter for clarity of notation (Stanley 1997). Bracketings built up of binary operations only are called binary bracketings. For example, four letters have 11 possible bracketings:(1)the last five of which are binary.The number of bracketings on letters is given by the generating function(2)(Schröder 1870, Stanley 1997) and the recurrencerelation(3)(Comtet 1974), giving the sequence for as 1, 1, 3, 11, 45, 197, 903, ... (OEIS A001003). They are therefore equivalent to the super Catalan numbers.A closed form expression in terms of Legendre polynomials for is(4)(5)(Vardi 1991, p. 199).The numbers are also given by(6)for (Stanley 1997).The first Plutarch number is equal to (Stanley 1997), suggesting that..

Binary bracketing

A binary bracketing is a bracketing built up entirely of binary operations. The number of binary bracketings of letters (Catalan's problem) are given by the Catalan numbers , where(1)(2)where denotes a binomial coefficient and is the usual factorial, as first shown by Catalan in 1838. For example, for the four letters , , , and there are five possibilities: , , , , and , written in shorthand as , , , , and .

Pascal matrix

Three types of matrices can be obtained by writing Pascal's triangle as a lower triangular matrix and truncating appropriately: a symmetric matrix with , a lower triangular matrix with , and an upper triangular matrix with , where , 1, ..., . For example, for , these would be given by(1)(2)(3)The Pascal -matrix or order is implemented in the Wolfram Language as LinearAlgebra`PascalMatrix[n].These matrices have some amazing properties. In particular, their determinants are all equal to 1(4)and(5)(Edelman and Strang).Edelman and Strang give four proofs of the identity (5), themost straightforward of which is(6)(7)(8)(9)where Einstein summation has been used.

Erdős squarefree conjecture

The central binomial coefficient is never squarefree for . This was proved true for all sufficiently large by Sárkőzy's theorem. Goetgheluck (1988) proved the conjecture true for and Vardi (1991) for . The conjecture was proved true in its entirety by Granville and Ramare (1996).

Pascal's formula

Each subsequent row of Pascal's triangle is obtained by adding the two entries diagonally above. This follows immediately from the binomial coefficient identity(1)(2)(3)(4)(5)

Dilcher's formula

(1)where is a binomial coefficient (Dilcher 1995, Flajolet and Sedgewick 1995, Prodinger 2000). An inverted version is given by(2)where is a harmonic number of order (Hernández 1999, Prodinger 2000). A q-analog of (1) is given by(3)where is a q-binomial coefficient (Prodinger 2000).

Waring formula

where is the floor function and is a binomial coefficient.

Multinomial coefficient

The multinomial coefficients(1)are the terms in the multinomial series expansion. In other words, the number of distinct permutations in a multiset of distinct elements of multiplicity () is (Skiena 1990, p. 12).The multinomial coefficient is returned by the Wolfram Language function Multinomial[n1, n2, ...].The special case is given by(2)where is a binomial coefficient.The multinomial coefficients satisfy(3)(4)and so on (Gosper 1972).

Deficiency

Given binomial coefficient , writefor , where contains only those prime factors . Then the number of for which (i.e., for which all the factors of are is called the deficiency of (Erdős et al. 1993, Guy 1994). The following table gives the good binomial coefficients (i.e., those with ) having deficiency (Erdős et al. 1993), and Erdős et al. (1993) conjecture that there are no other with .good binomial coefficients1, , , , , , , ...2, , , , , ,, 3, , , , , 49

Trinomial triangle

The trinomial triangle is a number triangle of trinomial coefficients. It can be obtained by starting with a row containing a single "1" and the next row containing three 1s and then letting subsequent row elements be computed by summing the elements above to the left, directly above, and above to the right:(OEIS A027907).The plot above shows the binary representations for the first 255 (top figure) and 511 (bottom figure) terms of a flattened trinomial triangle.

Multichoose

The number of multisets of length on symbols is sometimes termed " multichoose ," denoted by analogy with the binomial coefficient . multichoose is given by the simple formulawhere is a multinomial coefficient. For example, 3 multichoose 2 is given by 6, since the possible multisets of length 2 on three elements are , , , , , and .The first few values of are given in the following table. 12345112345213610153141020354151535705162156126Multichoose problems are sometimes called "bars and stars" problems. For example, suppose a recipe called for 5 pinches of spice, out of 9 spices. Each possibility is an arrangement of 5 spices (stars) and dividers between categories (bars), where the notation indicates a choice of spices 1, 1, 5, 6, and 9 (Feller 1968, p. 36). The number of possibilities in this case is then ,..

Christmas stocking theorem

The Christmas stocking theorem, also known as the hockey stick theorem, states that the sum of a diagonal string of numbers in Pascal's triangle starting at the th entry from the top (where the apex has ) on left edge and continuing down rows is equal to the number to the left and below (the "toe") bottom of the diagonal (the "heel"; Butterworth 2002). This follows from the identitywhere is a binomial coefficient.

Trinomial coefficient

A trinomial coefficient is a coefficient of the trinomial triangle. Following the notation of Andrews (1990), the trinomial coefficient , with and , is given by the coefficient of in the expansion of . Therefore,(1)The trinomial coefficient can be given by the closed form(2)where is a Gegenbauer polynomial.Equivalently, the trinomial coefficients are defined by(3)The trinomial coefficients also have generatingfunction(4)(5)i.e.,(6)The trinomial triangle gives the triangle oftrinomial coefficients,(7)(OEIS A027907).The central column of the trinomial triangle gives the centraltrinomial coefficients.The trinomial coefficient is also given by the number of permutations of symbols, each , 0, or 1, which sum to . For example, there are seven permutations of three symbols which sum to 0, , , , , and , , , so .An alternative (but different) definition of the trinomial coefficients is as the coefficients in (Andrews 1990), which is therefore..

Central trinomial coefficient

The th central trinomial coefficient is defined as the coefficient of in the expansion of . It is therefore the middle column of the trinomial triangle, i.e., the trinomial coefficient . The first few central trinomial coefficients for , 2, ... are 1, 3, 7, 19, 51, 141, 393, ... (OEIS A002426).The central trinomial coefficient is also gives the number of permutations of symbols, each , 0, or 1, which sum to 0. For example, there are seven such permutations of three symbols: , , , , and , , .The generating function is given by(1)(2)The central trinomial coefficients are given by the recurrenceequation(3)with , but cannot be expressed as a fixed number of hypergeometric terms (Petkovšek et al. 1996, p. 160).The coefficients satisfy the congruence(4)(T. D. Noe, pers. comm., Mar. 15, 2005) and(5)for a prime, which is easy to show using Fermat's little theorem (T. D. Noe, pers. comm., Oct. 26, 2005).Sum..

Lucas correspondence theorem

Let be prime and(1)(2)then(3)This is proved in Fine (1947).This theorem is the underlying reason that the binomial coefficient mod 2 can be computed using bitwise operations AND(NOT(),), giving the Sierpiński sieve.

Logarithmic binomial theorem

For all integers and ,where is the harmonic logarithm and is a Roman coefficient. For , the logarithmic binomial theorem reduces to the classical binomial theorem for positive , since for , for , and when .Similarly, taking and gives the negative binomial series. Roman (1992) gives expressions obtained for the case and which are not obtainable from the binomial theorem.

Central binomial coefficient

The th central binomial coefficient is defined as(1)(2)where is a binomial coefficient, is a factorial, and is a double factorial.These numbers have the generating function(3)The first few values are 2, 6, 20, 70, 252, 924, 3432, 12870, 48620, 184756, ... (OEIS A000984). The numbers of decimal digits in for , 1, ... are 1, 6, 59, 601, 6019, 60204, 602057, 6020597, ... (OEIS A114501). These digits converge to the digits in the decimal expansion of (OEIS A114493).The central binomial coefficients are never prime except for .A scaled form of the central binomial coefficient is known as a Catalannumber(4)Erdős and Graham (1975) conjectured that the central binomial coefficient is never squarefree for , and this is sometimes known as the Erdős squarefree conjecture. Sárkőzy's theorem (Sárkőzy 1985) provides a partial solution which states that the binomial coefficient is never squarefree for all sufficiently..

Klee's identity

Klee's identity is the binomial sumwhere is a binomial coefficient. For , 1, ... and , 1,..., the following array is obtained.10000000000000000000001000000000020000000001100000000040000000061000000004600000001151000000020800000015281(OEIS A092865)

Jonah formula

A formula for the generalized Catalan number . The general formula iswhere is a binomial coefficient, although Jonah's original formula corresponded to , (Hilton and Pederson 1991).

Staircase walk

The number of staircase walks on a grid with horizontal lines and vertical lines is given by(Vilenkin 1971, Mohanty 1979, Narayana 1979, Finch 2003). The first few values for , 2, ..., are 1, 2, 6, 20, 70, 252, ... (OEIS A000984), which are the central binomial coefficients. A Dyck path is a staircase walk from to which never crosses (but may touch) the diagonal .

Binomial coefficient

The binomial coefficient is the number of ways of picking unordered outcomes from possibilities, also known as a combination or combinatorial number. The symbols and are used to denote a binomial coefficient, and are sometimes read as " choose ." therefore gives the number of k-subsets possible out of a set of distinct items. For example, The 2-subsets of are the six pairs , , , , , and , so . The number of lattice paths from the origin to a point ) is the binomial coefficient (Hilton and Pedersen 1991).The value of the binomial coefficient for nonnegative and is given explicitly by(1)where denotes a factorial. Writing the factorial as a gamma function allows the binomial coefficient to be generalized to noninteger arguments (including complex and ) as(2)For nonnegative integer arguments, the gamma function reduces to factorials, leading to(3)which is Pascal's triangle. Using the symmetryformula(4)for integer , and complex , this..

Sárkőzy's theorem

A partial solution to the Erdős squarefree conjecture which states that the binomial coefficient is never squarefree for all sufficiently large . Sárkőzy (1985) showed that if is the square part of the binomial coefficient , thenwhere is the Riemann zeta function. An upper bound on of has been obtained.

Good binomial coefficient

A binomial coefficient with is called good if its least prime factor satisfies(Erdős et al. 1993). This is equivalent to the requirement thatThe first few good binomial coefficients are therefore , , , , , , , , .... Good binomial coefficients are closely related to the Erdős-selfridge function , which gives the least integer such that is good.

Franel number

The Franel numbers are the numbers(1)where is a binomial coefficient. The first few values for , 1, ... are 1, 2, 10, 56, 346, ... (OEIS A000172). They arise in the first Strehl identity(2)and can be written in closed form as(3)where is a generalized hypergeometric function.They are given by the integral(4)where is a Laguerre polynomial.They are also given by the recurrence equation(5)with and .

Exceptional binomial coefficient

A binomial coefficient is said to be exceptional if . The following table gives the exception binomial coefficients which are also good binomial coefficients, are not of the form , and have specified least prime factors .exceptional binomial coefficients1317, , , , ,, , 19, 2329

Dyson's conjecture

Based on a problem in particle physics, Dyson (1962abc) conjectured that the constantterm in the Laurent seriesis the multinomial coefficientThe theorem was proved by Wilson (1962) and independently by Gunson (1962). A definitive proof was subsequently published by Good (1970).

Domino tiling

The Fibonacci number gives the number of ways for dominoes to cover a checkerboard, as illustrated in the diagrams above (Dickau).The numbers of domino tilings, also known as dimer coverings, of a square for , 2, ... are given by 2, 36, 6728, 12988816, ... (OEIS A004003). The 36 tilings on the square are illustrated above. A formula for these numbers is given by(1)Writing(2)gives the surprising result(3)(John and Sachs 2000). For , 2, ..., the first few terms are 1, 3, 29, 5, 5, 7, 25, 9, 9, 11, 21, ... (OEIS A143234).Writing(4)(5)(6)(7)(OEIS A143233), where is Catalan's constant.

Polyomino tiling

A polyomino tiling is a tiling of the plane by specified types of polyominoes. Tiling by polyominoes has been investigated since at least the late 1950s, particularly by S. Golomb (Wolfram 2002, p. 943).Interestingly, the Fibonacci number gives the number of ways for dominoes to cover a checkerboard.Each monomino, domino, triomino, tetromino, pentomino, and hexomino tiles the plane without requiring flipping. In addition, each heptomino with the exception of the four illustrated above can tile the plane, also without flipping (Schroeppel 1972).Recently, sets of polyominoes that force non-periodic patterns have been found. The set illustrated at left above was announced by Roger Penrose in 1994, and the slightly smaller set illustrated at right below was found by Matthew Cook (Wolfram 2002, p. 943).Both of these sets yield nested patterns, as illustrated above for Cook's tiles (Wolfram2002, p. 943).Consider..

Weighing

weighings are sufficient to find a bad coin among coins (Steinhaus 1999, p. 61). vos Savant (1993) gives an algorithm for finding a bad ball among 12 balls in three weighings (which, in addition, determines if the bad ball is heavier or lighter than the other 11), and Steinhaus (1999, pp. 58-61) gives an algorithm for 13 balls.Bachet's weights problem asks for the minimum number of weights (which can be placed in either pan of a two-arm balance) required to weigh any integral number of pounds from 1 to 40 (Steinhaus 1999, p. 52). The solution is 1, 3, 9, and 27: 1, , 3, , , , , , 9, , , , , , , , , and so on.

Permutation pattern

Let denote the number of permutations on the symmetric group which avoid as a subpattern, where " contains as a subpattern" is interpreted to mean that there exist such that for ,iff .For example, a permutation contains the pattern (123) iff it has an ascending subsequence of length three. Here, note that members need not actually be consecutive, merely ascending (Wilf 1997). Therefore, of the partitions of , all but (i.e., , , , , and ) contain the pattern (12) (i.e., an increasing subsequence of length two).The following table gives the numbers of pattern-matching permutations of , , ..., numbers for various patterns of length .patternOEISnumber of pattern-matching permutations1A0001421, 2, 6, 24, 120, 720, 5040, ...12A0333121, 5, 23, 119, 719, 5039, 40319, ...A0569861, 10, 78, 588, 4611, 38890, ...1234A1580051, 17, 207, 2279, 24553, ...1324A1580091, 17, 207, 2278, 24527, ...1342A1580061, 17, 208, 2300, 24835, ...The following..

Permutation involution

An involution of a set is a permutation of which does not contain any permutation cycles of length (i.e., it consists exclusively of fixed points and transpositions). Involutions are in one-to-one correspondence with self-conjugate permutations (i.e., permutations that are their own inverse permutation). For example, the unique permutation involution on 1 element is , the two involution permutations on 2 elements are and , and the four involution permutations on 3 elements are , , , and . A permutation can be tested to determine if it is an involution using InvolutionQ[p] in the Wolfram Language package Combinatorica` .The permutation matrices of an involution are symmetric. The number of involutions on elements is the same as the number of distinct Young tableaux on elements (Skiena 1990, p. 32).In general, the number of involution permutations on letters is given by the formula(1)where is a binomial coefficient (Muir 1960, p. 5),..

Permutation inversion

A pair of elements is called an inversion in a permutation if and (Skiena 1990, p. 27; Pemmaraju and Skiena 2003, p. 69). For example, in the permutation contains the four inversions , , , and . Inversions are pairs which are out of order, and are important in sorting algorithms (Skiena 1990, p. 27).The total number of inversions can be obtained by summing the elements of the inversion vector. The number of inversions in any permutation is the same as the number of interchanges of consecutive elements necessary to arrange them in their natural order (Muir 1960, p. 1). The value can be found in the Wolfram Language using Signature[p].The number of inversions in a permutation is equal to that of its inverse permutation (Skiena 1990, p. 29; Knuth 1998). If, from any permutation, another is formed by interchanging two elements, then the difference between the number of inversions in the two is always an odd number...

Even permutation

An even permutation is a permutation obtainable from an even number of two-element swaps, i.e., a permutation with permutation symbol equal to . For initial set 1,2,3,4, the twelve even permutations are those with zero swaps: (1,2,3,4); and those with two swaps: (1,3,4,2, 1,4,2,3, 2,1,4,3, 2,3,1,4, 2,4,3,1, 3,1,2,4, 3,2,4,1, 3,4,1,2, 4,1,3,2, 4,2,1,3, 4,3,2,1).For a set of elements and , there are even permutations, which is the same as the number of odd permutations. For , 2, ..., the numbers are given by 0, 1, 3, 12, 60, 360, 2520, 20160, 181440, ... (OEIS A001710).

Wilf class

Two patterns and belong to the same Wilf class if for all , where denotes the set of permutations on that avoid the pattern . Two sets having the same Wilf class are said to be Wilf equivalent.

Permutation index

The index of a permutation is defined as the sum of all subscripts such that , for . MacMahon (1960) proved that the number of permutations of size having index is the same as the number having exactly inversions (Skiena 1990, p. 29). The permutation index can be computed as Index[p] in the Wolfram Language package Combinatorica` .

Eulerian number

The Eulerian number gives the number of permutations of having permutation ascents (Graham et al. 1994, p. 267). Note that a slightly different definition of Eulerian number is used by Comtet (1974), who defines the Eulerian number (sometimes also denoted ) as the number of permutation runs of length , and hence .The Eulerian numbers are given explicitly by the sum(1)(Comtet 1974, p.  243). The Eulerian numbers satisfy the sum identity(2)as well as Worpitzky's identity(3)Eulerian numbers also arise in the surprising context of integrating the sincfunction, and also in sums of the form(4)(5)where is the polylogarithm function. is therefore given by the coefficient of in(6) has the exponential generating function(7)The Eulerian numbers satisfy the recurrence relation(8)Special cases are given by(9)(10)(11)and summarized in the following table.OEIS, , , ...1A0002950, 1, 4, 11, 26, 57, 120, 247, 502, 1013, ...2A0004600,..

Euler zigzag number

The number of alternating permutations for elements is sometimes called an Euler zigzag number. Denote the number of alternating permutations on elements for which the first element is by . Then and(1)where is an Entringer number.

Permutation cycle

A permutation cycle is a subset of a permutation whose elements trade places with one another. Permutations cycles are called "orbits" by Comtet (1974, p. 256). For example, in the permutation group , (143) is a 3-cycle and (2) is a 1-cycle. Here, the notation (143) means that starting from the original ordering , the first element is replaced by the fourth, the fourth by the third, and the third by the first, i.e., .There is a great deal of freedom in picking the representation of a cyclic decomposition since (1) the cycles are disjoint and can therefore be specified in any order, and (2) any rotation of a given cycle specifies the same cycle (Skiena 1990, p. 20). Therefore, (431)(2), (314)(2), (143)(2), (2)(431), (2)(314), and (2)(143) all describe the same permutation. The following table gives the set of representations for each element of the symmetric group on three elements, , sorted in lowest canonical order (first..

Transposition

An exchange of two elements of an ordered list with all others staying the same. A transposition is therefore a permutation of two elements. For example, the swapping of 2 and 5 to take the list 123456 to 153426 is a transposition. The permutation symbol is defined as , where is the number of transpositions of pairs of elements that must be composed to build up the permutation.

Permutation ascent

Let be a permutation. Then is a permutation ascent if . For example, the permutation is composed of three ascents, namely , , and .The number of permutations of length having ascents is given by the Eulerian number .The total number of ascents in all permutations of order isgiving the first few terms for , 2, ... as 0, 1, 6, 36, 240, 1800, 15120, ... (OEIS A001286).There is an intimate connection between permutation ascents and permutation runs, with the number of ascents of length in the permutations being equal to the number of permutation runs of length (Skiena 1990, p. 31), or

Derangement

A derangement is a permutation in which none of the objects appear in their "natural" (i.e., ordered) place. For example, the only derangements of are and , so . Similarly, the derangements of are , , , , , , , , and . Derangements are permutations without fixed points (i.e., having no cycles of length one). The derangements of a list of elements can be computed in the Wolfram Language usingDerangements[l_List] := With[ {perms = Permutations[l]}, {supp = PermutationSupport /@ perms}, Pick[perms, Length /@ supp, Length[l]]]The derangement problem was formulated by P. R. de Montmort in 1708, and solved by him in 1713 (de Montmort 1713-1714). Nicholas Bernoulli also solved the problem using the inclusion-exclusion principle (de Montmort 1713-1714, p. 301; Bhatnagar 1995, p. 8).Derangements are also called rencontres numbers (named after rencontres solitaire) or complete permutations, and the..

Permutation

A permutation, also called an "arrangement number" or "order," is a rearrangement of the elements of an ordered list into a one-to-one correspondence with itself. The number of permutations on a set of elements is given by ( factorial; Uspensky 1937, p. 18). For example, there are permutations of , namely and , and permutations of , namely , , , , , and . The permutations of a list can be found in the Wolfram Language using the command Permutations[list]. A list of length can be tested to see if it is a permutation of 1, ..., in the Wolfram Language using the command PermutationListQ[list].Sedgewick (1977) summarizes a number of algorithms for generating permutations, and identifies the minimum change permutation algorithm of Heap (1963) to be generally the fastest (Skiena 1990, p. 10). Another method of enumerating permutations was given by Johnson (1963; Séroul 2000, pp. 213-218).The number..

Cyclic permutation

A permutation which shifts all elements of a set by a fixed offset, with the elements shifted off the end inserted back at the beginning. For a set with elements , , ..., , a cyclic permutation of one place to the left would yield , ..., , , and a cyclic permutation of one place to the right would yield , , , ....The mapping can be written as for a shift of places. A shift of places to the left is implemented in the Wolfram Language as RotateLeft[list, k], while a shift of places to the right is implemented as RotateRight[list, k].

Partial derangement

A permutation of distinct, ordered items in which none of the items is in its original ordered position is known as a derangement. If some, but not necessarily all, of the items are not in their original ordered positions, the configuration can be referred to as a partial derangement (Evans et al. 2002, p. 385).Among the possible permutations of distinct items, examine the number of these permutations in which exactly items are in their original ordered positions. Then(1)(2)(3)where is a binomial coefficient and is the subfactorialHere is a table of the number of partial derangements for , 1, ..., 8:(4)(OEIS A098825).

Contained pattern

A subset of a permutation is said to contain if there exist such that is order isomorphic to . Here, is the symmetric group on elements.In other words, contains iff any k-subset of is order isomorphic to .

Odd permutation

An odd permutation is a permutation obtainable from an odd number of two-element swaps, i.e., a permutation with permutation symbol equal to . For initial set 1,2,3,4, the twelve odd permutations are those with one swap (1,2,4,3, 1,3,2,4, 1,4,3,2, 2,1,3,4, 3,2,1,4, 4,2,3,1) and those with three swaps (2,3,4,1, 2,4,1,3, 3,1,4,2, 3,4,2,1, 4,1,2,3, 4,3,1,2).For a set of elements and , there are odd permutations (D'Angelo and West 2000, p. 111), which is the same as the number of even permutations. For , 2, ..., the numbers are given by 0, 1, 3, 12, 60, 360, 2520, 20160, 181440, ... (OEIS A001710).

Combination lock

Consider a combination lock consisting of buttons that can be pressed in any combination (including multiple buttons at once), but in such a way that each number is pressed exactly once. Then the number of possible combination locks with buttons is given by the number of lists (i.e., ordered sets) of disjoint nonempty subsets of the set that contain each number exactly once. For example, there are three possible combination locks with two buttons: , , and . Similarly there are 13 possible three-button combination locks: , , , , , , , , , , , , . satisfies the linear recurrence equation(1)with . This can also be written(2)(3)where the definition has been used. Furthermore,(4)(5)where are Eulerian numbers. In terms of the Stirling numbers of the second kind ,(6) can also be given in closed form as(7)where is the polylogarithm. The first few values of for , 2, ... are 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563, ... (OEIS A000670).The quantity(8)satisfies..

Stirling number of the first kind

The signed Stirling numbers of the first kind are variously denoted (Riordan 1980, Roman 1984), (Fort 1948, Abramowitz and Stegun 1972), (Jordan 1950). Abramowitz and Stegun (1972, p. 822) summarize the various notational conventions, which can be a bit confusing (especially since an unsigned version is also in common use). The signed Stirling number of the first kind is are returned by StirlingS1[n, m] in the Wolfram Language, where they are denoted .The signed Stirling numbers of the first kind are defined such that the number of permutations of elements which contain exactly permutation cycles is the nonnegative number(1)This means that for and . A related set of numbers is known as the associated Stirling numbers of the first kind. Both these and the usual Stirling numbers of the first kind are special cases of a general function which is related to the number of cycles in a permutation.The triangle of signed Stirling numbers of the..

Necklace

In the technical combinatorial sense, an -ary necklace of length is a string of characters, each of possible types. Rotation is ignored, in the sense that is equivalent to for any .In fixed necklaces, reversal of strings is respected, so they represent circular collections of beads in which the necklace may not be picked up out of the plane (i.e., opposite orientations are not considered equivalent). The number of fixed necklaces of length composed of types of beads is given by(1)where are the divisors of with , , ..., , is the number of divisors of , and is the totient function.For free necklaces, opposite orientations (mirror images) are regarded as equivalent, so the necklace can be picked up out of the plane and flipped over. The number of such necklaces composed of beads, each of possible colors, is given by(2)For and an odd prime, this simplifies to(3)A table of the first few numbers of necklaces for and follows. Note that is larger than for . For..

Combination

The number of ways of picking unordered outcomes from possibilities. Also known as the binomial coefficient or choice number and read " choose ,"where is a factorial (Uspensky 1937, p. 18). For example, there are combinations of two elements out of the set , namely , , , , , and . These combinations are known as k-subsets.The number of combinations can be computed in the Wolfram Language using Binomial[n, k], and the combinations themselves can be enumerated in the Wolfram Language using Subsets[Range[n],k].Muir (1960, p. 7) uses the nonstandard notations and .

Mousetrap

A permutation problem invented by Cayley. Let the numbers 1, 2, ..., be written on a set of cards, and shuffle this deck of cards. Now, start counting using the top card. If the card chosen does not equal the count, move it to the bottom of the deck and continue counting forward. If the card chosen does equal the count, discard the chosen card and begin counting again at 1. The game is won if all cards are discarded, and lost if the count reaches .The number of ways the cards can be arranged such that at least one card is in the proper place for , 2, ... are 1, 1, 4, 15, 76, 455, ... (OEIS A002467).

Circular permutation

The number of ways to arrange distinct objects along a fixed (i.e., cannot be picked up out of the plane and turned over) circle isThe number is instead of the usual factorial since all cyclic permutations of objects are equivalent because the circle can be rotated.For example, of the permutations of three objects, the distinct circular permutations are and . Similarly, of the permutations of four objects, the distinct circular permutations are , , , , , and . Of these, there are only three free permutations (i.e., inequivalent when flipping the circle is allowed): , , and . The number of free circular permutations of order is for , 2, andfor , giving the sequence 1, 1, 1, 3, 12, 60, 360, 2520, ... (OEIS A001710).

Married couples problem

Also called the ménage problem. In how many ways can married couples be seated around a circular table in such a manner than there is always one man between two women and none of the men is next to his own wife? The solution (Ball and Coxeter 1987, p. 50) uses discordant permutations and was solved by Laisant, Moreau, and Taylor. The solution for can be given in terms of Laisant's recurrence formulawith and (Dörrie 1965, p. 33).A closed form expression for in terms of a sum due to Touchard (1953) iswhere is a binomial coefficient (Comtet 1974, p. 185; Vardi 1991, p. 123).The first few values of for , 3, ... obtained from the recurrence and sum above are 0, 1, 2, 13, 80, 579, ... (OEIS A000179), which are sometimes called ménage numbers. The desired solution is then . The numbers can be considered a special case of a restricted rooks problem...

Siteswap

A siteswap is a sequence encountered in juggling in which each term is a positive integer, encoded in binary. The transition rule from one term to the next consists of changing some 0 to 1, subtracting 1, and then dividing by 2, with the constraint that the division by two must be exact. Therefore, if a term is even, the bit to be changed must be the units bit. In siteswaps, the number of 1-bits is a constant.Each transition is characterized by the bit position of the toggled bit (denoted here by the numeral on top of the arrow). For example,The second term is given from the first as follows: 000111 with bit 5 flipped becomes 100111, or 39. Subtract 1 to obtain 38 and divide by two to obtain 19, which is 10011.

Lexicographic order

An ordering for the Cartesian product of any two sets and with order relations and , respectively, such that if and both belong to , then iff either 1. , or 2. and . The lexicographic order can be readily extended to cartesian products of arbitrary length by recursively applying this definition, i.e., by observing that .When applied to permutations, lexicographic order is increasing numerical order (or equivalently, alphabetic order for lists of symbols; Skiena 1990, p. 4). For example, the permutations of in lexicographic order are 123, 132, 213, 231, 312, and 321.When applied to subsets, two subsets are ordered by their smallest elements (Skiena 1990, p. 44). For example, the subsets of in lexicographic order are , , , , , , , .Lexicographic order is sometimes called dictionary order...

Bumping algorithm

Given a permutation of , the bumping algorithm constructs a standard Young tableau by inserting the one by one into an already constructed Young tableau. To apply the bumping algorithm, start with , which is a Young tableau. If through have already been inserted, then in order to insert , start with the first line of the already constructed Young tableau and search for the first element of this line which is greater than . If there is no such element, append to the first line and stop. If there is such an element (say, ), exchange for , search the second line using , and so on.

Langford's problem

Arrange copies of the digits 1, ..., such that there is one digit between the 1s, two digits between the 2s, etc. For example, the unique (modulo reversal) solution is 231213, and the unique (again modulo reversal) solution is 23421314. Solutions to Langford's problem exist only if , so the next solutions occur for . There are 26 of these, as exhibited by Lloyd (1971). In lexicographically smallest order (i.e., small digits come first), the first few Langford sequences are 231213, 23421314, 14156742352637, 14167345236275, 15146735423627, ... (OEIS A050998).The number of solutions for , 4, 5, ... (modulo reversal of the digits) are 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, ... (OEIS A014552). No formula is known for the number of solutions of a given order .

Secant number

The secant numbers , also called the zig numbers or the Euler numbers numbers than can be defined either in terms of a generating function given as the Maclaurin series of or as the numbers of alternating permutations on , 4, 6, ... symbols (where permutations that are the reverses of one another counted as equivalent). The first few for , 2, ... are 1, 5, 61, 1385, ... (OEIS A000364).For example, the reversal-nonequivalent alternating permutations on and 4 numbers are , and , , , , , respectively.The secant numbers have the generating function(1)(2)

Avoided pattern

A pattern is said to avoid if is not contained in . In other words, avoids iff no k-subset of is order isomorphic to .

Prime circle

A prime circle of order is a free circular permutation of the numbers from 1 to with adjacent pairs summing to a prime. The number of prime circles for , 2, ..., are 1, 1, 1, 2, 48, 512, ... (OEIS A051252). The prime circles for the first few even orders are given in the table below.prime circles2468,

Associated stirling number of the first kind

The associated Stirling numbers of the first kind are defined as the number of permutations of a given number having exactly permutation cycles, all of which are of length or greater (Comtet 1974, p. 256; Riordan 1980, p. 75). They are a special case of the more general numbers , and have the recurrence relation(1)with initial conditions for , and (Appell 1880; Tricomi 1951; Carlitz 1958; Comtet 1974, pp. 256, 293, and 295). The generating function for is given by(2)(Comtet 1974, p. 256). The associated Stirling numbers of the first kind satisfy the sum identity(3)For and a prime,(4)For all integers ,(5)and similarly,(6)(Comtet 1974, p. 256).Special cases of the associated Stirling numbers of the first kind are given by(7)(8)(9)(10)(Comtet 1974, p. 256). The triangle of these numbers is given by(11)(OEIS A008306)...

Inverse permutation

An inverse permutation is a permutation in which each number and the number of the place which it occupies are exchanged. For example,(1)(2)are inverse permutations, since the positions of 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10 in are , and the positions of 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10 in are likewise (Muir 1960, p. 5).The inverse permutation of a given permutation can be computed in the Wolfram Language using InversePermutation[p].Inverse permutations are sometimes also called conjugate or reciprocal permutations (Muir 1960, p. 4).

Permutation symbol

The permutation symbol (Evett 1966; Goldstein 1980, p. 172; Aris 1989, p. 16) is a three-index object sometimes called the Levi-Civita symbol (Weinberg 1972, p. 38; Misner et al. 1973, p. 87; Arfken 1985, p. 132; Chandrasekhar 1998, p. 68), Levi-Civita density (Goldstein 1980, p. 172), alternating tensor (Goldstein 1980, p. 172; Landau and Lifshitz 1986, p. 110; Chou and Pagano 1992, p. 182), or signature. It is defined by(1)The permutation symbol is implemented in the WolframLanguage as Signature[list].There are several common notations for the symbol, the first of which uses the usual Greek epsilon character (Goldstein 1980, p. 172; Griffiths 1987, p. 139; Jeffreys and Jeffreys 1988, p. 69; Aris 1989, p. 16; Chou and Pagano 1992, p. 182), the second of which uses the curly variant (Weinberg 1972, p. 38; Misner et al. 1973, p. 87;..

Graceful permutation

A graceful permutation on letters is a permutation such thatFor example, there are four graceful permutations on : , , , and . The number of graceful permutations on letters for , 2, ... are 1, 2, 4, 4, 8, 24, 32, 40, ... (OEIS A006967).

Permutation run

A set of ascending sequences in a permutation is called a run (Graham et al. 1994) or sometimes a rise (Comtet 1974, p. 241). A sorted permutation consists of a single run, whereas a reverse permutation consists of runs, each of length 1. The permutation runs in a permutation can be computed using Runs[p] in the Wolfram Language package Combinatorica` . The number of permutation runs of the partition of with runs is sometimes denoted (Comtet 1974, p. 241).For example, the permutation contains the single run , while contains the two runs and . The following table lists the permutation runs for each permutation of .permutation runs, , , , , , The number of permutations of length with exactly runs is directly related to the number of permutation ascents, with runs implying ascents (Comtet 1974, p. 241; Skiena 1990, p. 31), sowhere is an Eulerian number.Surprisingly, the expected length of the first run is shorter than the expected..

Alternating permutation

An alternating permutation is an arrangement of the elements , ..., such that no element has a magnitude between and is called an alternating (or zigzag) permutation. The determination of the number of alternating permutations for the set of the first integers is known as André's problem.The numbers of alternating permutations on the integers from 1 to for , 2, ... are 1, 2, 4, 10, 32, 122, 544, ... (OEIS A001250). For example, the alternating permutations on integers for small are summarized in the following table.alternating permutations1122, 34, , , 410, , , , ,, , , , For , every alternating permutation can be written either forward or reversed, and so must be an even number . The quantity can be simply computed from the recurrence equation(1)where and pass through all integral numbers such that(2), and(3)The numbers are sometimes called the Euler zigzag numbers, and the first few are given by 1, 1, 1, 2, 5, 16, 61, 272, ... (OEIS A000111).The..

Random partition

A random partition of a number is one of the possible partitions of , where is the partition function P. A random partition can be given by RandomPartition[n] in the Wolfram Language package Combinatorica` .

Random composition

A random composition of a number in parts is one of the possible compositions of , where is a binomial coefficient. A random composition can be given by RandomComposition[n, k] in the Wolfram Language package Combinatorica` .

Young tableau

The Young tableau (plural, "tableaux") of a Ferrers diagram is obtained by placing the numbers 1, ..., in the boxes of the diagram. A "standard" Young tableau is a Young tableau in which the numbers form an increasing sequence along each line and along each column. For example, the standard Young tableaux of size are given by , , , and , illustrated above. The bumping algorithm is used to construct a standard Young tableau from a permutation of , and the number of standard Young tableaux of size 1, 2, 3, ... are 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... (OEIS A000085). These numbers can be generated by the recurrence relationwith and . This is the same as the number of permutation involutions on elements (Skiena 1990, p. 32).The number of all possible standard Young tableaux of a given shape can also be considered, and can be calculated with the hook length formula. For example, the illustration above shows the 35 standard..

Ramanujan's identity

where is a -Pochhammer symbol and is the partition function P.

Prime partition

A prime partition of a positive integer is a set of primes which sum to . For example, there are three prime partitions of 7 sinceThe number of prime partitions of , 3, ... are 1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 9, 10, 12, 14, 17, 19, 23, 26, ... (OEIS A000607). If for prime and for composite, then the Euler transform gives the number of partitions of into prime parts (Sloane and Plouffe 1995, p. 21).The minimum number of primes needed to sum to , 3, ... are 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, ... (OEIS A051034). The maximum number of primes needed to sum to is just , 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, ... (OEIS A004526), corresponding to a representation in terms of all 2s for an even number or one 3 and the rest 2s for an odd number.The numbers which can be represented by a single prime are obviously the primes themselves. Composite numbers which can be represented as the sum of two primes are 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, ... (OEIS A051035), and composite..

Ferrers diagram

A Ferrers diagram represents partitions as patterns of dots, with the th row having the same number of dots as the th term in the partition. The spelling "Ferrars" (Skiena 1990, pp. 53 and 78) is sometimes also used, and the diagram is sometimes called a graphical representation or Ferrers graph (Andrews 1998, p. 6). A Ferrers diagram of the partitionfor a list , , ..., of positive integers with is therefore the arrangement of dots or square boxes in rows, such that the dots or boxes are left-justified, the first row is of length , the second row is of length , and so on, with the th row of length . The above diagram corresponds to one of the possible partitions of 100.The partitions of integers less than or equal to in which there are at most parts and in which no part is larger than correspond (1) to Young tableaux which fit inside an rectangle and (2) to lattice paths which travel from the upper right corner of the rectangle to the lower..

Plane partition

A plane partition is a two-dimensional array of integers that are nonincreasing both from left to right and top to bottom and that add up to a given number . In other words,(1)(2)and(3)Implicit in this definition is the requirement that the array be flush on top and to the left and contain no holes.(4)For example, one plane partition of 22 is illustrated above.The generating function for the number of planar partitions of is(5)(OEIS A000219, MacMahon 1912b, Speciner 1972,Bender and Knuth 1972, Bressoud and Propp 1999).Writing , a recurrence equation for is given by(6)where is a divisor function. It also has generating function(7)MacMahon (1960) also showed that the number of plane partitions whose Young tableaux fit inside an rectangle and whose integers do not exceed (in other words, with all ) is given by(8)(Bressoud and Propp 1999, Fulmek and Krattenthaler 2000). Expanding out the products gives(9)(10)where is the Barnes G-function...

Euler identity

For ,(1)Both of these have closed form representation(2)where is a q-Pochhammer symbol.Expanding and taking a series expansion about zero for either side gives(3)giving 1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, ... (OEIS A000009), i.e., the number of partitions of into distinct parts .

Van der waerden's theorem

van der Waerden's theorem is a theorem about the existence of arithmetic progressions in sets. The theorem can be stated in four equivalent forms. 1. If , then some contains arbitrarily long arithmetic progressions (Baudet's conjecture). 2. For all positive integers and , there exists a constant such that if and , then some set contains an arithmetic progression of length . 3. If is an infinite sequence of integers satisfying for some , then the sequence contains arbitrarily long arithmetic progressions. 4. For all positive integers and , there is a constant such that if and , , ..., satisfies , then of the numbers , , ..., are in arithmetic progression. The constants are called van der Waerden numbers, and no formula for is known. van der Waerden's theorem is a corollary of Szemerédi's theorem...

Perfect partition

A perfect partition is a partition of a number whose elements uniquely generate any number 1, 2, ..., . is always a perfect partition of , and every perfect partition must contain a 1.The following table gives the first several perfect partitions for small .perfect partitions112132, 4153, , 61The numbers of perfect partitions of for , 2, ... are given by 1, 1, 2, 1, 3, 1, 4, 2, 3, ... (OEIS A002033). For a prime power, the number of perfect partitions is given byThe number of perfect partitions of is equal to the number of ordered factorizations of (Goulden and Jackson 1983, p. 94).

Van der waerden number

One form of van der Waerden's theorem states that for all positive integers and , there exists a constant such that if and , then some set contains an arithmetic progression of length . The least possible value of is known as a van der Waerden number. The only nontrivial van der Waerden numbers that are known exactly are summarized in the following table. As shown in the table, the first few values of for , 2, ... are 1, 3, 9, 35, 178, 1132, ... (OEIS A005346), the last of which is due to M. Kouril and J. L. Paul in 2007 (Kouril and Paul 2008).345629351781132327476Shelah (1988) proved that van der Waerden's numbers are primitiverecursive. It is known that(1)and that(2)for some constants and . In 1998, T. Gowers announced that he has proved the general result(3)(Gowers 2001). Berlekamp (1968) showed that for a prime,(4)A probabilistic argument using the Lovászlocal lemma shows that(5)New lower bounds have been given..

Entringer number

(1)The Entringer numbers (OEIS A008281) are the number of permutations of , starting with , which, after initially falling, alternately fall then rise. The Entringer numbers are given by(2)(3)together with the recurrence relation(4)A suitably arranged number triangle of these numbers is known as the Seidel-Entringer-Arnold triangle.The numbers are the secant and tangent numbers given by the Maclaurin series(5)They have closed form(6). where is an Euler number and is a Bernoulli number.

Elder's theorem

Elder's theorem is a generalization of Stanley's theorem which states that the total number of occurrences of an integer among all unordered partitions of is equal to the number of occasions that a part occurs or more times in a partition, where a partition which contains parts that each occur or more times contributes to the sum in question.The general result was discovered by R. P. Stanley in 1972 and submitted it to the "Problems and Solutions" section of the American Mathematical Monthly, where was rejected with the comment "A bit on the easy side, and using only a standard argument," presumably because the editors did not understand the actual statement and solution of the problem (Stanley 2004). The result was therefore first published as Problem 3.75 in Cohen (1978) after Cohen learned of the result from Stanley. For this reason, the case is sometimes called "Stanley's theorem." Independent..

Touchard's congruence

when is prime and is a Bell number.

Partition function q

The number of partitions of with or fewer addends, or equivalently, into partitions with no element greater than . This function is denoted or . (Note that if " or fewer" is changed to "exactly " and "no element greater than " to "greatest element equal to ," then the partition function P of two arguments is obtained.)The such partitions can be enumerated in the Wolfram Language using IntegerPartitions[n, k].For example, the partitions of 5 of which the largest member is are , , , , and . Similarly, the five partitions of 5 into three or fewer parts are , , , , and .The satisfy the recurrence relationwith , , and for . The triangle of is given by(OEIS A026820).

Durfee square

The length of the largest-sized square contained within the Ferrers diagram of a partition. Its size can be determined using DurfeeSquare[f] in the Wolfram Language package Combinatorica` . The size of the Durfee square remains unchanged between a partition and its conjugate partition (Skiena 1990, p. 57). In the plot above, the Durfee square has size 3.

Durfee polynomial

Let be a family of partitions of and let denote the set of partitions in with Durfee square of size . The Durfee polynomial of is then defined as the polynomialwhere .

Tableau class

When a Young tableau is constructed using the so-called insertion algorithm, an element starts in some position on the first row, from which it may later be bumped. In contrast, the elements that start out in the th column are said to belong to the th class (Skiena 1990, p. 73). Tableau classes may be computed using TableauClasses[p] in the Wolfram Language package Combinatorica` .

Dirichlet's box principle

A.k.a. the pigeonhole principle. Given boxes and objects, at least one box must contain more than one object. This statement has important applications in number theory and was first stated by Dirichlet in 1834.In general, if objects are placed into boxes, then there exists at least one box containing at least objects, where is the ceiling function.

Stirling number of the second kind

The number of ways of partitioning a set of elements into nonempty sets (i.e., set blocks), also called a Stirling set number. For example, the set can be partitioned into three subsets in one way: ; into two subsets in three ways: , , and ; and into one subset in one way: .The Stirling numbers of the second kind are variously denoted (Riordan 1980, Roman 1984), (Fort 1948; Abramowitz and Stegun 1972, p. 822), (Jordan 1965), , , or Knuth's notation (Graham et al. 1994; Knuth 1997, p. 65). Abramowitz and Stegun (1972, p. 822) summarize the various notational conventions, which can be a bit confusing. The Stirling numbers of the second kind are implemented in the Wolfram Language as StirlingS2[n, m], and denoted .The Stirling numbers of the second kind for three elements are(1)(2)(3)Since a set of elements can only be partitioned in a single way into 1 or subsets,(4)Other special cases include(5)(6)(7)(8)The triangle of Stirling..

Partition function b_k

The number of partitions of in which no parts are multiples of is sometimes denoted (Gordon and Ono 1997). is also the number of partitions of into at most copies of each part.There is a special case(1)where is the partition function Q, and is the number of irreducible -modular representations of the symmetric group . The generating function for is given by(2)(3)where is a q-Pochhammer symbol.The following table gives the first few values of for small .OEIS2A0000091, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, ...3A0007261, 2, 2, 4, 5, 7, 9, 13, 16, 22, 27, 36, 44, 57, ...4A0019351, 2, 3, 4, 6, 9, 12, 16, 22, 29, 38, 50, 64, 82, ...5A0359591, 2, 3, 5, 6, 10, 13, 19, 25, 34, 44, 60, 76, 100, ...Gordon and Ono (1997) show that(4)(5)(6)Defining as the number of positive integers for which , Gordon and Ono (1997) proved that if , then(7)for all , where ...

Descending plane partition

A descending plane partition of order is a two-dimensional array (possibly empty) of positive integers less than or equal to such that the left-hand edges are successively indented, rows are nonincreasing across, columns are decreasing downwards, and the number of entries in each row is strictly less than the largest entry in that row. Implicit in this definition are the requirements that no "holes" are allowed in the array, all rows are flush against the top, and the diagonal element must be filled if any element of its row is filled. The above example shows a decreasing plane partition of order seven.The sole descending plane partition of order one is the empty one , the two of order two are "2" and , and the seven of order three are illustrated above. In general, the number of descending plane partitions of order is equal to the number of -bordered alternating sign matrices: 1, 2, 7, 42, 429, ... (OEIS A005130)...

Stanley's theorem

Stanley's theorem states that the total number of 1s that occur among all unordered partitions of a positive integer is equal to the sum of the numbers of distinct members of those partitions. The generalization sometimes known as Elder's theorem was discovered by R. P. Stanley in 1972 and submitted it to the "Problems and Solutions" section of the American Mathematical Monthly, where was rejected with the terse comment "A bit on the easy side, and using only a standard argument," presumably because the editors did not understand the actual statement and solution of the problem (Stanley 2004). The result was therefore first published as Problem 3.75 in Cohen (1978) after Cohen learned of the result from Stanley. For this reason, the case is sometimes called "Stanley's theorem."As an example of the theorem, note that the partitions of 5 are , , , , , , . There are a total of 1s in this list, which is equal..

Partition

A partition is a way of writing an integer as a sum of positive integers where the order of the addends is not significant, possibly subject to one or more additional constraints. By convention, partitions are normally written from largest to smallest addends (Skiena 1990, p. 51), for example, . All the partitions of a given positive integer can be generated in the Wolfram Language using IntegerPartitions[list]. PartitionQ[p] in the Wolfram Language package Combinatorica` can be used to test if a list consists of positive integers and therefore is a valid partition.Andrews (1998, p. 1) uses the notation to indicate "a sequence is a partition of ," and the notation , known as the frequency representation, to abbreviate the partition .The partitions on a number correspond to the set of solutions to the Diophantine equationFor example, the partitions of four, given by (1, 1, 1, 1), (1, 1, 2), (2, 2), (4), and (1, 3) correspond..

Cyclically symmetric plane partition

A plane partition whose solid Ferrers diagram is invariant under the rotation which cyclically permutes the -, -, and -axes. Macdonald's plane partition conjecture gives a formula for the number of cyclically symmetric plane partitions (CSPPs) of a given integer whose Ferrers diagrams fit inside an box. Macdonald gave a product representation for the power series whose coefficients were the number of such partitions of .

Solid partition

Solid partitions are generalizations of plane partitions. MacMahon (1960) conjectured the generating function for the number of solid partitions wasbut this was subsequently shown to disagree at (Atkin et al. 1967). Knuth (1970) extended the tabulation of values, but was unable to find a correct generating function. The first few values are 1, 4, 10, 26, 59, 140, ... (OEIS A000293).

Contained partition

A partition is said to contain another partition if the Ferrers diagram of contains the Ferrers diagram of . For example, (left figure) contains both and (right figures). Young's lattice is the partial order of partitions contained within ordered by containment (Skiena 1990, p. 77).

Schur's problem

Schur (1916) proved that no matter how the set of positive integers less than or equal to (where is the floor function) is partitioned into classes, one class must contain integers , , such that , where and are not necessarily distinct. The least integer with this property is known as the Schur number. The upper bound has since been slightly improved to .

Complementary bell number

The complementary Bell numbers, also called the Uppuluri-Carpenter numbers,(1)where is a Stirling number of the second kind, are defined by analogy with the Bell numbers(2)They are given by(3)where is a Bell polynomial.For , 1, ..., the first few are 1, , 0, 1, 1, , , , 50, 267, 413, ... (OEIS A000587).They have generating function(4)(5)(6)They have the series representation(7)They are prime (in absolute value) for , 36, 723, ... (OEIS A118018), corresponding to the prime numbers 2, 1454252568471818731501051, ... (OEIS A118019), with no others for (E. W. Weisstein, Mar. 21, 2009).

Göllnitz's theorem

Let denote the number of partitions of into parts (mod 12), let denote the number of partitions of into distinct parts (mod 6), and let denote the number of partitions of of the form(1)where , with strict inequality if or 3 (mod 6), and . Then(2)(Andrews 1986, p. 101).The values of for , 2, ... are 0, 1, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7, 7, 8, 9, ... (OEIS A056970). For example, for , there are eight partitions satisfying these conditions, as summarized in the following table.24The identity can be established using the identity(3)(4)(5)(6)(7)(8)(9)where is a q-Pochhammer symbol (Andrews 1986, p. 101). The assertion is significantly more difficult, and no simple proof is known. However, it can be established with the aid of computer algebra and the following refinement of the Göllnitz theorem.Let denote the number of partitions of into distinct parts , 4, 5 (mod 6). Let denote the number of partitions of of the form(10)where..

Schur number

The Schur number is the largest integer for which the interval can be partitioned into sum-free sets (Fredricksen and Sweet 2000). is guaranteed to exist for each by Schur's problem. Note the definition of the Schur number as the smallest number for which such a partition does not exist is also prevalent in the literature (OEIS A030126; Fredricksen and Sweet 2000).Schur (1916) gave the lower bound(1)which is sharp for , 2, and 3 (Guy 1994). The Schur numbers also satisfy the inequality(2)for and some constant (Abbott and Moser 1966, Abbott and Hanson 1972, Exoo 1994). Schur's Ramsey theorem also shows that(3)where is a Ramsey number. The first few Schur numbers are 1, 4, 13, 44, (Fredricksen 1979), , , ... (OEIS A045652; Fredricksen and Sweet 2000). is due to Baumert (Baumert 1965, Abbott and Hanson 1972), the lower bound on is due to Exoo (1994), and the lower limits on and are due to Fredricksen and Sweet (2000)...

Witt design

Given a pick-7 lottery with 23 numbers that pays a prize to anyone matching at least 4 of the 7 numbers, there is a set of 253 tickets that guarantees a win. This set corresponds to the Witt design.More formally, the Witt design on 23 points is a 4-(23,7,1) block design (Witt 1938). It is one of the most remarkable structures in all of combinatorics (Godsil and Royle 2001). It can be constructed by factoring over GF(2), into , whereThe 2048 powers , , , ..., are then computed, mod . This set of vectors happens to be the [23,12,7] Golay code with 253 weight-7 vectors, 1288 weight-11 vectors, and 506 weight-15 vectors. For example, is a weight-7 vector.The Witt design is the set of 253 weight-7 vectors acting on 23 points.Consider as vertices the 253 vectors () and 23 points (). Set edges such that are adjacent if , and are adjacent if they share a single term. Select an arbitrary vertex. For all 176 neighbors of that vertex, change edges to non-edges, and non-edges..

Baudet's conjecture

If , , ... are sets of positive integers andthen some contains arbitrarily long arithmetic progressions. The conjecture was proved by van der Waerden (1927) and is now known as van der Waerden's Theorem.According to de Bruijn (1977), "We do not know when and in what context he [Baudet] stated his conjecture and what partial results he had," although van der Waerden (1971, 1998) indicates he first heard of the problem in 1926.

Combinatorics

Combinatorics is the branch of mathematics studying the enumeration, combination, and permutation of sets of elements and the mathematical relations that characterize their properties.Mathematicians sometimes use the term "combinatorics" to refer to a larger subset of discrete mathematics that includes graph theory. In that case, what is commonly called combinatorics is then referred to as "enumeration."The Season 1 episode "Noisy Edge" (2005) of the television crime drama NUMB3RS mentions combinatorics.

Narayana number

The Narayan number for , 2, ... and , ..., gives a solution to several counting problems in combinatorics. For example, gives the number of expressions with pairs of parentheses that are correctly matched and contain distinct nestings. It also gives the number Dyck paths of length with exactly peaks.A closed-form expression of is given bywhere is a binomial coefficient.Summing over gives the Catalan numberEnumerating as a number triangle is called the Narayana triangle.

Combinatorial matrix theory

Combinatorial matrix theory is a rich branch of mathematics that combines combinatorics, graph theory, and linear algebra. It includes the theory of matrices with prescribed combinatorial properties, including permanents and Latin squares. It also comprises combinatorial proof of classical algebraic theorems such as Cayley-Hamilton theorem.As mentioned in Season 4 episodes 407 "Primacy" and 412 "Power" of the television crime drama NUMB3RS, professor Amita Ramanujan's primary teaching interest is combinatorial matrix theory.

Catalan's triangle

Catalan's triangle is the number triangle(1)(OEIS A009766) with entries given by(2)for . Each element is equal to the one above plus the one to the left. The sum of each row is equal to the last element of the next row and also equal to the Catalan number . Furthermore, .The coefficients also give the number of nonnegative partial sums of 1s and s, denoted by Bailey (1996), who gave the alternate form(3)(4)for .

Rooks problem

The rook is a chess piece that may move any number of spaces either horizontally or vertically per move. The maximum number of nonattacking rooks that may be placed on an chessboard is . This arrangement is achieved by placing the rooks along the diagonal (Madachy 1979). The total number of ways of placing nonattacking rooks on an board is (Madachy 1979, p. 47). In general, the polynomialwhose coefficients give the numbers of ways nonattacking rooks can be placed on an chessboard is called a rook polynomial.The number of rotationally and reflectively inequivalent ways of placing nonattacking rooks on an board are 1, 2, 7, 23, 115, 694, ... (OEIS A000903; Dudeney 1970, p. 96; Madachy 1979, pp. 46-54).The minimum number of rooks needed to occupy or attack all spaces on an chessboard is 8 (Madachy 1979), arranged in the same orientation as above.Consider an chessboard with the restriction that, for every subset of , a rook may not..

Boustrophedon transform

The boustrophedon ("ox-plowing") transform of a sequence is given by(1)(2)for , where is a secant number or tangent number defined by(3)The exponential generating functions of and are related by(4)where the exponential generating function is defined by(5)

Bernoulli number of the second kind

A number defined by , where is a Bernoulli polynomial of the second kind (Roman 1984, p. 294), also called Cauchy numbers of the first kind. The first few for , 1, 2, ... are 1, 1/2, , 1/4, , 9/4, ... (OEIS A006232 and A006233). They are given bywhere is a falling factorial, and have exponential generating function

Rook number

The rook numbers of an board are the number of subsets of size such that no two elements have the same first or second coordinate. In other word, it is the number of ways of placing rooks on a board such that none attack each other (one form of the so-called rooks problem). The rook number is therefore the leading coefficient of the corresponding rook polynomial .For an board, each permutation matrix corresponds to an allowed configuration of rooks. However, the permutation matrices give only a subset of the total number of solutions, which on an board is simply the factorial . This can be seen easily by noting that there are ways to place the first rook in the first column, ways to place the second rook in the second column, ways to place the third rook, ..., and a single way to place the th rook in the last (th) column.The rook numbers of a board determine the rook numbers of the complementary board , written as . This is known as the rook reciprocity theorem...

Irregular pair

If divides the numerator of the Bernoulli number for , then is called an irregular pair. For , the irregular pairs of various forms are for , for , none for , and for .

Ballot problem

Suppose and are candidates for office and there are voters, voting for and for . In how many ways can the ballots be counted so that is never ahead of ? The solution is a Catalan number .A related problem also called "the" ballot problem is to let receive votes and votes with . This version of the ballot problem then asks for the probability that stays ahead of as the votes are counted (Vardi 1991). The solution is , as first shown by M. Bertrand (Hilton and Pedersen 1991). Another elegant solution was provided by André (1887) using the so-called André's reflection method.The problem can also be generalized (Hilton and Pedersen 1991). Furthermore, the TAK function is connected with the ballot problem (Vardi 1991).

Handshake problem

Various handshaking problems are in circulation, the most common one being the following. In a room of people, how many different handshakes are possible?The answer is . To see this, enumerate the people present, and consider one person at a time. The first person may shake hands with other people. The next person may shake hands with other people, not counting the first person again. Continuing like this gives us a total number ofhandshakes, which is exactly the answer given above.Another popular handshake problem starts out similarly with people at a party. Not being able to shake hands with yourself, and not counting multiple handshakes with the same person, the problem is to show that there will always be two people at the party, who have shaken hands the same number of times.The solution to this problem uses Dirichlet's box principle. If there exists a person at the party, who has shaken hands zero times, then every person at the party has shaken..

Backtracking

A method of solving combinatorial problems by means of an algorithm which is allowed to run forward until a dead end is reached, at which point previous steps are retraced and the algorithm is allowed to run forward again. Backtracking can greatly reduce the amount of work in an exhaustive search. Backtracking is implemented as Backtrack[s, partialQ, solutionQ] in the Wolfram Language package Combinatorica` .Backtracking also refers to a method of drawing fractals by appropriate numbering of the corresponding tree diagram which does not require storage of intermediate results (Lauwerier 1991).

Glove problem

Let there be doctors and patients, and let all possible combinations of examinations of patients by doctors take place. Then what is the minimum number of surgical gloves needed so that no doctor must wear a glove contaminated by a patient and no patient is exposed to a glove worn by another doctor (where it is assumed that each doctor wears a glove on a single hand only)? In this problem, the gloves can be turned inside out and even placed on top of one another if necessary, but no "decontamination" of gloves is permitted. The optimal solution is(1)where is the ceiling function (Vardi 1991).The case is straightforward since two gloves have a total of four surfaces, which is the number needed for examinations. With doctors AB, patients ab, and gloves 12, a solution is A12a, A1b, B2a, B21b...

Fountain

An fountain is an arrangement of coins in rows such that exactly coins are in the bottom row and each coin in the st row touches exactly two in the th row. For example, a (21, 10) fountain is illustrated above.A generalized Rogers-Ramanujan-type continued fraction is closely related to the enumeration of coins in a fountain (Berndt 1985).

Alternating sign matrix conjecture

The conjecture that the number of alternating sign matrices "bordered" by s is explicitly given by the formulaThis conjecture was proved by Doron Zeilberger in 1995 (Zeilberger 1996a). This proof enlisted the aid of an army of 88 referees together with extensive computer calculations. A beautiful, shorter proof was given later that year by Kuperberg (Kuperberg 1996), and the refined alternating sign matrix conjecture was subsequently proved by Zeilberger (Zeilberger 1996b) using Kuperberg's method together with techniques from -calculus and orthogonal polynomials.

Triangle counting

Given rods of length 1, 2, ..., , how many distinct triangles can be made? Lengths for which(1)obviously do not give triangles, but all other combinations of three rods do. The answer is(2)The values for , 2, ... are 0, 0, 0, 1, 3, 7, 13, 22, 34, 50, ... (OEIS A002623). Somewhat surprisingly, this sequence is also given by the generating function(3)

Squarefree word

A "square" word consists of two identical adjacent subwords (for example, acbacb). A squarefree word contains no square words as subwords (for example, abcacbabcb). The only squarefree binary words are , , ab, ba, aba, and bab (since aa, bb, aaa, aab, abb, baa, bba, and bbb contain square identical adjacent subwords a, b, a, a, b, a, b, and b, respectively).However, there are arbitrarily long ternary squarefree words. The number of ternary squarefree words of length , 2, ... are 1, 3, 6, 12, 18, 30, 42, 60, ... (OEIS A006156), and is bounded by(Brandenburg 1983). In addition,(Brinkhuis 1983, Noonan and Zeilberger 1999).The number of squarefree quaternary words of length , 2, ... are 4, 12, 36, 96, 264, 696, ... (OEIS A051041).

Pólya enumeration theorem

A very general theorem that allows the number of discrete combinatorial objects of a given type to be enumerated (counted) as a function of their "order." The most common application is in the counting of the number of simple graphs of nodes, tournaments on nodes, trees and rooted trees with branches, groups of order , etc. The theorem is an extension of the Cauchy-Frobenius lemma, which is sometimes also called Burnside's lemma, the Pólya-Burnside lemma, the Cauchy-Frobenius lemma, or even "the lemma that is not Burnside's!"Pólya enumeration is implemented as OrbitInventory[ci, x, w] in the Wolfram Language package Combinatorica` .

Overlapfree word

A word is said to be overlapfree if it has no subwords of the form xyxyx. A squarefree word is overlapfree, and an overlapfree word is cubefree.The numbers of binary overlapfree words of length , 2, ... are 2, 4, 6, 10, 14, 20, ... (OEIS A007777). satisfies(1)for some constants and (Restivo and Selemi 1985, Kobayashi 1988). In addition, while(2)does not exist,(3)where(4)(5)(Cassaigne 1993).The Thue-Morse sequence is overlapfree (Alloucheand Shallit 2003, p. 15).

Normal form

The word "normal form" is used in a variety of different ways in mathematics. In general, it refers to a way of representing objects so that, although each may have many different names, every possible name corresponds to exactly one object (Petkovšek et al. 1996, p. 7). For example, the term "normal form" is used in linear algebra to describe matrices that have been transformed into certain special forms (e.g., Hermite normal form and Smith normal form), in logic to describe statements formulated in a standard way involving so-called literals (e.g., conjunctive normal form and disjunctive normal form), and in the theory of special functions to mean the uniquely-determined holonomic function (i.e., solution of a linear homogeneous ordinary differential equation with polynomial coefficients) of lowest order up to multiplication by polynomials (Koepf 1998, p. 2)...

Partition function p

, sometimes also denoted (Abramowitz and Stegun 1972, p. 825; Comtet 1974, p. 94; Hardy and Wright 1979, p. 273; Conway and Guy 1996, p. 94; Andrews 1998, p. 1), gives the number of ways of writing the integer as a sum of positive integers, where the order of addends is not considered significant. By convention, partitions are usually ordered from largest to smallest (Skiena 1990, p. 51). For example, since 4 can be written(1)(2)(3)(4)(5)it follows that . is sometimes called the number of unrestricted partitions, and is implemented in the Wolfram Language as PartitionsP[n].The values of for , 2, ..., are 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, ... (OEIS A000041). The values of for , 1, ... are given by 1, 42, 190569292, 24061467864032622473692149727991, ... (OEIS A070177).The first few prime values of are 2, 3, 5, 7, 11, 101, 17977, 10619863, ... (OEIS A049575), corresponding to indices 2, 3, 4, 5, 6, 13, 36, 77, 132,..

Latin square

An Latin square is a Latin rectangle with . Specifically, a Latin square consists of sets of the numbers 1 to arranged in such a way that no orthogonal (row or column) contains the same number twice. For example, the two Latin squares of order two are given by(1)the 12 Latin squares of order three are given by(2)and two of the whopping 576 Latin squares of order 4 are given by(3)The numbers of Latin squares of order , 2, ... are 1, 2, 12, 576, 161280, ... (OEIS A002860). The number of isotopically distinct Latin squares of order , 2, ... are 1, 1, 1, 2, 2, 22, 564, 1676267, ... (OEIS A040082).A pair of Latin squares is said to be orthogonal if the pairs formed by juxtaposing the two arrays are all distinct. For example, the two Latin squares(4)are orthogonal. The number of pairs of orthogonal Latin squares of order , 2, ... are 0, 0, 36, 3456, ... (OEIS A072377).The number of Latin squares of order with first row given by is the same as the number of fixed diagonal Latin..

Irregular prime

In a 1847 talk to the Académie des Sciences in Paris, Gabriel Lamé (1795-1870) claimed to have proven Fermat's last theorem. However, Joseph Liouville immediately pointed out an error in Lamé's result by pointing out that Lamé had incorrectly assumed unique factorization in the ring of -cyclotomic integers. Kummer had already studied the failure of unique factorization in cyclotomic fields and subsequently formulated a theory of ideals which was later further developed by Dedekind.Kummer was able to prove Fermat's last theorem for all prime exponents falling into a class he called "regular." "Irregular" primes are thus primes that are not a member of this class, and a prime is irregular iff divides the class number of the cyclotomic field generated by . Equivalently, but more conveniently, an odd prime is irregular iff divides the numerator of a Bernoulli number with .An infinite number..

Golomb ruler

An -mark Golomb ruler is a set of distinct nonnegative integers , called "marks," such that the positive differences , computed over all possible pairs of different integers , ..., with are distinct.Let be the largest integer in an -mark Golomb ruler. Then an -mark Golomb ruler is optimal if 1. There exists no other -mark Golomb rulers having smaller largest mark , and 2. The ruler is written in canonical form as the "smaller" of the equivalent rulers and , where "smaller" means the first differing entry is less than the corresponding entry in the other ruler. In such a case, is the called the "length" of the optimal -mark ruler.Thus, (0, 1, 3) is the unique optimal 3-mark Golomb ruler modulo reversal (i.e., (0, 2, 3) is considered the same ruler).For example, the set (0, 1, 3, 7) is 4-mark Golomb ruler since its differences are (, , , , , ), all of which are distinct. However, the unique optimal Golomb 4-mark ruler..

Josephus problem

Given a group of men arranged in a circle under the edict that every th man will be executed going around the circle until only one remains, find the position in which you should stand in order to be the last survivor (Ball and Coxeter 1987). The list giving the place in the execution sequence of the first, second, etc. man can be given by Josephus[n, m] in the Wolfram Language package Combinatorica` . For example, consider men numbered 1 to 4 such that each second () man is iteratively slaughtered, as illustrated above. As can be seen, the first man is slaughtered 4th, the second man 1st, the third man 3rd, and the fourth man 2nd, so Josephus[4, 2] returns 4, 1, 3, 2.To obtain the ordered list of men who are consecutively slaughtered, InversePermutation can be applied to the output of Josephus. So, in the above example, InversePermutation[Josephus[4, 2]] returns 2, 4, 3, 1 since the 2nd man is slaughtered first, the 4th man is slaughtered second, the 3rd man..

Random permutation

A random permutation is a permutation containing a fixed number of a random selection from a given set of elements. There are two main algorithms for constructing random permutations. The first constructs a vector of random real numbers and uses them as keys to records containing the integers 1 to . The second starts with an arbitrary permutation and then exchanges the th element with a randomly selected one from the first elements for , ..., (Skiena 1990).A random permutation on the integers can be implemented in the Wolfram Language as RandomSample[Range[n]]. A random permutation in the permutation graph pg can be computed using RandomPermutation[pg], and such random permutations by RandomPermutation[pg, n]. random permutations in the symmetric group of order can be computed using RandomPermutation[d, n].There are an average of permutation inversions in a permutation on elements (Skiena 1990, p. 29). The expected number of permutation..

Conjugate partition

Pairs of partitions for a single number whose Ferrers diagrams transform into each other when reflected about the line , with the coordinates of the upper left dot taken as (0, 0), are called conjugate (or transpose) partitions. For example, the conjugate partitions illustrated above correspond to the partitions and of 15. A partition that is conjugate to itself is said to be a self-conjugate partition.The conjugate partition of a given partition can be implemented in the Wolfram Language as follows: ConjugatePartition[l_List] := Module[ {i, r = Reverse[l], n = Length[l]}, Table[ n + 1 - Position[r, _?(# >= i&), Infinity, 1][[1, 1]], {i, l[[1]]} ] ]

Essentially unique

An object is unique if there is no other object satisfying its defining properties. An object is said to be essentially unique if uniqueness is only referred to the underlying structure, whereas the form may vary in ways that do not affect the mathematical content. For the sake of precision, the decomposition of a positive integer into prime factors is not strictly unique, but rather is essentially unique, because it is unique only up to insignificant formal modifications such as permutations of the factors () or changes of sign (). Similarly, the group of order 2 is essentially unique--despite the evidence that the additive group and the multiplicative group are different--because they are isomorphic groups, which differ only in the names given to their elements and their operations.

Cubefree word

A cubefree word contains no cubed words as subwords. The number of binary cubefree words of length , 2, ... are 2, 4, 6, 10, 16, 24, 36, 56, 80, 118, ... (OEIS A028445). Binary cubefree words satisfyThe number of ternary cubefree words of length , 2, ... are 3, 9, 24, 66, 180, 486, 1314, ... (OEIS A051042). The number of quaternary cubefree words of length , 2, ... are 4, 16, 60, 228, 864, 3264, 12336, ... (OEIS A051043).

Hadamard design

A symmetric block design (, , ) which is equivalent to a Hadamard matrix of order . It is conjectured that Hadamard designs exist for all integers , but this has not yet been proven. This elusive proof (or disproof) remains one of the most important unsolved problems in combinatorics.

Partial latin square

In a normal Latin square, the entries in each row and column are chosen from a "global" set of objects. Like a Latin square, a partial Latin square has no two rows or columns which contain the same two symbols. However, in a partial Latin square, each cell is assigned one of its own set of possible "local" (and distinct) symbols, chosen from an overall set of more than three distinct symbols, and these symbols may vary from location to location. For example, given the possible symbols which must be arranged asthe partial Latin squarecan be constructed.

Fisher's block design inequality

A balanced incomplete block design (, , , , ) exists only for (or, equivalently, ).

Unital

There are several different definitions of the term "unital" used throughout various branches of mathematics.In geometric combinatorics, a block design of the form (, , 1) is said to be a unital. In particular, then, a unital is a collection consisting of points and arranged into subsets so that for all and every pair of distinct points is contained in exactly one .A completely separate notion of unital is used ubiquitously throughout abstract algebra as an adjective to refer to an algebraic structure which contains a unit, e.g., a unitary ring is a ring which contains at least one unit. Algebraic structures of this kind are sometimes called unitary, though caution must be exhibited due to numerous unrelated mathematical notions which are themselves called unitary, e.g., unitary matrices which collectively form the unitary group, unitary elements, unitary divisors, etc. One must also exhibit caution when consulting literature..

Orthogonal array

An orthogonal array OA is a array with entries taken from an -set having the property that in any two rows, each ordered pair of symbols from occurs exactly once.

Euler square

A square array made by combining objects of two types such that the first and second elements form Latin squares. Euler squares are also known as Graeco-Latin squares, Graeco-Roman squares, or Latin-Graeco squares.For many years, Euler squares were known to exist for , 4, and for every odd except . Euler's Graeco-roman squares conjecture maintained that there do not exist Euler squares of order for , 2, .... However, such squares were found to exist in 1959, refuting the conjecture. As of 1959, Euler squares are known to exist for all except and .

Transversal design

A transversal design of order , block size , and index is a triple (, , ) such that 1. is a set of elements, 2. is a partition of into classes, each of size (the "groups"), 3. is a collection of -subsets of (the "blocks"), and 4. Every unordered pair of elements from is contained in either exactly one group or in exactly blocks, but not both.

Transversal array

A set of cells in an square such that no two come from the same row and no two come from the same column. The number of transversals of an square is ( factorial).A Latin transversal is a transversal such that no two cells contain the same element (Snevily 1999).

Magma

Throughout abstract algebra, the term "magma" is most often used as a synonym of the more antiquated term "groupoid," referring to a set equipped with a binary operator. The term is thought to have originated with Bourbaki.Unlike the term "groupoid" which has a number of different uses across algebra, the term "magma" has the benefit of being essentially unused in other contexts. On the other hand, the use of the term "magma" appears to be somewhat less common in literature.

Talisman square

An array of the integers from 1 to such that the difference between any one integer and its neighbor (horizontally, vertically, or diagonally, without wrapping around) is greater than or equal to some value is called a -talisman square. The above illustrations show (4, 2)-, (4, 3)-, (5, 4)-, and (6, 8)-talisman squares.

Dinitz problem

Given any assignment of -element sets to the locations of a square array, is it always possible to find a partial Latin square? The fact that such a partial Latin square can always be found for a array can be proven analytically, and techniques were developed which also proved the existence for and arrays. However, the general problem eluded solution until it was answered in the affirmative by Galvin in 1993 using results of Janssen (1993ab) and F. Maffray.

Talisman hexagon

An -talisman hexagon is an arrangement of nested hexagons containing the integers 1, 2, ..., , where is the th hex number, such that the difference between all adjacent hexagons is at least as large as a number . The hexagon illustrated above is a (3, 4)-talisman hexagon.

Symmetric block design

A symmetric design is a block design (, , , , ) with the same number of blocks as points, so (or, equivalently, ). An example of a symmetric block design is a projective plane.

Costas array

An order- Costas array is a permutation on such that the distances in each row of the triangular difference table are distinct. For example, the permutation has triangular difference table , , , and . Since each row contains no duplications, the permutation is therefore a Costas array.There is no known formula, recursion, or generating function for giving the number of Costas arrays of order . Several number-theoretic generators are known (Golomb 1984, Beard et al. 2004), but these do not generate all known Costas arrays of orders greater than .The numbers of Costas arrays for , 2, ... counting flipped and rotated matrices distinctly are 1, 2, 4, 12, 40,116, 200, 444, 760, 2160, 4368, 7852, 12828, 17252, 19612, 21104, 18276, 15096, 10240, 6464, 3536, 2052, 872, 200, 88, 56, 204, ... (OEIS A008404). Here, counts for , 25, and 26 were found by Beard et al. (2004, 2007). was verified by Rickard et al. (2006) and the case was solved by Drakakis et al. (2008).The..

Steiner triple system

Let be a set of elements together with a set of 3-subset (triples) of such that every 2-subset of occurs in exactly one triple of . Then is called a Steiner triple system and is a special case of a Steiner system with and . A Steiner triple system of order exists iff (Kirkman 1847). In addition, if Steiner triple systems and of orders and exist, then so does a Steiner triple system of order (Ryser 1963, p. 101).Examples of Steiner triple systems of small orders are(1)(2)(3)The Steiner triple system is illustrated above.The numbers of nonisomorphic Steiner triple systems of orders , 9, 13, 15, 19, ... (i.e., ) are 1, 1, 2, 80, 11084874829, ... (Stinson and Ferch 1985; Colbourn and Dinitz 1996, pp. 14-15; Kaski and Östergård 2004; OEIS A030129). is the same as the finite projective plane of order 2. is a finite affine plane which can be constructed from the array(4)One of the two s is a finite hyperbolic plane. The 80 Steiner triple systems..

Latin rectangle

A Latin rectangle is a matrix with elements such that entries in each row and column are distinct. If , the special case of a Latin square results. A normalized Latin rectangle has first row and first column . Let be the number of normalized Latin rectangles, then the total number of Latin rectangles is(1)(McKay and Rogoyski 1995), where is a factorial. Kerewala (1941) found a recurrence relation for , and Athreya et al. (1980) found a summation formula for .The asymptotic value of was found by Godsil and McKay (1990). The numbers of Latin rectangles are given in the following table from McKay and Rogoyski (1995). The entries and are omitted, since(2)(3)but and are included for clarity. The values of are given as a "wrap-around" series by OEIS A001009.1112113214234345211534654566253631064646552659408723097335792741293216751127040076169420808221198316737928442090950485272066580488633539018956887535281401856921668793103443808942076245602569511268164308377696129526054043811849722438296791669145698377597570964258816102148329103815499923210414717452105958410574698838307628646410687073540559100370944010717714429698305418592256010842920394215918542730035201097580721483160132811489280..

Steiner system

A Steiner system is a set of points, and a collection of subsets of of size (called blocks), such that any points of are in exactly one of the blocks. The special case and corresponds to a so-called Steiner triple system. For a projective plane, , , , and the blocks are simply lines.The number of blocks containing a point in a Steiner system is independent of the point. In fact,where is a binomial coefficient. The total number of blocks is also determined and is given byThese numbers also satisfy and .The permutations of the points preserving the blocks of a Steiner system is the automorphism group of . For example, consider the set of 9 points in the two-dimensional vector space over the field over three elements. The blocks are the 12 lines of the form , which have three elements each. The system is a because any two points uniquely determine a line.The automorphism group of a Steiner system is the affine group which preserves the lines. For a vector space of..

Steiner quadruple system

A Steiner quadruple system is a Steiner system , where is a -set and is a collection of -sets of such that every -subset of is contained in exactly one member of . Barrau (1908) established the uniqueness of ,and Fitting (1915) subsequently constructed the cyclic systems and , and Bays and de Weck (1935) showed the existence of at least one . Hanani (1960) proved that a necessary and sufficient condition for the existence of an is that or 4 (mod 6).The numbers of nonisomorphic Steiner quadruple systems of orders 8, 10, 14, 16, ... are 1, 1, 4 (Mendelsohn and Hung 1972), 1054163 (Kaski et al. 2006), ... (OEIS A124119).

Spherical design

is a spherical -design in iff it is possible to exactly determine the average value on of any polynomial of degree at most by sampling at the points of . In other words,Spherical -designs give the placement of points on a sphere for use in numerical integration with equal weights.

Block design

An incidence system (, , , , ) in which a set of points is partitioned into a family of subsets (blocks) in such a way that any two points determine blocks with points in each block, and each point is contained in different blocks. It is also generally required that , which is where the "incomplete" comes from in the formal term most often encountered for block designs, balanced incomplete block designs (BIBD).The five parameters are not independent, but satisfy the two relations(1)(2)A BIBD is therefore commonly written as simply (, , ), since and are given in terms of , , and by(3)(4)A BIBD is called symmetric if (or, equivalently, ).Writing and , then the incidence matrix of the BIBD is given by the matrix defined by(5)This matrix satisfies the equation(6)where is a identity matrix and is the unit matrix (Dinitz and Stinson 1992).Examples of BIBDs are given in the following table.block design(, , )affine plane(, , 1)Fano plane(7, 3, 1)Hadamard..

Soma

Let and be integers. A SOMA, or more specifically a SOMA, is an array , whose entries are -subsets of a -set , such that each element of occurs exactly once in each row and exactly once in each column of , and no 2-subset of is contained in more than one entry of (Soicher 1999).A SOMA can be constructed by superposing mutually orthogonal Latin squares of order with pairwise disjoint symbol-sets, and so a SOMA can be seen as a generalization of mutually orthogonal Latin squares of order .

Kirkman triple system

A Kirkman triple system of order is a Steiner triple system with parallelism (Ball and Coxeter 1987), i.e., one with the following additional stipulation: the set of triples is partitioned into components such that each component is a -subset of triples and each of the elements appears exactly once in each component. The Steiner triple systems of order 3 and 9 are Kirkman triple systems with and 1. Solution to Kirkman's schoolgirl problem requires construction of a Kirkman triple system of order .Ray-Chaudhuri and Wilson (1971) showed that there exists at least one Kirkman triple system for every nonnegative order . Earlier editions of Ball and Coxeter (1987) gave constructions of Kirkman triple systems with . For , there is a single unique (up to an isomorphism) solution, while there are 7 different systems for (Mulder 1917, Cole 1922, Ball and Coxeter 1987)...

Tower of hanoi

The tower of Hanoi (commonly also known as the "towers of Hanoi"), is a puzzle invented by E. Lucas in 1883. It is also known as the Tower of Brahma puzzle and appeared as an intelligence test for apes in the film Rise of the Planet of the Apes (2011) under the name "Lucas Tower."Given a stack of disks arranged from largest on the bottom to smallest on top placed on a rod, together with two empty rods, the tower of Hanoi puzzle asks for the minimum number of moves required to move the stack from one rod to another, where moves are allowed only if they place smaller disks on top of larger disks. The puzzle with pegs and disks is sometimes known as Reve's puzzle.The problem is isomorphic to finding a Hamiltonian path on an -hypercube (Gardner 1957, 1959).Given three rods and disks, the sequence giving the number of the disk ( to ) to be moved at the th step is given by the remarkably simple recursive procedure of starting with the list for..

Tangent number

The tangent numbers, also called a zag number, andgiven by(1)where is a Bernoulli number, are numbers that can be defined either in terms of a generating function given as the Maclaurin series of or as the numbers of alternating permutations on , 3, 5, 7, ... symbols (where permutations that are the reverses of one another counted as equivalent). The first few for , 2, ... are 1, 2, 16, 272, 7936, ... (OEIS A000182).For example, the reversal-nonequivalent alternating permutations on and 3 numbers are , and , , respectively.The tangent numbers have the generating function(2)(3)(4)Shanks (1967) defines a generalization of the tangent numbers by(5)where is a Dirichlet L-series, giving the special case(6)The following table gives the first few values of for , 2, ....OEIS1A0001821, 2, 16, 272, 7936, ...2A0004641, 11, 361, 24611, ...3A0001912, 46, 3362, 515086, ...4A0003184, 128, 16384, 4456448, ...5A0003204, 272, 55744, 23750912, ...6A0004116,..

Partition function q congruences

Odd values of are 1, 1, 3, 5, 27, 89, 165, 585, ... (OEIS A051044), and occur with ever decreasing frequency as becomes large (unlike , for which the fraction of odd values remains roughly 50%). This follows from the pentagonal number theorem which gives(1)(2)(3)(Gordon and Ono 1997), so is odd iff is of the form , i.e., 1, 5, 12, 22, 35, ... or 2, 7, 15, 26, 40, ....The values of for which is prime are 3, 4, 5, 7, 22, 70, 100, 495, 1247, 2072, 320397, ... (OEIS A035359), with no others for (Weisstein, May 6, 2000). These values correspond to 2, 2, 3, 5, 89, 29927, 444793, 602644050950309, ... (OEIS A051005). It is not known if is infinitely often prime, but Gordon and Ono (1997) proved that it is "almost always" divisible by any given power of 2 (1997).Gordon and Hughes (1981) showed that(4)and(5)where is an integer depending only on ...

Balanced binomial coefficient

An integer is -balanced for a prime if, among all nonzero binomial coefficients for , ..., (mod ), there are equal numbers of quadratic residues and nonresidues (mod ). Let be the set of integers , , that are -balanced. Among all the primes , only those with , 3, and 11 have .The following table gives the -balanced integers for small primes (OEIS A093755).2357111317

Enumerate

To enumerate a set of objects satisfying some set of properties means to explicitly produce a listing of all such objects. The problem of determining or counting all such solutions is known as the enumeration problem.A generating functionis said to enumerate (Hardy 1999, p. 85).

Large witt graph

The large Witt graph, also called the octad graph (Brouwer) or Witt graph (DistanceRegular.org), is the graph whose vertices are the 759 blocks of a Steiner system in which two blocks are adjacent whenever they are disjoint (Brouwer et al. 1989, p. 366).Perhaps the simplest construction is by selecting the 759 codewords of weight 8 of the extended binary Golay code and joining two words when they have disjoint support (i.e., if the codeword vectors are orthogonal).It is a distance-regular graph with intersection array and is also distance-transitive. It is an integral graph with graph spectrum . Its automorphism group has order , where is the largest Mathieu group. Its chromatic number is apparently unknown.The large Witt graph is implemented in the WolframLanguage as GraphData["LargeWittGraph"]...

Schmidt's problem

Schmidt (1993) proposed the problem of determining if for any integer , the sequence of numbers defined by the binomial sums(1)are all integers.The following table gives the first few values of for small .OEISvalues1A0018501, 3, 13, 63, 321, 1683, 8989, 48639, ...2A0052591, 5, 73, 1445, 33001, 819005, ...3A0928131, 9, 433, 36729, 3824001, 450954009, ...4A0928141, 17, 2593, 990737, 473940001, ...5A0928151, 33, 15553, 27748833, 61371200001, ...This was proved by Strehl (1993, 1994) and Schmidt (1995) for the case , corresponding to the Franel numbers. Strehl (1994) also found an explicit expression for the case . The resulting identities for are therefore known as the Strehl identities. The problem was restated in Graham et al. (1994, pp. 256 and 549), who indicated that H. S. Wilf had shown to be an integer for any for (Zudilin 2004).The problem was answered in the affirmative by Zudilin (2004), who found explicit expressions..

Worpitzky's identity

where is an Eulerian number and is a binomial coefficient (Worpitzky 1883; Comtet 1974, p. 242).

Strehl identities

The first Strehl identity is the binomial sum identity(Strehl 1993, 1994; Koepf 1998, p. 55), which are the so-called Franel numbers. For , 2, ..., the first few terms are 1, 2, 10, 56, 346, 2252, 15184, 104960, ... (OEIS A000172).The second Strehl identity is the binomial sum identity(Strehl 1993, 1994; Koepf 1998, p. 55) that is the case of Schmidt's problem. For , 1, 2, ..., these give the Apéry numbers 1, 5, 73, 1445, 33001, 819005, ... (OEIS A005259).

Binomial sums

The important binomial theorem states that(1)Consider sums of powers of binomial coefficients(2)(3)where is a generalized hypergeometric function. When they exist, the recurrence equations that give solutions to these equations can be generated quickly using Zeilberger's algorithm.For , the closed-form solution is given by(4)i.e., the powers of two. obeys the recurrence relation(5)For , the closed-form solution is given by(6)i.e., the central binomial coefficients. obeys the recurrence relation(7)Franel (1894, 1895) was the first to obtain recurrences for ,(8)(Riordan 1980, p. 193; Barrucand 1975; Cusick 1989; Jin and Dickinson 2000), so are sometimes called Franel numbers. The sequence for cannot be expressed as a fixed number of hypergeometric terms (Petkovšek et al. 1996, p. 160), and therefore has no closed-form hypergeometric expression.Franel (1894, 1895) was also the first to obtain the recurrence..

Classification theorem of finite groups

The classification theorem of finite simple groups, also known as the "enormous theorem," which states that the finite simple groups can be classified completely into 1. Cyclic groups of prime group order, 2. Alternating groups of degree at least five, 3. Lie-type Chevalley groups given by , , , and , 4. Lie-type (twisted Chevalley groups or the Tits group) , , , , , , , , , 5. Sporadic groups , , , , , , Suz, HS, McL, , , , He, , , , HN, Th, , , , O'N, , Ly, Ru, . The "proof" of this theorem is spread throughout the mathematical literature and is estimated to be approximately pages in length.

Krattenthaler matrix inversion formula

Let and be sequences of complex numbers such that for , and let the lower triangular matrices and be defined asandwhere the product over an empty set is 1. Then and are matrix inverses (Bhatnagar 1995, pp. 16-17).This result simplifies to the Gould and Hsu matrix inversion formula when , to Carlitz's -analog for (Carlitz 1972), and specialized to Bressoud's matrix theorem (Bressoud 1983) for and (Bhatnagar 1995, p. 17).The formula can also be extended to a summation theorem which generalizes Gosper's bibasic sum (Gasper and Rahman 1990, p. 240; Bhatnagar 1995, p. 19).

Leonard graph

The Leonard graph is a distance-regular graph on 288 vertices (Brouwer et al. 1989, p. 369) with intersection array . It is however not distance-transitive. It has graph spectrum .The Leonard graph is implemented in the WolframLanguage as GraphData["LeonardGraph"].The two halved Leonard graphs are also distance-regular, both with intersection array .

Doubly truncated witt graph

The doubly truncated Witt graph is the graph on 330 vertices related to a 3- design (Brouwer et al. 1989, p. 367). The doubly truncated Witt graph can be constructed by removing all vectors of the large Witt design containing any two arbitrarily chosen symbols. Consider the 759 vertices of the large Witt graph as words of weight 8 in extended binary Golay. Call the octads, and view them as sets of size 8. Pick one coordinate position. 253 octads have a 1 there, 506 octads have a 0 there. Pick a second coordinate position. Of the 506, there are 176 with a 1 there, and 330 with a 0. The induced subgraph from 759, or from 506 on this 330 gives the doubly truncated Witt graph (A. E. Brouwer, pers. comm., Jun. 8, 2009).It is an integral graph with graph spectrum , is weakly regular with parameters . It is also distance-transitive with intersection array . The order of its automorphism group is , where is a Mathieu group.This graph is implemented..

Four travelers problem

Let four lines in a plane represent four roads in general position, and let one traveler be walking along each road at a constant (but not necessarily equal to any other traveler's) speed. Say that two travelers and have "met" if they were simultaneously at the intersection of their two roads. Then if has met all other three travelers (, , and ) and , in addition to meeting , has met and , then and have also met!

Bell polynomial

There are two kinds of Bell polynomials.A Bell polynomial , also called an exponential polynomial and denoted (Bell 1934, Roman 1984, pp. 63-67) is a polynomial that generalizes the Bell number and complementary Bell number such that(1)(2)These Bell polynomial generalize the exponentialfunction.Bell polynomials should not be confused with Bernoulli polynomials, which are also commonly denoted .Bell polynomials are implemented in the Wolfram Language as BellB[n, x].The first few Bell polynomials are(3)(4)(5)(6)(7)(8)(9)(OEIS A106800). forms the associated Sheffer sequence for(10)so the polynomials have that exponentialgenerating function(11)Additional generating functions for are given by(12)or(13)with , where is a binomial coefficient.The Bell polynomials have the explicit formula(14)where is a Stirling number of the second kind.A beautiful binomial sum is given by(15)where is a binomial coefficient.The..

Birthday problem

Consider the probability that no two people out of a group of will have matching birthdays out of equally possible birthdays. Start with an arbitrary person's birthday, then note that the probability that the second person's birthday is different is , that the third person's birthday is different from the first two is , and so on, up through the th person. Explicitly,(1)(2)But this can be written in terms of factorials as(3)so the probability that two or more people out of a group of do have the same birthday is therefore(4)(5)In general, let denote the probability that a birthday is shared by exactly (and no more) people out of a group of people. Then the probability that a birthday is shared by or more people is given by(6)In general, can be computed using the recurrence relation(7)(Finch 1997). However, the time to compute this recursive function grows exponentially with and so rapidly becomes unwieldy.If 365-day years have been assumed, i.e.,..

Subfactorial

The th subfactorial (also called the derangement number; Goulden and Jackson 1983, p. 48; Graham et al. 2003, p. 1050) is the number of permutations of objects in which no object appears in its natural place (i.e., "derangements").The term "subfactorial "was introduced by Whitworth (1867 or 1878; Cajori 1993, p. 77). Euler (1809) calculated the first ten terms.The first few values of for , 2, ... are 0, 1, 2, 9, 44, 265, 1854, 14833, ... (OEIS A000166). For example, the only derangements of are and , so . Similarly, the derangements of are , , , , , , , , and , so .Sums and formulas for include(1)(2)(3)(4)where is a factorial, is a binomial coefficient, and is the incomplete gamma function.Subfactorials are implemented in the WolframLanguage as Subfactorial[n].A plot the real and imaginary parts of the subfactorial generalized to any real argument is illustrated above, with the usual integer-valued subfactorial..

Ordering

The number of "arrangements" in an ordering of items is given by either a combination (order is ignored) or a permutation (order is significant).An ordering (or order) is also a method for choosing the order in which elements are placed (i.e., a sorting function).The Wolfram Language function Ordering[p] gives the inverse permutation of a given permutation .

Roman coefficient

A generalization of the binomial coefficientwhose notation was suggested by Knuth,(1)where is a Roman factorial. The above expression is read "Roman choose ." Whenever the binomial coefficient is defined (i.e., or ), the Roman coefficient agrees with it. However, the Roman coefficients are defined for values for which the binomial coefficients are not, e.g.,(2)(3)where(4)The Roman coefficients also satisfy properties like those of the binomialcoefficient,(5)(6)an analog of Pascal's formula(7)and a curious rotation/reflection law due to Knuth(8)(Roman 1992).

Young's geometry

Young's geometry is a finite geometry which satisfiesthe following five axioms: 1. There exists at least one line. 2. Every line of the geometryhas exactly three points on it. 3. Not all points of the geometryare on the same line. 4. For two distinct points, there exists exactly one line on both of them. 5. If a point does not lie on a given line, then there exists exactly one line on that point that does not intersect the given line. Cherowitzo (2006) notes that the last axiom bears a strong resemblance to the parallel postulate of Euclidean geometry.

Three point geometry

Three point geometry is a finite geometry subjectto the following four axioms: 1. There exist exactly three points. 2. Two distinct points are on exactly one line.3. Not all the three points are collinear.4. Two distinct lines are on at least one point.Three point geometry is categorical.Like many finite geometries, the number of provable theorems in three point geometry is small. One can prove from this collection of axioms that two distinct lines are on exactly one point and that three point geometry contains exactly three lines. In this sense, three point geometry is extremely simple. On the other hand, note that the axioms say nothing about whether the lines are straight or curved, whereby it is possible that a number of different (but equivalent) visualizations of three point geometry may exist...

Subscribe to our updates
79 345 subscribers already with us
Math Subcategories
Check the price
for your project