• Non ci sono risultati.

# Leti k be the Stirling number of first kind which counts the number of permutations of {1, 2

N/A
N/A
Protected

Condividi "Leti k be the Stirling number of first kind which counts the number of permutations of {1, 2"

Copied!
1
0
0

Testo completo

(1)

Problem 11403

(American Mathematical Monthly, Vol.115, December 2008) Proposed by Yaming Yu (USA).

Letn be an integer greater than 1, and let fn be the polynomial given by

n

X

i=0

n i



(−x)n−i

i−1

Y

j=0

(x + j).

Find the degree offn.

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

Leti

k be the Stirling number of first kind which counts the number of permutations of {1, 2, . . . , i}

with k-cycles. Since

i−1

Y

j=0

(x + j) = xi=

i

X

k=0

 i k

 xk then the coefficient of xmin fn is

an,m=

n

X

i=0

n i



(−1)n−i

 i

m − (n − i)



=

n

X

k=0

(−1)kn k

 n − k m − k

 .

Note that nkn−k

m−k is the number of permutations of {1, 2, . . . , n} which have m cycles with at least k fixed points (a fixed point is a cycle of length 1): nk is the number of ways of choosing k fixed points andn−k

m−k is the number of ways of completing the permutation with other m − k cycles.

Hence the formula of an,m can be seen as an application of the Inclusion-Exclusion Principle and it follows that an,m is the number of permutations of {1, 2, . . . , n} with m cycles of length greater than 1. So, an,m= 0 when 2m > n that is if m > ⌊n/2⌋ and an,m> 0 when m = ⌊n/2⌋ because

(1, 2)(3, 4) . . . (n − 1, n) for n even and (1, 2)(3, 4) . . . (n − 2, n − 1, n) for n odd have ⌊n/2⌋ cycles of length greater than 1.

Hence the degree of fn is ⌊n/2⌋. 

Riferimenti

Documenti correlati

Two families of non-overlapping coercive domain decomposition methods are proposed for the numerical approximation of advection dominated advection-di usion equations and

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

[r]

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

For positive integer n and i ∈ {0, 1}, let D i (n) be the number of derangements on n elements whose number of cycles has the same parity

, 2n} with n cycles all of length greater than 1, that is with all cycles of

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]