• Non ci sono risultati.

# The (unsigned) Stirling number of the first kind  n k  counts the number of permutations of n objects with k cycles

N/A
N/A
Protected

Condividi "The (unsigned) Stirling number of the first kind  n k  counts the number of permutations of n objects with k cycles"

Copied!
1
0
0

Testo completo

(1)

Problem 11668

(American Mathematical Monthly, Vol.119, October 2012)

Proposed by Dimitris Stathopoulos (Greece).

For positive integer n and i ∈ {0, 1}, let Di(n) be the number of derangements on n elements whose number of cycles has the same parity as i. Prove that D1(n) − D0(n) = n − 1.

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

The (unsigned) Stirling number of the first kind  n k



counts the number of permutations of n objects with k cycles. Hence, by the inclusion-exclusion principle, the number of derangements (permutations without fixed points) of n objects with k cycles is given by the formula

D(n, k) =

k

X

j=0

(−1)jn j

  n − j k − j

 .

It follows that

D1(n) − D0(n) =

bn/2c

X

k=0

D(n, 2k + 1) −

bn/2c

X

k=1

D(n, 2k) =

n

X

k=1

(−1)k−1D(n, k)

=

n

X

k=0

(−1)k−1

k

X

j=0

(−1)jn j

  n − j k − j



=

n

X

j=0 n

X

k=j

(−1)j+k−1n j

  n − j k − j



=

n

X

j=0 n−j

X

k=0

(−1)k−1n j

  n − j k



= −

n

X

j=0

n j

 j X

k=0

(−1)k j k



= −

1

X

j=0

n j

 j X

k=0

(−1)k j k



= −(1 + n(0 − 1)) = n − 1.

where in the last step we used the fact that for j > 1

j

X

k=0

(−1)k j k



=

j

X

k=0

 j k

 xk

!

x=−1

= (x(x + 1) . . . (x + j − 1))x=−1= 0.



Riferimenti

Documenti correlati

[r]

Moreover, if we remove from G all the edges of a single path, then the number of vertices of odd degree decreases at most by two (namely the vertices at the start and at the end of

(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

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

[r]

, 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]