Tag

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.

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..

Composition

The nesting of two or more functions to form a single new function is known as composition. The composition of two functions and is denoted , where is a function whose domain includes the range of . The notation(1)is sometimes used to explicitly indicate the variable.Composition is associative, so that(2)If the functions is continuous at and is continuous at , then is also continuous at .A function which is the composition of two other functions, say and , is sometimes said to be a composite function.Faà di Bruno's formula gives an explicit formula for the th derivative of the composition .A combinatorial composition is defined as an ordered arrangement of nonnegative integers which sum to (Skiena 1990, p. 60). It is therefore a partition in which order is significant. For example, there are eight compositions of 4,(3)(4)(5)(6)(7)(8)(9)(10)A positive integer has compositions.The number of compositions of into parts (where..

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).

Set partition

A set partition of a set is a collection of disjoint subsets of whose union is . The number of partitions of the set is called a Bell number.

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).

Lengyel's constant

Let denote the partition lattice of the set . The maximum element of is(1)and the minimum element is(2)Let denote the number of chains of any length in containing both and . Then satisfies the recurrence relation(3)where and is a Stirling number of the second kind. The first few values of for , 2, ... are then 1, 1, 4, 32, 436, 9012, 262760, ... (OEIS A005121).Lengyel (1984) proved that the quotient(4)is bounded between two constants as , and Flajolet and Salvy (1990) improved the result of Babai and Lengyel (1992) to show that(5)(OEIS A086053).

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)...

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.

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,..

Coin problem

Let there be integers with . The values represent the denominations of different coins, where these denominations have greatest common divisor of 1. The sums of money that can be represented using the given coins are then given by(1)where the are nonnegative integers giving the numbers of each coin used. If , it is obviously possibly to represent any quantity of money . However, in the general case, only some quantities can be produced. For example, if the allowed coins are , it is impossible to represent and 3, although all other quantities can be represented.Determining the function giving the greatest for which there is no solution is called the coin problem, or sometimes the money-changing problem. The largest such for a given problem is called the Frobenius number .The result(2)(3)(Nijenhuis and Wilf 1972) is mathematical folklore. The total number of such nonrepresentable amounts is given by(4)The largest nonrepresentable amounts for..

Frobenius number

The Frobenius number is the largest value for which the Frobenius equation(1)has no solution, where the are positive integers, is an integer, and the solutions are nonnegative integer. As an example, if the values are 4 and 9, then 23 is the largest unsolvable number. Similarly, the largest number that is not a McNugget number (a number obtainable by adding multiples of 6, 9, and 20) is 43.Finding the Frobenius number of a given problem is known as the coinproblem.Computation of the Frobenius number is implemented in the Wolfram Language as FrobeniusNumber[a1, ..., an].Sylvester (1884) showed(2)(3)

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]]} ] ]

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 ...

Newman's conjecture

If is an integer, then for every residue class (mod ), there are infinitely many nonnegative integers for which , where is the partition function P.

Postage stamp problem

Consider a set of positive integer-denomination postage stamps sorted such that . Suppose they are to be used on an envelope with room for no more than stamps. The postage stamp problem then consists of determining the smallest integer which cannot be represented by a linear combination with and .Without the latter restriction, this problem is known as the Frobenius problem or Frobenius postage stamp problem.The number of consecutive possible postage amounts is given by(1)where is called an -range.Exact solutions exist for arbitrary for and 3. The solution is(2)for . It is also known that(3)(Stöhr 1955, Guy 1994), where is the floor function, the first few values of which are 2, 4, 7, 10, 14, 18, 23, 28, 34, 40, ... (OEIS A014616; Guy 1994, p. 123).Hofmeister (1968, 1983) showed that for ,(4)where and are functions of (mod 9), and Mossige (1981, 1987) showed that(5)(Guy 1994, p. 123).Shallit (2002) proved that the (local) postage..

Waring's problem

In his Meditationes algebraicae, Waring (1770, 1782) proposed a generalization of Lagrange's four-square theorem, stating that every rational integer is the sum of a fixed number of th powers of positive integers, where is any given positive integer and depends only on . Waring originally speculated that , , and . In 1909, Hilbert proved the general conjecture using an identity in 25-fold multiple integrals (Rademacher and Toeplitz 1957, pp. 52-61).In Lagrange's four-square theorem, Lagrange proved that , where 4 may be reduced to 3 except for numbers of the form (as proved by Legendre; Hardy 1999, p. 12). In 1909, Wieferich proved that . In 1859, Liouville proved (using Lagrange's four-square theorem and Liouville polynomial identity) that . Hardy, and Little established , and this was subsequently reduced to by Balasubramanian et al. (1986). For the case , in 1896, Maillet began with a proof that , in 1909 Wieferich proved , and..

Partition function p congruences

The fraction of odd values of the partition function P(n) is roughly 50%, independent of , whereas odd values of occur with ever decreasing frequency as becomes large. Kolberg (1959) proved that there are infinitely many even and odd values of .Leibniz noted that is prime for , 3, 4, 5, 6, but not 7. In fact, values of for which is prime are 2, 3, 4, 5, 6, 13, 36, 77, 132, 157, 168, 186, ... (OEIS A046063), corresponding to 2, 3, 5, 7, 11, 101, 17977, 10619863, ... (OEIS A049575). Numbers which cannot be written as a product of are 13, 17, 19, 23, 26, 29, 31, 34, 37, 38, 39, ... (OEIS A046064), corresponding to numbers of nonisomorphic Abelian groups which are not possible for any group order.Ramanujan conjectured a number of amazing and unexpected congruences involving . In particular, he proved(1)using Ramanujan's identity (Darling 1919; Hardy and Wright 1979; Drost 1997; Hardy 1999, pp. 87-88; Hirschhorn 1999). Ramanujan (1919) also showed that(2)and..

Check the price
for your project
we accept
Money back
guarantee
100% quality