Liczby Eulera I-go rodzaju (rzędu)
Liczby Eulera I-go rodzaju (rzędu) wyrażają liczbę permutacji posiadających
k wzniesień (wzgórz) wśród wszystkich permutacji zbioru n-elementowego.
Liczby Eulera możemy obliczyć z wzoru:
n>k
albo z rekurencyjnego wzoru:
Wiemy, że:
,
,
Przykład 1
Wzgórze to sytuacja, gdy przed daną liczbą (wzgórze) występuje liczba od niej mniejsza.
n | k | Permutacje | ![]() |
---|---|---|---|
1 | 0 | {1} | ![]() |
2 | 0 | {2,1} | ![]() |
1 | {1,2} | ![]() |
|
3 | 0 | {3,2,1} | ![]() |
1 | {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2} | ![]() |
|
2 | {1,2,3} | ![]() |
k | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
0 | 1 | ||||||||||||||||||||
1 | 1 | 0 | |||||||||||||||||||
2 | 1 | 1 | 0 | ||||||||||||||||||
3 | 1 | 4 | 1 | 0 | |||||||||||||||||
4 | 1 | 11 | 11 | 1 | 0 | ||||||||||||||||
5 | 1 | 26 | 66 | 26 | 1 | 0 | |||||||||||||||
6 | 1 | 57 | 302 | 302 | 57 | 1 | 0 | ||||||||||||||
7 | 1 | 120 | 1191 | 2416 | 1191 | 120 | 1 | 0 | |||||||||||||
8 | 1 | 247 | 4293 | 15619 | 15619 | 4293 | 247 | 1 | 0 | ||||||||||||
9 | 1 | 502 | 14608 | 88234 | 156190 | 88234 | 14608 | 502 | 1 | 0 | |||||||||||
10 | 1 | 1013 | 47840 | 455192 | 1310354 | 1310354 | 455192 | 47840 | 1013 | 1 | 0 | ||||||||||
11 | 1 | 2036 | 152637 | 2203488 | 9738114 | 15724248 | 9738114 | 2203488 | 152637 | 2036 | 1 | 0 | |||||||||
12 | 1 | 4083 | 478271 | 10187685 | 66318474 | 162512286 | 162512286 | 66318474 | 10187685 | 478271 | 4083 | 1 | 0 | ||||||||
13 | 1 | 8178 | 1479726 | 45533450 | 423281535 | 1505621508 | 2275172004 | 1505621508 | 423281535 | 45533450 | 1479726 | 8178 | 1 | 0 | |||||||
14 | 1 | 16369 | 4537314 | 198410786 | 2571742175 | 12843262863 | 27971176092 | 27971176092 | 12843262863 | 2571742175 | 198410786 | 4537314 | 16369 | 1 | 0 | ||||||
15 | 1 | 32752 | 13824739 | 848090912 | 15041229521 | 102776998928 | 311387598411 | 447538817472 | 311387598411 | 102776998928 | 15041229521 | 848090912 | 13824739 | 32752 | 1 | 0 | |||||
16 | 1 | 65519 | 41932745 | 3572085255 | 85383238549 | 782115518299 | 3207483178157 | 6382798925475 | 6382798925475 | 3207483178157 | 782115518299 | 85383238549 | 3572085255 | 41932745 | 65519 | 1 | 0 | ||||
17 | 1 | 131054 | 126781020 | 14875399450 | 473353301060 | 5717291972382 | 31055652948388 | 83137223185370 | 114890380658550 | 83137223185370 | 31055652948388 | 5717291972382 | 473353301060 | 14875399450 | 126781020 | 131054 | 1 | 0 | |||
18 | 1 | 262125 | 382439924 | 61403313100 | 2575022097600 | 40457344748072 | 285997074307300 | 1006709967915228 | 1865385657780650 | 1865385657780650 | 1006709967915228 | 285997074307300 | 40457344748072 | 2575022097600 | 61403313100 | 382439924 | 262125 | 1 | 0 | ||
19 | 1 | 524268 | 1151775897 | 251732291184 | 13796160184500 | 278794377854832 | 2527925001876036 | 11485644635009424 | 27862280567093358 | 37307713155613000 | 27862280567093358 | 11485644635009424 | 2527925001876036 | 278794377854832 | 13796160184500 | 251732291184 | 1151775897 | 524268 | 1 | 0 | |
20 | 1 | 1048555 | 3464764515 | 1026509354985 | 73008517581444 | 1879708669896492 | 21598596303099900 | 124748182104463860 | 388588260723953310 | 679562217794156938 | 679562217794156938 | 388588260723953310 | 124748182104463860 | 21598596303099900 | 1879708669896492 | 73008517581444 | 1026509354985 | 3464764515 | 1048555 | 1 | 0 |