• Non ci sono risultati.

# Let p be the Euler partition function, i.e., p(n) is the number of nondecreasing lists of positive integers that sum to n

N/A
N/A
Protected

Condividi "Let p be the Euler partition function, i.e., p(n) is the number of nondecreasing lists of positive integers that sum to n"

Copied!
1
0
0

Testo completo

(1)

Problem 11675

(American Mathematical Monthly, Vol.119, November 2012) Proposed by Mircea Merca (Romania).

Let p be the Euler partition function, i.e., p(n) is the number of nondecreasing lists of positive integers that sum to n. Let p(0) = 1, and let p(n) = 0 for n < 0. Prove that for n ≥ 0 with n 6= 3,

p(n) − 4p(n − 3) + 4p(n − 5) − p(n − 8) > 0.

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.

Let P (x) be the generating function of the integer partitions

P (x) =

X

n=0

p(n)xn=

Y

n=1

1 1 − xn.

We have to prove that, in the following generating function, the coefficient of xn is positive for all n 6= 3:

X

n=0

(p(n) − 4p(n − 3) + 4p(n − 5) − p(n − 8))xn

= (1 − 4x3+ 4x5− x8)P (x)

= (x2(1 − x)(1 − x)(1 − x2) + (x2+ x + 1)(1 − x)(1 − x2)(1 − x3))P (x)

= (x2− x3)

Y

n=3

1

1 − xn + (x2+ x + 1)

Y

n=4

1 1 − xn.

Let pa(n) be the number of of nondecreasing lists of positive integers greater or equal to a that sum to n. Then

(x2− x3)

Y

n=3

1 1 − xn =

X

n=0

(p3(n − 2) − p3(n − 3))xn= x2− x3+ x5+ x8+ . . .

and the coefficient of xn is non-negative for all n 6= 3. Infact p3(n − 2) ≥ p3(n − 3) ≥ 1 for all n ≥ 6 because there is an injective map from the partitions counted by p3(n − 3) to the the ones counted by p3(n − 2), given by adding 1 to the greatest number in a list. Moreover

(x2+ x + 1)

Y

n=4

1 1 − xn =

X

n=0

(p4(n − 2) + p4(n − 1) + p4(n))xn= 1 + x + x2+ x4+ . . .

and the coefficient of xn is positive for all n 6= 3 (note that p4(n) ≥ 1 for all n ≥ 4). 

Riferimenti

Documenti correlati

[r]

[r]

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit` a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.. If M is finite then the

[r]

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit` a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy. Let N b (k) be the set of

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.. For k

in such a way that U 1 receives at least one ball, and while any balls remain, each successive urn receives at least as many balls as in all the previous urns combined.. Let b(n)

[r]