組み合わせ

ホモ接合体とヘテロ接合体、順序を気にする気にしない

ここで同胞のIBDを計算している ヒトは2倍体なので、ペアを作る作業が多発する。 ペアを作るときにペアの構成要素が同じか違うかは、組み合わせを作るときに問題になる また、ペアを作ったときに、ペアの構成要素の順序を気にするかしないか、も問題になりう…

ラベルの貼り方と場合の数

こちらから。 N個の箱が一列に並んでいるとします。 N枚のラベルがあるとします。 ラベルには1からNまでの数字が書いてあります。 そのラベルは2色に分けられています。 1からn1までのn1枚は赤色で、n1+1からNまでのN-n1枚は青色です。 今、N個の箱にN枚…

いろいろ数え上げる

数え上げ # 順列 permN<-function(N=10,k=3){ return(exp(lgamma(N+1)-lgamma((N-k)+1))) } 組み合わせ combN<-function(N=10,k=3){ return( exp(lgamma(N+1)-lgamma((N-k)+1)-lgamma(k+1)) ) } 重複順列 repPermN<-function(N=10,k=3){ return(N^k) } 重複…

選ぶ

aからbを選ぶ場合の数は、です。 これに対応するRの関数はchoose()で > choose(10,3) [1] 120 aからbを選ぶのは、aをb+c,ただしb+c=aに分けること。 Nをn1,n2,...,nk, na+n2+...+nk=Nに分けるのは そんな関数は。ただし、n1,...,nkは、全部与えても、nkを省…

多人数をグループ分けする

今、人をグループに分けることを考える。グループの所属メンバーの数は0人でもよいものとする。その人数配分のとり方は 通り 考え方1 ******|*********|***|*****|************* 人をグループに分けるとき、その人数配分は、本の区切り線を個の印の列に入れ…

兄弟(同胞)の遺伝子はどれくらい似ているか(3)

これの続き 前回までに、染色体が同長で組み換えがない場合、染色体の長さが不均等で組み換えがない場合について考えた。 組み換えを考慮しよう。 はじめに、染色体数が1で、組み換えがある場合を考える 同胞が共有する割合の期待値は これは、同胞のそれぞ…

兄弟(同胞)の遺伝子はどれくらい似ているか(2)

これの続き 組み換えを考慮する前に、染色体の長さが均等でない場合を考えよう 前回は、すべての染色体の長さが同じものと仮定した。 全部でk種類の染色体があり、なる長さの染色体とする 同胞がシェアする期待値は ただしはk種類の染色体の父母由来を0,1で…

兄弟(同胞)の遺伝子はどれくらい似ているか

一卵性双生児は遺伝的に同一だから、一致率が1 親子の関係の場合、子はその遺伝子の半分を片親から引き継いでいるので、 兄弟姉妹(同胞)の場合は、親子の半分で したがって、同胞はだけ似通っている… 平均的には。 本当のところはどれくらいだろうか? 今、…

ウェットのスタディのドライ的評価

たとえば、こんな論文がある。リンパ球を表面に発現している膜分子の発現パターンや、機能性小分子の分泌パターンなどで、亜分類し、それらの、発現パターンによる役割づけをし、また、それを分化と結びつけて考える論文であり、よくあるタイプである。 この…

攪乱順列

N個のものが並んでいる。それを取り出して、並べ替えて、戻したときに、N個のいずれも元の位置に戻らないような順列が攪乱順列であり、そのような順列が、全順列に占める割合はに極めて早く収束する。 エクセルはこちら

第5講 シュレーゲル図式と4-多面体

多面集合的複体(polyhedral complex)と多面体的複体(polytopal complex)。多面集合的複体は有限個の多面集合の集まりであるが、そのすべての要素が有界である(多面体である)ときに、多面体的複体という。 多面体や多面体的複体はその分割(subdivision)に興味…

第6講 双対性、ゲール図式とその応用

ゲール図式 有向マトロイド 有向マトロイドの双対性 点配置のアフィン従属性ベクトル

第4講 3-多面体のシュタイニッツの定理

