Apr 4, 2016 - RESIDUE CLASSES. OLIVIA BECKWITH AND MICHAEL H. MERTENS. Abstract. Improving upon previous work  on the subject, we use Wright's Circle Method to derive an asymptotic formula for the number of parts in all partitions of an integer n
Oct 5, 2011 - that algebras HbA(E) are test algebras for the famous Michael's problem on the continuity of characters. ... are of the same type, see [31, p. 289-. 290]. We investigate this question for the case of holomorphic functions of bounded A-t
Dec 13, 2011 - Recall that a partition of a non-negative integer n is a non-increasing sequence of positive integers Î»1 ...Î»m that sum to n. .... must have MapleTM installed on your computer. Then download the file: .... systems (Maple in our case)
May 16, 2017 - number of positive integers at most x with no prime factors less than y. In this paper we ... Therefore, in what follows, we can restrict our attention to ..... of f(p) rounded to two decimal places; clearly, f(p) > 2.01 > g(p) for all
the graph obtained from G by deleting vertex v â VG, or edge uv â EG, respectively (this ... For v â VG, let NG(v) (or N(v) for short) denote the set of all the adjacent .... (iii) S6(G) = 2Ï(P2) + 12Ï(P3)+6Ï(P4) + 12Ï(K1,3) + 12Ï(H2) + 36
Oct 26, 2016 - girth, where the girth g of a graph is the length of a shortest cycle in the graph. Let G be ... A graph is triangle-free if it is K3-free. Let D be a digraph with vertex set V (D) and arc set A(D). The out-degree of a vertex v in D, d
Jul 3, 2008 - limited battery lifetime. 1 Introduction .... To enable us to reduce our problem to circular arc coloring, in Section 4 we define a parametrization ...
Aug 2, 2017 - numbers, partitions, and the set of divisors of a positive integer. .... of a finite arithmetic progression of integers of length k and difference t, that is ...
Jan 17, 2014 - this number-theoretical problem and the enumeration of microstates of the ideal two-dimensional Bose-gas is used. The conjectured ex-.
Nov 5, 2015 - can grow very fast, requiring the use of computer algebra in order to handle the complexity of the resulting expressions. There are ..... paper and we will limit ourselves to show explicitly how this works in practice with several examp
Dec 28, 2008 - (Dated: January 1, 2014). We study partition of networks into basins of attraction based on a steepest ascent search for the node of highest degree. Each node is associated with, or âattractedâ to its neighbor of maximal degree, as
Apr 27, 2017 - Marius TËarnËauceanu and LÃ¡szlÃ³ TÃ³th. Publications de ... , M. TËarnËauceanu [11, 12], M. Hampejs, N. Holighaus, L. TÃ³th, C. Wiesmeyr ,.
Apr 29, 2016 - into maximally nonparallel Hamming codes. â. Denis S. Krotovâ . Abstract. By using the Gold map, we construct a partition of the hypercube into cosets of Hamming codes such that for every two cosets the cor- responding Hamming codes
Jan 7, 2015 - with the numbers 1,...,2n in clockwise order, and join the two points in a pair with a chord for a pictorial representation. .... meeting (3) t s1. 1 s1! à¸à¸à¸ tsn n sn! = (2n)!. (2n + 1 - m)!. [xn]. T(x)m m! = 1 m(. 2n m - 1). [xn]
Dec 28, 2008 - sembles of maximally random scale-free (SF) networks. [1, 2, 3, 4]. ..... dom SF networks. In particular, hierarchical networks have a giant basin for small Î³, and a power-law distribu- tion of the basin sizes P(s) for large Î³, just
Sep 20, 2013 - Recently Tao, Croot and Helfgott  invented an al- gorithm to determine the parity of the number of primes in a given interval in O(x1/2âc+Îµ) ...
Apr 3, 2018 - pairs (Ï(Î),Ï(Îâ)) currently known to the author are (Ï, +â), where Ï is of the ... 2 below, which asserts the existence of linear forms of a given ...
May 29, 2015 - a rather slow procedure and we consider it far from being a satisfactory answer to Question 2. Irreducible ... that there exists no semigroup fulfilling the condition of having the given set as set of pseudo-Frobenius numbers, this app
Apr 30, 2018 - Key words: Independence number; linear map; TurÃ¡n graph; vertex permutation ..... financial support of China Scholarship Council. He thanks ...
Jul 19, 2017 - the group of decimals with addition modulo 1 and the induced order ([3, Theorem 7]). The first-order theories of (Z,+,0,
Oct 6, 2011 - 2 Institute of Information Systems, Vienna University of Technology, Vienna, Austria. [email protected] ... multisets of weighted objects (such as edges in a graph, or jobs to be scheduled). Such ..... programming algorithm comput
Oct 22, 2013 -  H. Rademacher, E. Grosswald, Dedekind sums. Mathematical Association of Amer- ica 1972. Kurt Girstmair. Institut fÃ¼r Mathematik. UniversitÃ¤t Innsbruck. Technikerstr. 13/7. A-6020 Innsbruck, Austria. [email protected] 7.
arXiv:0712.0120v1 [math.HO] 2 Dec 2007
On the partition of numbers into parts of a given type and number∗ Leonhard Euler
1. Some time ago I had treated the problem of the partition of numbers, which looks for how many different ways a given number can be separated into two, three, or generally any number, of parts. I had been careful that I present nothing about this solution by induction, as we often use in solving this kind of problem. The method which I used seems such that it could be applied with equal success to other problems, in particular the common problem which searches for how many ways a given number can be thrown as a given number of dice, which indeed I have decided to explain here in a way that can be easily generalized. 2. Since we are looking for how many ways a given number N can occur by throwing a given number n of dice, here the question reduces to this, how many distinct ways can can a given number N be resolved into n parts, which are altogether 1, 2, 3, 4, 5 or 6, if the sides of the dice are marked with these numbers. From this a more general question presents itself, in how many distinct ways can a given number N be divided into n parts, which are altogether α, β, γ, δ etc., the number of which is = m, such that both the number and type of parts, in which a given number shall be resolved, are given. 3. Namely let the dice, not just in this particular case of six sides, but indeed have m sides or faces, so that in each the sides are marked with the numbers α, β, γ, δ, etc., and one then asks how many ways a given number N can be produced by throwing n of these dice. It could also be assumed that the dice are different from each other, so that each would have a particular number of faces, which would moreover be inscribed with particular numbers; truly the solution of this question, which I have generalized from the common problem of dice, can found without excessive difficulty. 4. Indeed, I consider the numbers, which the sides of the dice are marked with, as exponents of some quantity x, so that for common dice we would have ∗ Presented to the St. Petersburg Academy on August 18, 1768. Originally published as De partitione numerorum in partes tam numero quam specie datas, Novi Commentarii academiae scientiarum Petropolitanae 14 (1770), 168–187. E394 in the Enestr¨ om index. Translated from the Latin by Jordan Bell, Department of Mathematics, University of Toronto, Toronto, Canada. Email: [email protected]
this expression x1 + x2 + x3 + x4 + x5 + x6 , where I take unity as the coefficient of each power, since each number is designated by the exponent equal to it. But if we take the square of this expression, each power of x will receive a coefficient that indicates how many ways this power can result from the multiplication of two terms of the expression, that is, how many ways its exponent can be produced from the addition of two numbers from the sequence 1, 2, 3, 4, 5, 6. Therefore by expanding the square of our expression, if the term M xN occurs in it, it follows from this that the number N can be thrown as two dice in as many ways as the coefficient M contains unities. 5. In a similar way, it is clear that if one takes the cube of this expression (x+x2 +x3 +x4 +x5 +x6 )3 , in its expansion any particular power xN occurs just as many times as the ways in which the exponent N can arise from the addition of three numbers from the sequence 1, 2, 3, 4, 5, 6; thus if M is the coefficient of a power, and the whole term is M xN , we conclude from this that the the number N can be produced from throws of three dice in as many ways as the coefficient M contains unities. Therefore in general, if n is taken as the exponent of our expression (x + x2 + x3 + x4 + x5 + x6 )n , by expanding according to powers of x, any term M xN shows that, if the number of dice = n, the number N can be made by throwing them together in as many ways as the coefficient M contains unities. 6. Therefore if the number of dice were = n and we search for how many ways a given number N can be made by throwing these, the question is resolved by the expansion of this formula (x + x2 + x3 + x4 + x5 + x6 )n ; now since the first term will be xn , the last indeed x6n , the progression of the terms follows in this way xn + Axn+1 + Bxn+2 + Cxn+3 + · · · + M xN + · · · + x6n , where for any term M xN it is clear that the number N which equals the exponent can be made in as many ways as the coefficient M contains unities; from this it is immediately clear that the question does not even occur unless the proposed number N is contained within the limits n and 6n. The whole matter thus now becomes that this progression, or the coefficients of all its terms, be assigned. 7. Therefore to find these, let the formula that is to be expanded be represented in this way xn (1 + x + x2 + x3 + x4 + x5 )n = V,
then indeed for its expansion let V = xn (1 + Ax + Bx2 + Cx3 + Dx4 + Ex5 + F x6 + etc.). V xn
And by putting
= Z by differentiating the logarithm it will be for the first
nx + 2nx2 + 3nx3 + 4nx4 + 5nx5 xdZ . = Zdx 1 + x + x2 + x3 + x4 + x5 As well, the value for the latter will follow xdZ Ax + 2Bx2 + 3Cx3 + 4Dx4 + 5Ex5 + 6F x6 + etc. = , Zdx 1 + Ax + Bx2 + Cx3 + Dx4 + Ex5 + F x6 + etc. and since these two expressions are equal to each other, from this the values of the coefficients can be determined. 8. Having constituted the equality of these two expressions, this equation follows nx
+nBx3 +2nA +3n
+nCx4 +2nB +3nA +4n
+3Cx3 +2B +A
+nDx5 +2nC +3nB +4nA +5n
+4Dx4 +3C +2B +A
+nEx6 +2nD +3nC +4nB +5nA
+5Ex5 +4D +3C +2B +A
+6F x6 +5E +4D +3C +2B +A
+nF x7 +2nE +3nD +4nC +5nB
+nGx8 +2nF +3nE +4nD +5nC
+7Gx7 +6F +5E +4D +3C +2B
+8Hx8 +7G +6F +5E +4D +3C
and these two expressions, since all their terms are equal to each other, will provide the values of all the coefficients. 9. The following determinations are now obtained: A =
Thus any coefficient can be determined by the preceding five, and with these found it will be V = xn + Axn+1 + Bxn+2 + Cxn+3 + Dxn+4 + Exn+5 + etc. and this is the general solution to the problem for n faces. 10. If each of the preceding is subtracted from the above equations, the following much simpler determinations can be obtained: A
= nA + n, = nB + nA + n,
= nC + nB + nA + n, = nD + nC + nB + nA + n,
= nE + nD + nC + nB + nA − 5n,
7G = nF + nE + nD + nC + nB − (5n − 1)A, 8H = nG + nF + nE + nD + nC − (5n − 2)B etc. If again the differences are taken, these relations will become even simpler, in this way: 2B 3C
11. Then, if the number of dice were 2, 3 or 4, the law for the progression of
the coefficients will be as follows, for two A=2 2B = 3A 3C = 4B 4D = 5C 5E = 6D 6F = 7E − 12 7G = 8F − 11A + 10 8H = 9G − 10B + 9A 9I = 10H − 9C + 8B 10K = 11I − 8D + 7C 11L = 12K − 7E + 6D 12M = 13L − 6F + 5E etc.
for three 3 4A 5B 6C 7D 8E − 18 9F − 17A + 15 10G − 16B + 14A 11H − 15C + 13B 12I − 14D + 12C 13K − 13E + 11D 14L − 12F + 10E etc.
for four 4 5A 6B 7C 8D 9E − 24 10F − 23A + 20 11G − 22B + 19A 12H − 21C + 18B 13I − 20D + 17C 14K − 19E + 16D 15L − 18F + 15E etc.
Therefore any coefficient can be determined by three preceding, where it is particularly noteworthy here that finally they shall abate to nothing, and the same happens for those following the first to disappear, which is not entirely clear from this law. 12. To help us clearly understand this law, let the formula (N )(n) denote the number of cases in which the number N can be made by n dice, so that it would be (n)(n) = 1,
(n + 1)(n) = A,
(n + 2)(n) = B,
(n + 4)(n) = D, . . . , (n + 9)(n) = I
(n + 3)(n) = C,
and (n + 10)(n) = K.
It will therefore be 10(n + 10)(n) = (n + 9)(n + 9)(n) − (6n − 4)(n + 4)(n) + (5n − 3)(n + 3)(n) , and here it can be concluded generally to be λ(n + λ)(n) = (n + λ − 1)(n + λ − 1)(n) − (6n + 6 − λ)(n + λ − 6)(n) + (5n + 7 − λ)(n + λ − 7)(n) . Let us now put n + λ = N , and so that λ = N − n, and it will be (N )(n) =
(N − 1)(N − 1)(n) − (7n + 6 − N )(N − 6)(n) + (6n + 7 − N )(N − 7)(n) , N −n
where it is noted to always be (P )(n) = 0 when P < n.
13. Also, these coefficients can easily be defined for any number of dice, if those for the number of dice one less are known. For if it were (x + x2 + x3 + x4 + x5 + x6 )n = xn + Axn+1 + Bxn+2 + Cxn+3 + Dxn+4 + etc. let it be put (x + x2 + x3 + x4 + x5 + x6 )n+1 xn+1 + A′ xn+2 + B ′ xn+3 + C ′ xn+4 + D′ xn+5 + etc. then it will be, because this expression is equal to the former multiplied by x + x2 + x3 + x4 + x5 + x6 , A′ = A + 1 B′ = B + A + 1 C′ = C + B + A + 1 D′ = D + C + B + A + 1 E′ = E + D + C + B + A + 1 F′ = F + E + D + C + B + A G′ = G + F + E + D + C + B etc.
then taking the differentials B ′ = A′ + B C ′ = B′ + C D′ = C ′ + D E ′ = D′ + E F ′ = E′ + F − 1 G′ = F ′ + G − A etc.
14. Thus if the way of denoting introduced above is used, from the equation G′ = F ′ + G − A it is (n + 8)(n+1) = (n + 7)(n+1) + (n + 7)(n) − (n + 1)(n) , which will be represented in general as (n + 1 + λ)(n+1) = (n + λ)(n+1) + (n + λ)(n) − (n + λ − 6)(n) . Now if n + λ is written for N , it will be (N + 1)(n+1) = (N )(n+1) + (N )(n) − (N − 6)(n) , where it should be noted that whenever N − 6 < n it will be (N − 6)(n) = 0. It is clear immediately that all these numbers are integers, which was less apparent from the previous law. 15. In these series also the properties found in §12 occur; thus if n = 6, it will be (N )(6) =
(N − 1)(N − 1)(6) − (48 − N )(N − 6)(6) + (43 − N )(N − 7)(6) , N −6
where, if for example N = 25, it will be (25)(6) =
24 · (24)(6) − 23 · (19)(6) + 18 · (18)(6) ; 19 6
Table 1: Exhibiting how many ways a number N can be made by n dice N n=1 1 1 2 1 3 1 4 1 1 5 6 1 0 7 0 8 9 0 0 10 11 0 12 0 0 13 14 0 15 0 0 16 17 0 18 0 19 0 20 0 0 21 22 0 23 0 0 24 25 0 0 26 27 0 28 0 29 0 30 0 31 0 0 32 33 0 0 34 35 0 36 0
as is obtained in the table. Similarly if N = 29, it will be (29)(6) =
28 · (28)(6) − 19 · (23)(6) + 14 · (22)(6) ; 23
then because (28)(6) = 1161, (23)(6) = 3906 and (22)(6) = 4221 it will be (29)(6) =
32508 − 74214 + 59094 17388 = = 756. 23 23
16. Truly the expansion of the formula V (§7) can be done in a different way, such that any term can be completely assigned without the use of the preceding. For since it is 1 − x6 1 + x + x2 + x3 + x4 + x5 = , 1−x it will be xn (1 − x6 )n V = (1 − x)n and by expanding (1 − x6 )n
xn (1 − x)n
n 6 n(n − 1) 12 n(n − 1)(n − 2) 18 x + x − x 1 1·2 1·2·3 n(n − 1)(n − 2)(n − 3) 24 + x − etc., 1·2·3·4 1−
n n+1 n(n + 1) n+2 n(n + 1)(n + 2) n+3 x + x + x 1 1·2 1·2·3 n(n + 1)(n + 2)(n + 3) n+4 x + etc. + 1·2·3·4 xn +
17. This solution can be adapted to dice possessing any other number of faces. For let the number of faces on all the dice be m, which shall be marked with the numbers 1, 2, 3, . . . , m, while the number of dice itself shall be = n for which the number of throws are sought in which the given number N land. Or, 9
which ends up being the same thing, it is sought how many ways the number N can be resolved into n parts, each of which is comprised from the sequence of numbers 1, 2, 3, . . . , m; here indeed it should be noted that not only different partitions but also different orders of the same parts are counted, as usually happens in dice, where for example the throws 3, 4 and 4, 3 are considered to be two different cases. 18. But if therefore this symbol (N )(n) denotes the number of cases in which the number N can be produced by throwing n dice, each of which have m sides marked with the numbers 1, 2, 3, . . . , m, it should first be noted that (n)(n) = 1, and if N < n then (N )(n) = 0. Next, if N = mn then too (mn)(n) = 1, and if N > mn it will be (N )(n) = 0. Finally, if either N = n + λ or N = mn − λ, the number of cases is the same, namely (n + λ)(n) = (mn − λ)(n) . The first formula can also be developed as (n + λ)(n)
19. As well, these numbers can very easily be determined from the preceding, where the number of dice is one less. For in general it will be, if the number of all the dice were = m and each were marked with the numbers 1, 2, 3, . . . , m, (N + 1)(n+1) = (N )(n+1) + (N )(n) − (N − m)(n) or (N + 1)(n) = (N )(n) + (N )(n−1) − (N − m)(n−1) . Then, if n + λ is written for N + 1, we will obtain (n + λ)(n) = (n + λ − 1)(n) + (n + λ − 1)(n−1) − (n + λ − m − 1)(n−1) . Finally, for the same number of dice, this number n depends thus on preceding numbers λ(n + λ)(n)
(n + λ − 1)(n + λ − 1)(n) − (mn + m − λ)(n + λ − m)(n) +(mn − n + m + 1 − λ)(n + λ − m − 1)(n) .
Again it is noted that the sum of all these numbers is = mn . 20. The question can be resolved in a similar way even if not all the dice occur with the same number of faces. Let us take three dice, the first a hexahedron bearing the numbers 1, 2, 3, 4, 5, 6, the second an octahedron bearing 10
the numbers 1, 2, 3, . . . , 8, and the third a dodecahedron bearing the numbers 1, 2, 3, . . . , 12; if we now ask for how many ways a given number N can be decomposed, we should expand this product (x + x2 + x3 + · · · + x6 )(x + x2 + x3 + · · · + x8 )(x + x2 + x3 + · · · + x12 ) = V, and the coefficient of the power xN will display the number of cases. Now, since here it will be x3 (1 − x6 )(1 − x8 )(1 − x12 ) V = , (1 − x)3 by expanding the numerator it will be V =
1 + 3x + 6x2 + 10x3 + 15x4 + 21x5 + 28x6 + 36x7 + etc., whose coefficients are the triangular numbers; and since the nth triangular num, any term of this series will be ber is n(n+1) 2 n(n + 1) n−1 x 2
(n − 1)(n − 2) n−3 x . 2
Now multiplying by the numerator, the coefficient of the power xn turns out to be (n − 1)(n − 2) (n − 7)(n − 8) (n − 9)(n − 10) (n − 13)(n − 14) − − − 2 2 2 2 (n − 15)(n − 16) (n − 19)(n − 20) (n − 21)(n − 22) (n − 27)(n − 28) + + + . + 2 2 2 2 This expression does not need to be continued beyond the case when negative factors are arrived at. 22. Noticing however for the denominator (1 − x)3 = 1 − 3x + 3x2 − x3 , the series that is sought will be recurrent, arising from the ladder relation 3, −3, +1, providing that we have the rule for the terms of the numerator. Then the
The numbers here are not greater than 26, since 26 = 6 + 8 + 12, and the sum of all the cases is 576 = 6 · 8 · 12. 23. Since here we have succeeded in the resolution of numbers into parts of a given number and type without the help of induction, some elegant Theorems of Fermat come to my mind; while they have not yet been demonstrated, it seems that this method will perhaps lead to demonstrations of them. For Fermat had asserted that all numbers are either triangles or the aggregate of two or three triangles, and because zero also occurs in the order of triangles, the theorem can thus be stated as that all numbers can be resolved into three triangles. Thus if the triangular numbers are taken for exponents and this series is formed 1 + x1 + x3 + x6 + x10 + x15 + x21 + x28 + etc. = S, it needs to be demonstrated that if the cube of this series is expanded, then every power of x occurs without omission; for if this could be demonstrated, the demonstration of this Theorem of Fermat would be possessed. 24. In a similar way, if we take the fourth power of this series 1 + x1 + x4 + x9 + x16 + x25 + x36 + etc. = S, and we could show that every power of x occurs in it, then we would have a demonstration of the Theorem of Fermat, that all numbers are made from the addition of four squares. Indeed in general if we put S = 1 + x1 + xm + x3m−3 + x6m−8 + x10m−15 + x15m−24 + x21m−35 + etc. and we take the power of this series of the exponent m, it needs to be demonstrated that every power of x will be produced in it, and thus that all numbers are the aggregate of m or less polygonal numbers with a number of sides = m. 12
25. From these same principles another way presents itself for investigating the demonstrations, which differs from the preceding in that where there not only different parts but also different orders were considered, here the stipulation about the order is omitted. Namely for the resolution into triangular numbers let this formula be constituted (1 − z)(1 − xz)(1 −
1 , − x6 z)(1 − x10 z)(1 − x15 z) etc.
which expanded produces this series 1 + P z + Qz 2 + Rz 3 + Sz 4 + T z 5 + etc., such that P, Q, R, S etc. are some functions of x. Now it will clearly be P = 1 + x + x3 + x6 + x10 + x15 + x21 + etc.; while Q will also contain those powers of x whose exponents are the aggregate of two triangles. It therefore needs to be be demonstrated that every power of x occurs in the function R. 26. In a similar way for the resolution of numbers into four squares, let this fraction be expanded 1 ; (1 − z)(1 − xz)(1 − x4 z)(1 − x9 z)(1 − x16 z)(1 − x25 z) etc. then if it is changed into the form 1 + P z + Qz 2 + Rz 3 + Sz 4 + etc., it needs to be demonstrated that the function S contains every power of x. For instance, P is equal to the series 1 + x + x4 + x9 + x16 + etc. and Q also contains those powers of x whose exponents are the aggregate of two squares, in which series therefore many powers are still absent. Further, in R there are the additional powers whose exponents are the aggregate of three squares, and then in S those will occur whose exponents are the sum of four, so that in S all numbers should occur as exponents. 27. From this principle, we can define how many solutions those problems admit which are commonly referred to by Arithmeticians as the Regula Virginum1 . In this way, the problems are reduced here to finding numbers p, q, r, s, t etc. that satisfy these two conditions ap + bq + cr + ds + etc. = n, and αp + βq + γr + δs + etc. = ν, 1 Translator: In English, Rule of the Virgins. See Volume II of Leonard Eugene Dickson’s History of the Theory of Numbers, under the indices “Coeci rule” and “Virgins”.
and now the question is, how many solutions occur in positive integers; where indeed the numbers a, b, c, d etc., n and α, β, γ, δ etc., ν may be taken to be integers, as if this were not so, it can be easily reduced to this. It is at once apparent that if two numbers p and q are given to be investigated, more than one solution cannot be given. Commonly the problem only occurs with positive integral numbers for p and q. 28. Now, for defining the number of all the solutions in any particular case, so that nothing is done by induction or by trials, let us consider this expression 1 (1 − xa y α )(1 − xb y β )(1 − xc y γ )(1 − xd y δ ) etc. and let it be expanded, which yields such a series 1 + Ax... y ... + Bx... y ... + Cx... y ... etc.; if the term N xn y ν occurs in this, the coefficient N will indicate the number of solutions; and if it turns out that this term does not occur, this indicates that there will be no solution. Thus the whole problem turns here on investigating the coefficient of the term xn y ν .