Strona główna

Spostrzeżenie kluczowe niech np n = 6 & k = 4, wtedy = + + + + Istotnie: 4-inwersje 


Pobieranie 34.56 Kb.
Data18.06.2016
Rozmiar34.56 Kb.
C] liczba permutacji o k inwersjach

Def. Inwersja permutacji to para taka, że i>.

Pytanie: = ?

Przykład: Patrz następna strona.

Spostrzeżenie kluczowe niech np. n = 6 & k = 4 , wtedy

= + + + +

Istotnie:

4-inwersje  4-inwersje 

= ,,,,  ,,,,,6 =

3-inwersje  4-inwersje 

= ,,,,  ,,,,6, =

2-inwersje  4-inwersje 

= ,,,,  ,,,6,, =

1-inwersja  4-inwersje 

= ,,,,  ,,6,,, =

0-inwersji  4-inwersje 

= ,,,,  ,6,,,, =
r
ównanie rekurencyjne


=

potęgowa funkcja tworząca:



=

rozwiązanie

Łatwo stwiedzić [ćw.D] (rozpisz szeregi w wiersze- staranie by co trzeba było w tych co trzeba kolumnach napisu) wykorzystując rekurencję na , że


=

gdzie


.

dodano 2009-08-30 skąd



=!  ...

czyli


= .

patrz: The permutahedron for n=4 http://garsia.math.yorku.ca:16080/~zabrocki/posets/phedron4/



the member of the Institute of Combinatorics and Applications

a.krzysztof kwaśniewski



a.k.k.

dodano 2009-08-30
The number of those among n! words (permutations) ttat show precisely k inversions is given by

! =

patrz

[PA] G. Polya, G. Alexanderson, Gaussian binomial coefficients, Elem. Math. 26 (1971) 102-109.
wynik znany z
E. Netto, Lehrbuch der Combinatorik. 2end ed. (Leipzig & Berlin 1927) p. 94-97.  [7] in [PA]
patrz także:
Maurice G. Kendall, A. Stuart The advanced theory of statistics (London, 1961), v.2 see p.479 and p.964  [4] and [7] in [PA]


dodano 2009-08-30

ad tzw. Mahattan paths: w/g

Z. Palka , A. Ruciński „Wykłady z Kombinatoryki - Część I WNT Warszawa 1998

patrz:

patrz: zigzag paths in [P]

[P] G. Pólya, Mathematical discovery (Viley 1962) v.1, see pp. 68-75

and in [PA]



[PA] G. Polya, G. Alexanderson, Gaussian binomial coefficients, Elem. Math. 26 (1971) 102-109.

ad tzw. Mahattan: w/g



Z. Palka , A. Ruciński „Wykłady z Kombinatoryki - Część I WNT Warszawa 1998

patrz:



©snauka.pl 2016
wyślij wiadomość