グラフGが3次元多面体のグラフであるのは、単純で、平面的で、さらに3-連結であるときであり、かつそのときに限る。 2-connected(2-連結、1個の頂点とそれに接続するすべての辺を取り除いても、非連結にならないグラフ)、3-connected(3-連結、1個または2…

第3講 多面体のグラフ

多面体Pに関して一般の位置 面の向こう側 辺の向きづけ(Orientation of G(P) induced by ) 幾何学者のための線形計画法 頂点と辺とで構成されたものをグラフとするなら、多面体はn次元空間に表示されたグラフである。 凸多面体は、一般の位置にある任意のベ…

第2講 多面体の面

頂点、面、ファセット 面束、半順序、束(こちらも) 半順序集合、ポセット、鎖、区間、ブール的、階層的、有界、原子的、余原子的、逆ポセット、順序双対 ハッセ図 極性 多面体を線形化して「錐の極性」へ話しを移すことができること 内点、相対的内点 極集合…

第1講 多面体、多面集合、錐

Fourier–Motzkin elimination 錐と凸多面体との和で表された多面体を、上位次元の錐として捉えて扱いを容易にすること ファルカスの補題 後退錐、斉次化 カラテオドリの定理

第0講 イントロダクションといくつかの例(駆け足で読む凸多面体の数学)

ベクトル空間 双対ベクトル空間 アフィン(アフィン部分空間、アフィン包、アフィン独立、アフィン同型、アフィン像、射影) 点、直線、平面、超平面、ファセット 凸包 多面体、polytope、polyhedron 組み合わせ同値 d-単体、標準d-単体 d次元超立方体(単純、…

凸多面体覚書

ひとまず、きれいなウェブサイトはこちら こちらもよいサイト モーメント曲線、巡回多面体、近傍的多面体、上限定理に関して記載された日本語PDFはこちら

駆け足で読む凸多面体の数学

教科書 凸多面体の数学 作者: G.M.ツィーグラー, G¨unter M. Ziegler, 八森正泰, 岡本吉央 出版社/メーカー: シュプリンガーフェアラーク東京 発売日: 2003/04 メディア: 単行本 この本についてコメントしてあるブログはこちら 東大今井研輪講資料(第3講『…

サブグループ内の順位、試験の季節に思うこと

今、N個の値の集合があるとする。それらをn個ずつk個の部分集合に分ける。 今、全体N個の中での、順番がi番目の値が、n個の部分集合内で、1番になる確率は、どうなるだろうか。 また、このようにして選ばれる、k個の部分集合内の1番の値の期待値はいくつに…

単体 Simplex

単体は、パスカルの3角形の先にあるような存在で、組み合わせについて考えるときの道具として有用。 Wikiのこちらのページや、こちらのページなど。

集合・べき集合・べき集合から作る組み合わせ

要素数k個の集合がある そのべき集合はの要素を持つ。 べき集合の要素であるサブセットは、i=0,...,k個の要素を持つ。i=pなるサブセットの数は通りある 一方、要素数iの集合(サブセット)を、q=2,3,...,i個の更なるサブセットの組に分けるわけ方は、http://d.…

2.3 連結性 (グラフ) 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム

グラフの実装表現 接続行列表現 行に点、列に辺をとり、点が辺の端点なら1(始点なら1、終点なら−1)、そうでなければ、0 必要領域:O(点の数x辺の数) 隣接行列表現 行と列に点をとり、点のペア間に辺があれば1、なければ0。向きを考慮するときは辺があ…

2.2 木、閉路、カット (グラフ) 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム

グラフにおける閉路とカット 閉路はぐるっと一巡するタイプのグラフ 定義としては、点と辺を交互にたどってもとの点に戻ってくるような点と辺の集合である。ただし、このとき点と辺はそれぞれ1度ずつしか使用しないし、1度は使用するものとする。 カットは…

解析変数次元とepistasis解析

書き終わるかどうか、不明な書きかけ(今月の宿題) 予備項目 カテゴリカル変数の次元についてのメモ(こちら) 変数の数 関連解析を想定する 量的変数は次元1の変数とする(量的変数には、順序のあるカテゴリ変数を含める) カテゴリカル変数は、複数のカテゴリ…

とりあえず解きたい(続)

6月22日の記事の問題の変形 今、N個の要素からなる要素集合がある これの部分集合がk個与えられている k個の部分集合のうち、s個の部分集合がロシアのマトリョーシカ人形のような包含関係にあるときs個の部分集合に対する処理はその一番要素数の多い部分…

関連組み合わせ

多変量解析をするとき、従属変数群と説明変数群とに2分できるならば、それらの間の関連解析組み合わせのグラフ表現は2部グラフとなる 逆に、従属変数群内の変数間の関連、説明変数群内の変数間の関連も検定するときには、2部グラフにならない(こともある)…

16.4 グリーディ彩色アルゴリズム 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム

点彩色問題の位置 集合があり、その部分集合の作る集合の集合(べき集合)があるときに、与えられた条件のもとでの最適な(ある指標を最小化する)べき集合の組み合わせを求める問題の1つ 最小集合カバー問題と呼ばれる べき集合数は、元の集合の要素数に対して…

とりあえず解きたい

今、N個の要素からなる要素集合がある それぞれの要素はX個の要素からなっている。これを 、と表す 今、このN種類の要素のX個の要素をシャッフルしたい。完全にシャッフルするのでなく、一定の制約を入れてシャッフルすることを考える シャッフルに与える制…

1.2 マージソート 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム

O(n log n)時間でのソート。この時間は、ソート対象列のデータ型・データ構造の条件を用いない場合には、最短なものの1つ。 本項中のその他の記述。「任意の再帰アルゴリズムを計算時間を増加させることなく、再帰呼び出しなしのアルゴリズムで書ける」 リ…