のサブセットの数 $\{1,2,…,n\}$ 3つの連続した整数が含まれていませんか？
私の試み。仮定しましょう$n$ は大きな正の整数です。 ${n \choose 0},{n \choose 1},{n \choose 2}$ そのようなサブセットの数は $0,1,2$それぞれ要素、それは些細なことです。にとって$3$ 要素、そのようなサブセットの数は ${n \choose 3}-(n-2)$。から始まる$4$要素、私の脳は混乱し始めます。体系的にさらに進める方法がわかりません。ヒントやアイデアをいただければ幸いです。
リマーク。VIVIDとMasacrosoによる部分的な解決策のおかげで、私はこの問題を完全に解決しました。VIVIDの回答に続いて、主に将来の参照のためにソリューションを完成させる回答を投稿しました。
多くの編集から見たこの問題に非常に熱心に取り組んできたVIVIDに、受け入れられた答えを与えるつもりです。また、最も重要なことは、VIVIDがソリューションのコア部分を投稿した最初の人物でした。マサクロソ、気にしないでください。
最後に、この問題は完全に解決されましたが、新しいアプローチはいつでも歓迎します。
回答
部分的な解決策：で示しましょう$S \subseteq \{1,2,\dots,n\}$条件を満たすすべてのセット。そして、$a_n$ そのようなセットの数になります。
場合によっては次のようになります。
- $n \not \in S \implies$ がある $a_{n-1}$ の可能性 $S$ （晴れ）
- $n \in S$：
- a） $n-1 \not \in S \implies$ がある $a_{n-2}$ の可能性 $S$ （なぜ？）
- b） $n-1 \in S, \ \ n-2 \not \in S \implies$ がある $a_{n-3}$ の可能性 $S$。（なぜ？）
したがって、漸化式が得られます $$\boxed{a_n = a_{n-1} + a_{n-2} + a_{n-3}}$$
上記の2つの（なぜ？）部分に答えると、完全な解決策になります。
解決策のスケッチ：この数を見つけるために再帰を作成できます。しましょう$x_k$ のサブセットの数 $\{1,\ldots ,k\}$ 3つの連続した数字が含まれていない場合 $x_{k+1}=x_k+x_{k-1}+x_{k-2}$ なぜなら
- $x_k$ のサブセットの数です $\{1,\ldots ,k+1\}$ 含まれていません $k+1$ と3つの連続した番号を持っていない
- $x_{k-1}$ のサブセットの数です $\{1,\ldots ,k+1\}$ 含まれています $k+1$ 含まれていません $k$ 3つの連続した数字は含まれていません
- $x_{k-2}$ のサブセットのためにとどまる $\{1,\ldots ,k+1\}$ 含まれています $k+1$ そして $k$ ただし、3つの連続した番号は含まれていません。
これはおそらく別のアプローチです。（基本的にはすでに与えられた答えと同等ですが、バイナリ文字列表現によって問題が考えやすくなるかもしれません。少なくとも私にとってはそうですが、それは私がこれらの「ランレングスの問題」にすでに精通しているためかもしれません。 。）
あなたはサブセットを考えることができます $S$ の $\{1,\dots, n\}$ 長さのバイナリ文字列として $n$、 どこ $1$ 位置で $j$ 手段 $j\in S$ そして $0$ 手段 $j\notin S$。これで、カウントするサブセットは、$3$-の実行 $1$の。
この新しい問題を解決するために、
$$A_n = \{\text{length } n \text{ binary strings without a run of three 1's} \}$$
今考えてみてください $w\in A_n$ との数 $1$それは最初に持っています。それはどちらでもかまいません$0$、 $1$ または $2$。次に、ゼロがあり、残りは単語です$A_{n-1}$、 $A_{n-2}$ または $A_{n-3}$、それぞれ。私たちは仮定しています$n>3$; 最初のものはベースケースです。サイズのtribonacci-recursionを見ることができます$|A_n|$。
まず第一に、VIVIDとMasacrosoの再帰的アプローチによる部分的な解決策に感謝します。これは本当に素晴らしいことです。以下では、将来の参考のために、そして私自身の理解を強化するために、彼らが中断したことを終えたいと思います（これは私が考えることができるように良いです）。
VIVIDの表記法に従いましょう。
しましょう$s$ の一般的な要素を示します $S$。
- それらのための $s$ 含まれていない $n$、 がある $a_{n-1}$ そのような $s$、それは些細なことです。
- それらのための $s$ 含まれています $n$ しかし含まない $n-1$、 がある $a_{n-2}$ そのような $s$。なぜなら「隔離する」ことによって$n$ 残りの選択だけを考慮する必要があります $n-2$ 整数。
- それらのための $s$ 両方が含まれています $n$ そして $n-1$、含めてはいけません $n-2$ そのような中で $s$、そして「分離」することによって $n$ そして $n-1$ 残りの選択だけを考慮する必要があります $n-3$整数。したがって、$a_{n-3}$ そのような $s$。
次に、これらの3つの異なるセットを認識します $s$ 互いに素であり、実際に彼らの和集合は $S$。したがって、漸化式$a_n=a_{n-1}+a_{n-2}+a_{n-3}$。次に、フィボナッチ数に似たシーケンスを形成できますが、今回は前の3つの数を加算して、次の数を取得します。$1,2,4,7,13,24,44,81,...$、最初の数字は $a_0$ これは空のセットに対応します。
リマーク。この再帰的イデオロギーを使用して、次のシーケンスをさらに導出できることを理解しています。$a_n$ ないことによって条件が置き換えられた $r$ 連続する整数ここで $r$ 任意の正の整数にすることができます。