パーティションのカバー関係の数

2
Phil 2019-12-02 06:37.

$L(m,n)$ は長さmのパーティションのセットであり、各パーツはセット内にあります ${0,...n}$。2つのパーティション$a$ そして $b$$L(m,n)$$a=(a_1,...,a_m)$ そして $b=(b_1,...,b_m)$ 関係している: $a\leq b$ もし $a_i\leq b_i$ すべてのために $i$ そして $a_i<b_i$ 少なくとも1つ $i$

$c(n,m)$ ペアの数です $(a,b), \; a,b \in L(m,n)$$a\leq b$ パーティションなし $c$$a\leq c \leq b$

私はそれを示す必要があります: $$c(m,n)=\frac {(m+n-1)!}{(n-1)!(m-1)!}$$

私はすでに見るためのヒントを持っています $a_1$しかし、解決策に進まないでください。どんな助けも感謝します!ありがとう。

3 answers

1
Mike Earnest 2019-12-02 12:05.

私はあなたがそれを知っていると確信しています $L(m,n)$ からの格子パスのセットで識別できます $(0,0)$$(m,n)$、そのようなパスの下にある単位正方形のセットは、まさに $m$ サイズがせいぜいすべての部品 $m$。これの意味は$|L(m,n)|=\binom{n+m}{m}$、そのようなパスが持っているように $n+m$ ステップ、そしてあなたは選択する必要があります $m$ 水平になるステップの。

同様に、ペア $(a,b)$ によって数えられる $c(m,n)$ からのパスのペアとして表示できます $(0,0)$$(m,n)$ これはほとんど重なりますが、その間の領域を囲み、1つの単位正方形で構成されます。

私はそれを証明します $$ c(m,n)=(m+n-1)\cdot \binom{m+n-2}{m-1} $$組み合わせて。要因$\binom{m+n-2}{m-1}$ からの格子パスの数をカウントします $(0,0)$$(m-1,n-1)$、下の最初の画像のように。そのような道は訪れるでしょう$m+n-1$整数格子の頂点。これらの頂点の1つ(*画像内)を選択します。$m+n-1$以下に示すように、それをボックスに「拡張」して、グリッドの幅と高さを1つ増やします。結果はからのパスのペアです$(0,0)$$(m,n)$ 必要に応じて、それらの間に1つのボックスを配置します。

前:

.   .   .   . _ . _ .   
            |
.   .   .   *   .   .   
            |
.   .   . _ .   .   .   
        |
. _ . _ .   .   .   .   

後:

.   .   .   .   . _ . _ .   
                |
.   .   .   . _ .   .   .
            |   |
.   .   .   . _ .   .   .
            |
.   .   . _ .   .   .   .
        |
. _ . _ .   .   .   .   .
1
Peter Taylor 2019-12-02 08:02.

これは非反射関係の非常に奇妙な表記ですが、気にしないでください。

あなたが数えようとしているのはペアです $(a, b)$ 1つを除くすべての部分に同意し、その1つの部分の違いは $1$。だからどちらか$a_1=b_1=k \le n$、この場合、残りの行には $c(m-1,k)$可能性; または$a_1= b_1-1 = k<n$、この場合、残りの行は互いに等しく、 $|L(m-1,k)|$ 可能性。

1
Phicar 2019-12-02 08:03.

そう $$c(m,n)=\frac{(n+m-1)!}{(n-1)!(m-1)!}$$ 次のように書くことができます $$c(m,n)=n\binom{m+n-1}{m-1}.$$あなたは次のように考えることができます。まず、パーティションを次のように分割できます$$L(m,n)=\bigcup _{k=0}^m\bigcup _{\ell =1}^n L_{k,\ell}(m,n)$$ どこ $L_{k,\ell}(m,n)$ 正確に使用するパーティションです $m-k$ ブロックの倍 $n.$ そしてあります $\ell$ ブロックの種類は言う $\{a_1,\cdots ,a_{\ell}\}\subseteq [n-1]\cup \{0\}$ など $$c(m,n)=\sum _{k=0}^m\sum _{\ell =1}^n\ell |L_{k,\ell}(m,n)|,$$このタイプのブロックの1つを選択して、1つ追加できるからです。今$$|L_{k,\ell}(m,n)|=\binom{n}{\ell}\binom{k-1}{\ell -1}$$ 私たちが選ぶので $\ell$ からのブロックの種類 $0,\cdots ,n-1$ そして私達は $k$ これらから残っているブロック $\ell$タイプ。そう$$c(m,n)=\sum _{k=0}^m\sum _{\ell =1}^n\ell \binom{n}{\ell}\binom{k-1}{\ell -1}=\sum _{\ell =1}^n\ell \binom{n}{\ell}\sum _{k=0}^m\binom{k-1}{\ell -1}=\sum _{\ell =1}^n\ell \binom{n}{\ell}\binom{m}{\ell }=n\sum _{\ell =1}^n\binom{n-1}{\ell -1}\binom{m}{m-\ell}=n\binom{m+n-1}{m-1}.$$

Related questions

MORE COOL STUFF

ダイアナ妃は、8歳でウィリアム王子を寄宿学校に送るという決定に「涙を流した」

ダイアナ妃は、8歳でウィリアム王子を寄宿学校に送るという決定に「涙を流した」

ウィリアム王子が 8 歳のときに寄宿学校に通わせたことについて、ダイアナ妃がどのように感じたかを学びましょう。

