text: • 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]