ForHosting KIT · 数学

a×bグリッド上の単調格子経路

Q: これはカタラン数と同じですか?

いいえ。 カタラン数は対角線以下にとどまるDyck経路を数えます。このツールは制約のないすべての単調格子経路を数えます。

右か上にしか進まない格子上の道順を数えます。右に2、上に3進んだ点までは10通りでC(5, 2)に当たり、2×2の正方形なら6通りです。ブラウザで無料で使えます。

無料
ブラウザで動作
登録不要
データは端末の外に出ません

無料で実行 API仕様を見る

ご利用方法ウェブAPIメールTelegramアプリ近日

計算例

入力した場合

水平方向の移動: 2
垂直方向の移動: 3

結果

経路数: 10
A + B: 5
最大A: 500
最大B: 500

この格子経路計算は、右移動と上移動だけを使って原点(0, 0)からグリッド上の点(a, b)まで移動する単調な経路が何通りあるかを返します。この古典的な組み合わせ論の値は二項係数C(a + b, a)に等しく、これはC(a + b, b)とも同じです。なぜなら、どの経路もちょうどa回の東への移動とb回の北への移動の並びだからです。よく知られた例としては、2行2列の正方形で6通り、2行3列の長方形で10通り、幅がゼロの退化した通路では唯一の経路が1本の垂直な上りとなる場合が挙げられます。エンジンは決定的なBigIntの積で二項係数を評価するため、大きなグリッドでも浮動小数点の誤差に埋もれることなく全桁を保持します。ネットワーク呼び出しもモンテカルロ法によるサンプリングも日付依存のショートカットもありません。宿題やコンテスト対策、コーディング演習にはブラウザで無料でお試しください。

単調な格子経路の意味と結果の見方

平面の整数グリッド上の単調格子経路とは、(0, 0)から出発し、単位右移動(1, 0)と単位上移動(0, 1)のみを使って(a, b)に到達する経路のことです。左や下に動くことはないため、有効な経路はすべてa回の右移動とb回の上移動の並べ方に過ぎず、その異なる並べ方の数が二項係数C(a + b, a)です。

この恒等式は数え切れないほどの離散数学の演習の土台であり、学生は都市の街区グリッドを通る経路を数えるときに初めてこれに出会い、その後、東と北にしか進まないランダムウォークと二項係数を結びつけるとき、さらに対角線より下にとどまるという制約を持つカタラン数の経路と、制約のない単調経路を比較するときにも再び登場します。

この計算は、要求されたaとb、10進数の文字列としての正確な経路数、和a + b、C(5, 2)のような短い式のタグ、そしてクライアントが送信前に検証できるよう公開された最大値を返します。真実として提示される近似的な浮動小数点の経路や、経路のランダムなサンプリングは一切ありません。

拒否される場合には、aまたはbの欠落、整数でない値、分数、指数表記、公開された上限を超える値、負のaまたはbが含まれます。Dyck語、カタラン数、障害物のある最短経路、あるいは左や下への移動も許す制約なしのランダムウォークが必要な場合は、それぞれ専用のツールをお使いください。

aとbの読み取り方とBigIntが全桁を正確に保つ仕組み

任意で先頭に正符号を付けられます。埋め込まれた空白、16進数の接頭辞、負の符号、指数表記は明確なメッセージとともに拒否されるため、不正なセルが誤った経路数になることはありません。どちらの寸法もゼロは有効な値です。

aがゼロのとき、経路はb回の移動からなる純粋な垂直の上りとなり経路数は1です。両方がゼロのとき、空の経路がC(0, 0)の空積の慣例に従って1として数えられます。

エンジンはaとbの両方に500という厳格な上限を課しており、二項係数が超指数関数的に増加するにもかかわらず、無料のブラウザ経路とエッジのWorkerの両方で中間の積の長さと遅延を予測可能な範囲に収めています。計算にはC(a + b, a)の乗法的な公式を使います。

iを0からa−1まで(あるいは対称性によりより小さい方の添字まで)動かしながら(a + b − i) / (i + 1)を掛け合わせ、各段階で正確に割り切ることで素因数が失われないようにします。

格子経路数が活きる学習・コード・モデリングの場面

学生は、教科書がa行b列の都市グリッドを横切る最短経路の数を尋ねるとき、二項係数の演習に幾何学的な物語が必要になるとき、あるいは主対角線より上の経路を禁じるカタラン数と制約のない経路数を比較しなければならないときに単調格子経路に出会います。

教師は、大きな整数を丸めたり黙って指数表記に切り替えたりする不透明な電卓アプリを信用せずに、手頃なaとbに対する解答例を事前に生成できます。

開発者は、決定的なテストベクトルの種を作るため、グリッドナビゲーションのモデルの規模を決めるため、あるいは対数空間での近似値ではなく正確なC(a + b, a)を要求するプログラミング課題の条件を満たすために、スクリプトから同じ契約を呼び出します。

競技プログラミングの練習では、時間制限の中でOEISの表をダウンロードせずに解答を検証できる、高速でオフラインの格子経路ランクの情報源がしばしば必要になります。

プロダクトや研究の分析者は、a回の東への決定とb回の北への決定からなる単調な並びがいくつ存在するかを見積もる際にこの数値を使い、これはシーケンシング関連の実験、初等確率のデモ、列挙的組み合わせ論のワークシートに登場します。このページ上ではすべての処理がブラウザ内で完結します。

活用例

宿題とグリッド経路の確認

単調な街区経路と二項係数の幾何に関する教科書の演習のために、正確なC(a + b, a)の値を調べます。

決定的なテストフィクスチャ

