Schröderjevo število

Schröderjeva števila so v matematiki členi zaporedja naravnih števil določeni z rekurenčno enačbo:

$S_{0}=1\qquad {\mbox{ in }}\qquad S_{n}=S_{n-1}+\sum _{i=0}^{n-1}S_{i}S_{n-1-i}\quad {\mbox{ za }}n\geq 1\;.$

Schröderjeva števila predstavljajo število poti na mreži (n + 1) × (n + 1) v kartezični ravnini, ki potekajo od izhodišča (0,0) do točke (n,n) in ne vsebujejo nobene točke nad premico y = x. Poleg tega so na teh poteh, ki jim včasih pravijo tudi kraljevske poti, dovoljeni le koraki desno (1,0), gor (0,1) in desno diagonalno (1,1).

• 2 × 2, S₁ = 2

Kraljevski poti na mreži 2 × 2

• 3 × 3, S₂ = 6

Kraljevske poti na mreži 3 × 3

• 4 × 4, S₃ = 22

Kraljevske poti na mreži 4 × 4

Prva Schröderjeva števila za n ≥ 0 so (OEIS A006318):

1, 2, 6, 22, 90, 394, 1806, 8558, 41586, 206098, 1037718, ...

Po Richardu Stanleyju, profesorju uporabne matematike na Tehnološkem inštitutu Massachusettsa (MIT), naj bi Hiparh verjetno poznal enajsto Schröderjevo število S₁₀ = 1037718, ni pa popolnoma jasno kako je prišel do njega.

Števila se imenujejo po nemškem matematiku Ernestu Schröderju.

Glej tudi

• Catalanovo število
• Schröder-Hiparhovo število
• Delannoyjevo število
• Motzkinovo število
• Narajanovo število