Schröderjevo število

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

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\ge 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, S1 = 2
Kraljevski poti na mreži 2 × 2
  • 3 × 3, S2 = 6
Kraljevske poti na mreži 3 × 3
  • 4 × 4, S3 = 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 S10 = 1037718, ni pa popolnoma jasno kako je prišel do njega.

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

Glej tudi[uredi | uredi kodo]