表を手作業で維持することなく、単体テストやプロパティテスト、CIのアサーションのために再現可能な格子経路の10進数の文字列を生成します。

コンテストとモデルの準備

近似値ではなく正確なBigIntの係数を使って、プログラミング課題の答えを検証し、東北方向の経路モデルの規模を決めます。

よくある質問

単調格子経路はどのように定義されますか?

単位右移動と単位上移動のみを使って(0, 0)から(a, b)まで進む経路です。その数は二項係数C(a + b, a)に等しくなります。

これはカタラン数と同じですか?

いいえ。カタラン数は対角線以下にとどまるDyck経路を数えます。このツールは制約のないすべての単調格子経路を数えます。

結果が数値ではなく文字列なのはなぜですか?

二項係数による格子経路数は急速に増加し、JavaScriptの安全な整数を超えることがあります。

格子の大きさの上限はいくつですか？

横と縦のそれぞれについて、0から500歩まで入力できます。この上限により、大きな格子で経路の数が膨大になっても、結果は正確なまますぐに求められます。

横か縦のどちらかが0のときはどうなりますか？

経路は1通りになります。たとえば横が0なら、上にまっすぐ進む道しかありません。両方が0のときも、動かないという空の経路を1通りと数えます。

開発者向け — APIアクセス

このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。

エンドポイント

POSThttps://api.kit.forhosting.com/combo/lattice-paths

Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。

お使いのスタックから呼び出す

curl -X POST https://api.kit.forhosting.com/combo/lattice-paths \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"a":2,"b":3}'

const res = await fetch("https://api.kit.forhosting.com/combo/lattice-paths", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "a": 2,
    "b": 3
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/combo/lattice-paths",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "a": 2,
    "b": 3
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/combo/lattice-paths", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"a":2,"b":3}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"a":2,"b":3}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/combo/lattice-paths", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

リクエスト例

{
  "a": 2,
  "b": 3
}

レスポンス例

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "combo.lattice_paths",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。

料金

1リクエストあたり$0.002

単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。

制限

`max_a`	500
`max_b`	500

エラー

HTTP	コード	意味
`401`	`unauthorized`	APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。
`402`	`insufficient_balance`	残高が不足しています。チャージ後に再度お試しください。
`404`	`unknown_type`	指定されたタスクタイプは存在しません。タイプ名を確認してください。
`429`	`rate_limited`	リクエストが多すぎます。しばらく待ってから再度お試しください。

技術的な注記

CI、授業用のワークシート、二項係数のグリッド幾何のデモで再現可能な格子経路のフィクスチャが必要な場合は、リクエストが成功するごとに$0.002でAPIをお使いください。

単調格子経路が意味するものとレスポンスの内容

エンジンは対応範囲内で正確な二項係数を構築するか、invalid_inputで入力を拒否します。負の寸法は単調格子経路数にとって意味を持たないため、黙ってゼロを返すのではなく、該当フィールドを明示したメッセージで即座に失敗します。このページは、ワークシートや単体テスト、JavaScriptの安全な整数を超えて桁を失ってはならないAPI利用者に適した、正確なBigInt出力による制約なしの古典的な単調経路数のみに答えます。

aとbの読み取り方とBigIntが全桁を正確に保つ仕組み

優先されるフィールドは水平方向の移動(グリッドの幅)を表すaと垂直方向の移動(グリッドの高さ)を表すbですが、aにはwidth、m、x、bにはheight、n、yという別名も受け付けるため、スプレッドシートやクエリ文字列、型付きフォームで同じ契約を再利用できます。すべての中間値はBigIntであり、最終的な値はtoStringでシリアライズされるため、JSONでIEEEの倍精度浮動小数点数が53ビットを超えたところで桁を失うようなことは起こりません。二項演算を自分で再実装せずに自動パイプライン内で同一の数学的結果が必要な場合は、このページの無料ブラウザ実行と有料APIを組み合わせてください。

格子経路数が活きる学習・コード・モデリングの場面

APIでは成功した照会1件ごとに$0.002が課金され、検証に失敗した場合は課金されず、レスポンスを返した後は何も保存されません。この無料の対話的な検証と同一結果を返す有料APIという組み合わせは、KITのtier-Aカタログ全体の方針と一致しており、教室でのデモから自動パイプラインへ、数学的な結果を変えることなく移行できます。移動の種類が2つより多い経路には多項係数のツールと、交差しない特殊なケースが必要な場合はカタラン数のツールと、そして無料で決定的な組み合わせ論のツール群を構築する際には他の数学系エンドポイントと組み合わせてください。

技術的な質問

格子経路計算の料金は?

このページではブラウザ上で無料です。APIでは成功したリクエストごとに$0.002が課金され、無効な入力には課金されません。

aまたはbが負の場合はどうなりますか?

負のaまたはbはinvalid_inputとして拒否されます。両方の寸法は公開された上限内の非負整数である必要があります。

KITの完全なドキュメントを見る →

a×bグリッド上の単調格子経路

無料で実行

計算例

単調な格子経路の意味と結果の見方

aとbの読み取り方とBigIntが全桁を正確に保つ仕組み

格子経路数が活きる学習・コード・モデリングの場面

活用例

宿題とグリッド経路の確認

決定的なテストフィクスチャ

コンテストとモデルの準備

よくある質問

関連ツール

開発者向け — APIアクセス

エンドポイント

お使いのスタックから呼び出す

リクエスト例

レスポンス例

料金

制限

エラー

技術的な注記

単調格子経路が意味するものとレスポンスの内容

aとbの読み取り方とBigIntが全桁を正確に保つ仕組み

格子経路数が活きる学習・コード・モデリングの場面

技術的な質問

ありがとう