カタラン数

座標平面上で、原点 $(0,0)$ から点 $(6,6)$ まで、1 歩ごとに $x$ 軸の正の向きに $1$ 進む（右へ $1$）か、$y$ 軸の正の向きに $1$ 進む（上へ $1$）かのどちらかで進む最短経路を考える。このうち、経路上のすべての格子点 $(x,y)$ が $y\le x$ を満たすもの（直線 $y=x$ より上側に一度も出ないもの）の個数を求めよ。

座標平面上で、原点 $(0,0)$ から点 $(5,5)$ まで、1 歩ごとに $x$ 軸の正の向きに $1$ 進むか、$y$ 軸の正の向きに $1$ 進むかのどちらかで移動する経路（最短経路）を考える。このうち、途中で通る格子点 $(x,y)$ がすべて $y\le x$ を満たす経路は何通りあるか求めよ。

ある窓口で 1 枚 500 円の券を売っている。窓口に並んだ 10 人の客のうち、5 人は 500 円硬貨 1 枚で支払い、残りの 5 人は 1000 円札 1 枚で支払う。1000 円札で支払う客には、その場で 500 円硬貨 1 枚のおつりを渡す。窓口のレジには、はじめ硬貨が 1 枚も入っていない。客を区別せず、10 人の支払い方の並び（500 円硬貨を A、1000 円札を B として、A を 5 個、B を 5 個並べた長さ 10 の列）だけを考えるとき、どの客にも必ずおつりを渡せるような並びは何通りあるか求めよ。

原子型として $o$ ただ 1 つをもち、定数をもたない単純型付きラムダ計算（チャーチ流）を考える。型は $$\tau ::=o\mid (\tau \to \tau )$$ で生成される式とし、括弧の付け方（木としての形）が異なる型は異なる型とみなす。型 $\tau$ が住人をもつとは、型 $\tau$ の閉じた項（自由変数をもたない項）が存在することをいう。

矢印 $\to$ をちょうど $5$ 個含む型（したがって $o$ をちょうど $6$ 個含む型）のうち、住人をもつものの個数を求めよ。

互いに異なる $2$ つの原子型 $a,b$ をもち、定数をもたない単純型付きラムダ計算（チャーチ流）を考える。型は
$$\tau ::=a\mid b\mid (\tau \to \tau )$$
で生成される式とする。括弧の付け方（木としての形）または原子型の配置が異なる型は、異なる型とみなす。$\to$ は右結合とし、型に現れる $\to$ の個数をその型の矢印数とよぶ。

型 $\tau$ の住人とは、型 $\tau$ をもつ閉項であって、$\beta$ 正規形かつ $\eta$ 長形（long normal form）であるもののこととする。住人は $\alpha$ 同値なものを同一視して数える。

矢印数がちょうど $3$ である型のうち、住人をちょうど $1$ つだけもつ型の個数を求めよ。

カタラン数 $C_0,C_1,C_2,\dots$ を
$$C_0=1,C_{n+1}=\sum _{i=0}^n{C}_i{C}_{n-i}(n\text{は 0 以上の整数})$$
で定める。0 以上の整数 $n$ について、$C_n$ が奇数であるための必要十分条件は、ある 0 以上の整数 $j$ を用いて $n=2^j-1$ と表されることであることを証明せよ（$2^0=1$ とし、$n=0$ は $j=0$ の場合にあたる）。

集合 $\{1,2,\dots ,10\}$ の分割（空でない互いに素なブロックへの分け方。ブロックの順序は区別しない）を考える。分割が非交差であるとは、$a<b<c<d$ を満たす $a,b,c,d\in \{1,\dots ,10\}$ で、$a,c$ が同じブロックに属し、$b,d$ がそれとは異なる同じブロックに属するようなものが存在しないことをいう。

$\{1,2,\dots ,10\}$ の非交差分割のうち、どのブロックも 2 個以上の要素を含む（要素 1 個だけのブロックを持たない）ものの個数を求めよ。

左括弧「(」7 個と右括弧「)」7 個を 1 列に並べた長さ 14 の文字列で、正しく対応のとれた括弧列（どの位置までを見ても「(」の個数が「)」の個数以上であり、全体では両者が等しいもの）を考える。括弧列の左から $j$ 文字目までに含まれる「(」の個数から「)」の個数を引いた値を $j$ 文字目での深さとし、$j=1,2,\dots ,14$ にわたる深さの最大値を、その括弧列の入れ子の深さという。入れ子の深さが 3 以下である正しい括弧列の個数を求めよ。

原子型を $o$ ただ 1 つだけもつ単純型付きラムダ計算（チャーチ流、定数なし）を考える。型は
$$\tau ::=o\mid (\tau \to \tau )$$
で生成されるものとし、括弧の付け方が異なる型は異なる型とみなす（たとえば $(o\to o)\to o$ と $o\to (o\to o)$ は異なる型である）。型 $\tau$ に含まれる記号 $\to$ の個数を $\tau$ の矢印の個数という。

型 $\tau$ をもつ閉じた項（自由変数をもたない項）が少なくとも 1 つ存在するとき、$\tau$ は住人をもつという。矢印の個数がちょうど $6$ である型のうち、住人をもつものの個数を求めよ。

$n$ を正の整数とする。座標平面上で、原点 $(0,0)$ から点 $(2n,0)$ まで、1 歩ごとに $(1,1)$ または $(1,-1)$ だけ進む経路のうち、途中で $y$ 座標が一度も負にならないものを考える（このような経路をディック経路という）。ディック経路 $P$ に対し、$P$ が通る点 $(i,0)$ で $1\le i\le 2n$ を満たすものの個数を $r(P)$ とする（$x$ 軸に戻る回数。終点 $(2n,0)$ も数える）。

$$S_n=\sum _{P}r(P{)}^2$$

とおく。ただし、和は長さ $2n$ のディック経路 $P$ すべてにわたってとる。$S_n$ を $n$ の式で表せ。