• Non ci sono risultati.

# Leti k be the Stirling number of first kind which counts the number of permutations of {1, 2

N/A
N/A
Protected

Condividi "Leti 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.

Leti

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)kn k

 n − k m − k

 .

Note that nkn−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 andn−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]
The text passage is a solution to a mathematical problem from the American Mathematical Monthly, which involves the use of Stirling numbers of the first kind and the Inclusion-Exclusion Principle to find the degree of a polynomial.
no_question

the passage does not contain a mathematical question but rather provides a solution to a previously stated problem.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
• Non ci sono risultati.

# Leti k be the Stirling number of first kind which counts the number of permutations of {1, 2

N/A
N/A
Protected

Condividi "Leti 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.

Leti

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)kn k

 n − k m − k

 .

Note that nkn−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 andn−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]
user
The text passage is a solution to a mathematical problem from the American Mathematical Monthly, which involves the use of Stirling numbers of the first kind and the Inclusion-Exclusion Principle to find the degree of a polynomial.

TYPE: NO_QUESTION

The passage does not contain a mathematical question but rather provides a solution to a previously stated problem.