Matematické Fórum

↑ Andrejka3:
Keď som sa Googlu opýtal na "number of linear extensions" poset, tak mi vrátil napríklad takéto odkazy:

* Linear extension - Wikipedia
* Best known bounds for the number of linear extensions of a poset - MSE

Podľa tej literatúry, čo tam je uvedená, sa zdá, že sa okolo takýchto problémov robí nejaká celkom dosť seriózna matika.

A tipoval by som z toho, že asi nejaké úplne jednoduché vyjadrenie nie je. Ak ti teda náhodou nestačí nejaké rekurentné vyjadrenie - napríklad ako je uvedené tu: Paul Edelman, Takayuki Hibi, Richard P. Stanley: A recurrence for linear extensions; Order 1989, Volume 6, Issue 1, pp 15-18, DOI: 10.1007/BF00341632, free link.

EDIT: Aj podľa tohoto sa zdá, že to asi bolo pomerne dosť študované. V Richard P. Stanley: Enumberative combinatorics píšu

If , then an order-preserving bijection is called an extension of P to a total order or linear extension of P.
The number of extensions of P to a total order is denoted and is probably the single most useful number for measuring the "complexity" of P.

Andrejka3 napsal(a):

↑ kompik:
PS: v tom citovaném by mě zajímalo, v čem konkrétně by ta užitečnost mohla být (jen k měření složitosti?) :)

O kombinatorike toho viem veľmi málo - sem som skutočne napísal iba to, čo sa mi podarilo vygoogliť. Čiže k tomuto by pomohlo asi jedine zobrať si tú knihu a pozrieť sa, čo v nej s tým e(P) ešte robia. Alebo počkať, či sa tu vyjadrí niekto, kto sa v tejto oblasti vyzná.