シャキール・オニールは、レイカーズのスターが彼のチキン帝国を北テキサスに拡大するにつれて、ダラスの外に永住権を購入しました

シャキール・オニールは、レイカーズのスターが彼のチキン帝国を北テキサスに拡大するにつれて、ダラスの外に永住権を購入しました

Shaquille O'Neal は最近、Big Chicken レストラン帝国を拡大するため、ダラス郊外に住居を購入しました。

「90 日間の婚約者」: イヴが逮捕され、浮気スキャンダルの後、モハメドに対する家庭内暴力の容疑に直面している — 何が起こったのか?

「90 日間の婚約者」: イヴが逮捕され、浮気スキャンダルの後、モハメドに対する家庭内暴力の容疑に直面している — 何が起こったのか?

「90日の婚約者」シーズン9のスター、イヴ・アレラーノが逮捕され、モハメド・アブデルハメドへの暴行容疑で家庭内暴力の罪に問われている.

ナターシャ・リオンは、ピーウィー・ハーマンは「ビジネスで最高のGIFを送る」と言います

ナターシャ・リオンは、ピーウィー・ハーマンは「ビジネスで最高のGIFを送る」と言います

ナターシャ・リオンは、ピーウィー・ハーマン自身、ポール・ルーベンスと親密です。彼らの友情について彼女が言ったことを発見してください。

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

ハードコアシェフのゴードンラムゼイが最もハードコアなフェラーリをドライブ

ハードコアシェフのゴードンラムゼイが最もハードコアなフェラーリをドライブ

有名シェフのゴードン・ラムゼイの味わいと爆発的なとんでもない悪意に相当する車を考えざるを得なかったとしたら、ラムゼイ自身が所有している新しいフェラーリF12tdfを思い浮かべるでしょう。ちょっとそれを見てください、彼は実際にこのビデオでちょっといいです!彼は通りの農民と一緒に写真を撮るのをやめ、写真を撮るために若者を車の中に座らせさえしているようです。

私たちの最初の宇宙農場にはジャガイモよりもはるかに良い選択肢があります

私たちの最初の宇宙農場にはジャガイモよりもはるかに良い選択肢があります

火星人は、宇宙のジャガイモ栽培を、かなり美味しくも簡単でもないにしても、確かにもっともらしいものにしました。しかし、私たちが本当に宇宙に住むつもりなら、ジャガイモは絶対に私たちの最初の農業の選択であるべきではありません。

ランドローバーは新しいボディスタイルで10倍以上のディフェンダーを売りたい

ランドローバーは新しいボディスタイルで10倍以上のディフェンダーを売りたい

ランドローバーのデザインチーフであるジェリーマガバーンは、次のランドローバーディフェンダーが私たちが見たレゴのようなコンセプトに「似ていない」ことを確認しましたが、彼は次回はもっと売りたいと言っています。はるかに。

アダムサンドラーは、Netflixが彼の人種差別的な映画について非常に冷静だったと言います

アダムサンドラーは、Netflixが彼の人種差別的な映画について非常に冷静だったと言います

アダムサンドラーのNetflix限定映画、リディキュラスシックスは、平均的なアダムサンドラー映画よりも見栄えが悪いです。マグニフィセントセブンのパロディーであるこの映画は、ネイティブアメリカンと彼の5人の異母兄弟が、誘拐された父親を救おうとしているところを追っています。

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、子供向けのパズルの本の序文を書き、ジョージ王子、シャーロット王女、ルイ王子と一緒にテキストを読むと述べた.

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

Yak's Produce は、数十個のつぶれたメロンを野生動物のリハビリ専門家であるレスリー グリーンと彼女のルイジアナ州の救助施設で暮らす 42 匹の動物に寄付しました。

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

8 枚目のスタジオ アルバムのリリースに向けて準備を進めているデミ ロヴァートは、「スーパー グレート ガイ」と付き合っている、と情報筋は PEOPLE に確認しています。

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

イーサン プラスの誕生日のお祝いは、TLC のウェルカム トゥ プラスビルのシーズン 4 のフィナーレで、戦争中の母親のキム プラスと妻のオリビア プラスを結びつけました。

水門の修理

水門の修理

天王星と海王星の間の領域に向かって宇宙を 3/4 g の低温で航行しながら、私たちは数週間燃え続けていました。Dawson Trawler の科学者が Yggdrasil ポータルと呼んだもの。

美しいもの

美しいもの

女性として、私は通常、関係を築くことをためらっています。私はいつも彼らに負けないように苦労しました。私は誰かと共有したいという衝動と戦わなければなりません。

逃走中の女性からの発信

最も家が必要なときに家のように感じる場所はありません。

逃走中の女性からの発信

私は誰よりも移動しました。父が住んでいた土地には、父が 1 歳馬を折るミニチュアの競馬場がありました。

死にゆく男から学んだ最大の人生の教訓

彼は、私たちが持っているのはこの現在の瞬間だけであることを知るのが遅すぎました。

死にゆく男から学んだ最大の人生の教訓

ブラッドは、カーキ色のショート パンツとポロ シャツを着たまま、白いゴルフ グローブを両手で高く引っ張ったまま、ベッドルームに入ってきました。彼は満面の笑みを浮かべながら、「今年は私の人生で最高の年だったと思います!」と言いました。通常は保守的な消費者である私たちは、通常とは異なることをしました。

Language