線形の問題です
すべての置換があみだくじで表せることを示せ
なんとなくはわかるのですが、うまく言葉にできません

このQ&Aに関連する最新のQ&A

php 置換」に関するQ&A: PHPの置換方法

A 回答 (3件)

 過去にも同じような質問があるようです。

過去の質問では
・当りが必ずあること、ダブらないこと
を証明するものでしたが、今回は加えて
・あみだくじの横線を追加すればどんな置換でも必ず表せる
の証明なので、余分な手間がかかって少し難しくなってい
るかも知れません。しかし、同じようなレベルの問題が2つになった
のと同じようなものかも知れません。一応残り(2つのうちの後半)
部分も含めて書きますが、詳しい証明は省略します。

 先ず、あみだくじを厳密に定義する必要があります。
あみだくじには道筋(行き先を決定する過程)を複雑にするために
a.隣り合う横の線をある位置で水平に結ぶ
b.バイパスさせて隣り合わない任意の2つの線をある位置で水平に
  結ぶ
c.上の2つの操作を水平でない線によって行う
 またはこれと同等な操作ですが、2つの線を選んでその各々のある
 位置で小さい分岐路を作りその先にまるばつさんかくなどの共通の
 記号をふっておいて道筋をたどるときにその共通記号までジャンプ
 させる
などがありますが、どこまで採用するかは本問題を証明する観点からは
大きな影響は与えないようです。しかし、その範囲ははっきりさせて
おく必要はあります。(今回はたまたま操作c無しで可能ですが、場合
によっては操作cが無いと実はある置換は表現できないと言うこともあ
り得ますから。)

 その上で以下のような点を証明すればよいと思います。
1)1:1でかつ漏れがないこと
  何人もが同時に当たりにならないことを示すにはこれを証明しなけ
  ればなりません。また、あみだくじが置換を表すためにはこの条件
  を満たしている必要があります。
  n本の線を考えて、上で示した操作を施した後、線をたどるとき、
  どの線上端の点を選んでも必ずいずれかの線の下端にたどり着く
  こととどの線の下端を選んでも必ずいずれかの線の上端からたどる
  道筋があること。それからそのようなたどる道筋がそれぞれ1本の
  みである事を、あみだくじの定義に基づいて成立することを示すこ
  とが必要です。
2)置換の場合はその定義から置き換える全てのケースを含んでいます
  が、あみだくじの場合はそれは保証されていませんので、定義(規
  約)から出発してそれを示す必要があります。これは次のように考
  えて証明できるのではないかと思います。
  ・任意の置換は互換の積で表される。
  ・任意の互換に対応するあみだくじを作ることが出来る
  ・ある置換に対応するあみだくじが存在する場合、
    その置換と任意の互換の積によって出来る新しい置換に対し、
    既存のあみだくじに、上に述べた筋道の複雑化の操作を適当に
    追加して新しい置換に対応するような新しいあみだくじを作る
    ことが出来る
  ・以上を組み合わせて任意の置換に対応するあみだくじを作ること
   が出来る

 1)、2)を示せば目的は達成できたことになると思いますが、
これはいずれも比較的容易だと思います。

 2本の線を結ぶ場合に操作a、bまでを許し、かつ同一高さで結ぶこと
を許さないなら、上からある高さまで下った時点で最初の出発点がどの線
に入れ替わっているかによりその時点の入れ替えの状態を定義する事が出
来るのと、次にどの入れ替えが行われるかが規定できるので(上の条件を
満たす)任意のあみだくじに対して対応する置換を互換の積で表す時に積
の表現形式(冗長さも含めて)も一意に決められますが、操作cを許す場
合はこれは成り立たず、積の表現形式を対応させること自体が不可能にな
ると思います。しかし、このことは上の証明には影響を与えません。上の
証明では表現形式の対応付けは要求しておらず(表現形式の対応付けが出
来る出来ないに拘わらず)、任意の互換を付け足して出来る新しい置換に
対して適当なあみだくじ側の追加操作により新しい置換に対応するあみだ
くじを作れると言っているだけです。更に言うなら、「あみだくじには
いろいろな操作が用意されているが、置換を表すなら操作aだけで十分」
と言うことが証明できます。(互換を表す操作、新しい置換を表すための
追加操作が操作aで出来ることを示せばOKだが、上の証明2)を具体的
に行うときはそのようになります。)
    • good
    • 0
この回答へのお礼

とても丁寧な回答をありがとうございます
急いでいたもので過去の質問をきっちり把握しておりませんでしたスミマセン
助かりました
本当にありがとうございました

お礼日時:2002/02/07 23:20

前に同じような質問があって


その中で僕が置換とあみだくじの同値性について証明しているので
参考にしてください

参考URL:http://oshiete1.goo.ne.jp/kotaeru.php3?q=180014
    • good
    • 0
この回答へのお礼

ごめんなさい過去の質問をきっちり見てませんでした
非常に助かりました
ありがとうございました

お礼日時:2002/02/07 23:24

変換(線形)前後の点は1対1に対応する、ということではないでしょうか?


例えば、1つの点を変換したときに2つ以上の点に移ることはないし、また2つ以上の点が変換後に1点に集まることはありません。
あみだくじも、スタートとゴールで1対1に対応しているということで、そのような意味で同じことだということだと思います。
    • good
    • 0
この回答へのお礼

簡単に言うとそうなんですね!
うんうん納得!!
わかりやすく教えていただいてありがとうございました!

お礼日時:2002/02/07 23:26

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aと関連する良く見られている質問

Q定番のフリーソフト

フリーソフトを入れたいのですが、定番のフリーソフトは何ですか?
フリーソフトのほうが市販ソフトより性能が上ということはありますか?

Aベストアンサー

僕がパソコンを買い換えたら必ず入れるソフトは…

・GlaryUtilities(統合メンテナンス)
>ワンクリックメンテナンス機能やOSの起動に合わせて起動するソフトの管理など、パソコンのかゆいところに手が届くメンテナンスソフトです。

・UltraDefrag(デフラグ)
>オープンソースの強力なデフラグソフトです。インストール先がCドライブ直下にフォルダを作ってそこにインストールされるという、他のソフトとは若干違う仕様です。オープンソースってのが個人的には気に入ってます。

・K-LiteCodecPack(コーデックパック)
>WindowsMediaPlayerを万能プレイヤーに変えてくれるものです。WMPはあまり多くの動画や音楽の形式には対応していませんが、このソフトを入れれば世の中にあるほぼすべての形式のメディアファイルが再生できるようになります。
メディア系のソフトを何個も入れるのは嫌なので、これを使っています。

・XMediaRecode(エンコーダ)
>動画や音楽の形式を変換するソフトです。設定項目が多く、やや使いにくいですが、性能はピカイチ。特に容量を指定して、その範囲でベストの綺麗さで変換してくれる機能は良く使います。

・GoogleChrome(ブラウザ)
>世界最速と言われるブラウザです。Googleアカウントを持っていれば、AndroidやiOS版のChromeとブックマークや開いているタブが同期できてとても便利です。パソコンを買えた時にいちいちブックマークを再構築するという手間が省けます。豊富な拡張機能も便利で、ページの読み込みもサックサクです。

・LibreOffice(オフィススイート)
>フリーのオフィススイートで昔から知られているOpenOffice.orgから諸事情で派生したソフトです。MSOffice互換で、MSOffice形式での保存も可能。オープンソースで開発されており、さほどMSOffice2003ライクな操作性で、それに慣れている世代の人は不便は感じないと思います。

・ThunderBird(メーラ)
>ブラウザのFirefoxで有名なMozillaが開発しているフリーのメーラの代名詞的なソフトです。現在は新機能の開発が停止しており、概ね保守のみとなっています。

と、このくらいですね。

これらに加えて昔はフリーのセキュリティソフトも使っていました。ここ数年は、有料のものを使うようにしています。

僕がパソコンを買い換えたら必ず入れるソフトは…

・GlaryUtilities(統合メンテナンス)
>ワンクリックメンテナンス機能やOSの起動に合わせて起動するソフトの管理など、パソコンのかゆいところに手が届くメンテナンスソフトです。

・UltraDefrag(デフラグ)
>オープンソースの強力なデフラグソフトです。インストール先がCドライブ直下にフォルダを作ってそこにインストールされるという、他のソフトとは若干違う仕様です。オープンソースってのが個人的には気に入ってます。

・K-LiteCodecPack(コーデッ...続きを読む

Q10進法で表された数0.12を5進法で表せ。

整数を10進法から5進法にするのは出来るのですが少数を変換するのが、
できません。どうすればいいか教えてください。

Aベストアンサー

1回5倍して1になる量は五進法で表すと  0.1
2回5倍して1になる量は五進法で表すと  0.01
3回5倍して1になる量は五進法で表すと  0.001

0.12 × 5 = 0.6  ・・・  五進法の小数第一位は   0(1回5倍して0)
0.6 × 5 = 3.0  ・・・  五進法の小数第一位は   3(2回5倍して3)
 ※これ以降は、小数点以下がすべて0なのでこれ以上は変化がないため、これで終了。

 従って、  0.03  がこたえです。

Qフリーソフトの寄与したことありますか?

多少パソコンの扱いに慣れていれば、フリーソフトというものを
お使いだと思いますが、よく寄与歓迎をもとめるフリーソフトが
あると思いますが、海外製のフリーソフトのほうが多いみたいですが

でも海外製のフリーソフトではなかなか寄与するのも手順がわからず
大変そうですが、国産のフリーソフトなら可能そうですが、

質問ですがフリーソフトで寄与したことがある方っていらっしゃいますか?
寄与したことがある方は金額的にいくらほど寄与したことがありますか?
シェアソフトは含まないものとして回答お願いします。

Aベストアンサー

>結構善意の入金される方もいるのですね、どうも勉強になりました。

自分が普段使っているソフトウェアは長くメンテナンスされて欲しいじゃないですか。
その作者のモチベーションが金銭だというのであれば、多少の額を払うのもやぶさかではないですよ。

フリーソフトというのは、メンテナンスを続けていくのが非常に難しい配布形態なんですね。
タダだから突然開発を止めても文句を言われにくいので、容易に投げ出してしまえるわけですよ。

お金を払うことで、少しても作者のヤル気が出るならラッキー。という思想です。

寄付を求めていない場合は、金銭ではなく使用者からのフィードバックが主なモチベーションになるので、
なるべくバグ報告をしたり、改善の要望を出したりするのが使用者の勤めというものです。

Q線形代数 線形空間の問題

[]は下つき文字です。

a,b,c,dを異なる実数、f[1],f[2]f[3],f[4]をR{x}[3]の4つの要素として
4×4行列
V=((f[1](a),f[2](a).f[3](a),f[4](a)),
(f[1](b),f[2](b).f[3](b),f[4](b)),
(f[1](c),f[2](c).f[3](c),f[4](c)),
(f[1](d),f[2](d).f[3](d),f[4](d)))

を定義する。

det(V)=0のときf[1],f[2]f[3],f[4]は一次従属であることを示せ。

この問題が解けなくて困っています。

どなたか解き方を教えてください

Aベストアンサー

[※] ax^3 + bx^2 + cx + d = (1, x, x^2, x^3) (d, c, b, a)^t
(^t は転置)
と書けることを使って行列 V を 2つの行列の積に分解します.
分解して得られる 2つの行列のうち左のものがファンデルモンドの行列式に現れる行列 (かその転置). 右にあるのは係数を並べた行列です.
ここで両辺の行列式をとると係数行列の行列式が 0 であることが分かります.
最後に [※] を使うために左から (1, x, x^2, x^3) を掛ければ終わり.
やってみればわかります.

Qアクセスに替わるフリーソフト

アクセスを勉強したいのです。マイクロOfficeのソフトなら、フリーソフトならオープンOfficeがフリーソフトであります。アクセスでフリーソフトで同じように使えるソフト(一般的にメジャー)はあるのでしょうか?

Aベストアンサー

その、オープンOfficeがアクセスも入っています

とーぜんの事ですがMSアクセスと違う所もあります、完全互換じゃないので、ご注意ください

Q線形代数[線形従属・線形結合]

線形代数についての質問です。
1:0ベクトルを含むベクトルたちは、線形従属であることを示せ。
2:少なくとも2つの同じベクトルを含むベクトルたちは、線形従属であることを示せ。
3:次の2つの条件(1)(2)が同値であることを示せ。
(1)a_1ベクトル,・・・,a_nベクトルは線形従属である。
(2)a_1ベクトル,・・・,a_nベクトルが他のベクトルたちの線形結合で表される。

当たり前だろうと思ってしまい、証明が出来ません。
どなたが教えてくれるとありがたいです。

Aベストアンサー

>> 当たり前だろうと思ってしまい、証明が出来ません。

とのことですが、#3さんもご指摘の通り、こういうタイプの問題は、
定義さえはっきりさせれば簡単に答えられるものがよくあります。
というわけで定義をはっきりさせましょう。
(以下、ベクトルを示す矢印は省略することがありますので、
適宜補ってください。)

ベクトル a[1]~a[n] 、係数 c[1]~c[n] について、
「Σc[j]a[j] = 0 ならば c[1] = … = c[n] = 0」が成り立つとき、
ベクトル a[1]~a[n] は線形独立である、といいます。

そうでないとき、つまり、 Σc[j]a[j] = 0 を満たす、
c[1]~c[n] のどれかが0でないような係数 c[1]~c[n] が存在するとき、
ベクトル a[1]~a[n] は線形従属である、といいます。

上記定義にあてはめれば、容易に証明できます。

問題1については、a[1] = 0↑ とすると、
c[1] = 1 , c[2] = c[3] = … = c[n] = 0 は
Σc[j]a[j] = 0 を満たすので、ベクトル a[1]~a[n] は線形従属です。

問題2については、a[1] = a[2] とすると、
c[1] = 1 , c[2] = -1 , c[3] = c[4] = … = c[n] = 0 は
Σc[j]a[j] = 0 を満たすので、ベクトル a[1]~a[n] は線形従属です。

問題3については、問題に不備があるようです。
(2)を、「a_1ベクトル,・・・,a_nベクトルのどれかが
     他のベクトルたちの線形結合で表される。」にして
解いてみてください。

(a) a[1]~a[n] が線形従属ならば、
   a[1]~a[n] のうちのどれかは他のベクトルの線形結合で表せる
(b) a[1] が他のベクトルの線形結合で表せるならば、
   a[1]~a[n] は線形従属である
ことを示せばOKです。

問題3は答えを書きませんので、ご自分でやってみてください。
わからなければ、また質問して頂いてかまいません。

>> 当たり前だろうと思ってしまい、証明が出来ません。

とのことですが、#3さんもご指摘の通り、こういうタイプの問題は、
定義さえはっきりさせれば簡単に答えられるものがよくあります。
というわけで定義をはっきりさせましょう。
(以下、ベクトルを示す矢印は省略することがありますので、
適宜補ってください。)

ベクトル a[1]~a[n] 、係数 c[1]~c[n] について、
「Σc[j]a[j] = 0 ならば c[1] = … = c[n] = 0」が成り立つとき、
ベクトル a[1]~a[n] は線形独立である、といいます。

そ...続きを読む

Qフリーソフトのオススメ

フリーソフトでオススメがあれば教えてください。。。 
(1)欲しいのは動画が快適に見れるフリーソフト。
(2)ダウンロードが早くなるフリーソフト
(3)常駐してパソコンを最適化してくれるフリーソフト

オススメガあれば教えてください

Aベストアンサー

(1)動画が快適に見れるかどうかはパソコンのスペックによります

(2)ダウンローダーというジャンルがありますので、自分に合うものをお探しください。どういう物をダウンロードするかにもよりますので。

(3)OS毎に最適化とか高速化ツールがありますので、ご自分にあったものを。パソコンユーザーすべての要求を満たすようなものはないので、ツールごとに一長一短があります。

Windowsユーザーなら窓の杜(まどのもり)やVectorのサイトで分類訳されているので、そちらで探してみてください。

Q非線形システム・線形システム・線形化・微分方程式について。

非線形システム・線形システム・線形化・微分方程式について。

私は機械系の大学に通ってるのですが、線形システムや非線形システムというのがよく分かりません。
授業で、ある関数f(x)について、f(x1+x2)=f(x1)+f(x2)が成立するのが線形で、成立しないものが非線形だという事は習い、納得出来ました。
しかし実際にどんなシステム(現象?運動?)が線形なのか、非線形なのかというイメージが全く湧きません。

よく色んな人の研究発表の場で、質問者が「これは非線形になると思うんですけど~」とか言ってるのを聞くんですが、どうやってあんなにすぐ判別出来ているのでしょうか。
しかもだいたいがf(x)=~のような関数ではなく、微分とかの入ってる微分方程式を見て判別しているように思えます。

そこで質問なのですが、線形・非線形とはそれぞれ具体的にどんなシステムなのか。どうやって判断すればよいのか。また、微分方程式とは何を表しているのか。非線形のシステムはどうやって線形にしているのか(線形化?)線形化するとどうなるのか。


質問が多くなってしまったので、全部いっぺんにでなくて小分けに回答して頂いてもいいので、どなたかご教授していただけないでしょうか。
よろしくお願いします。

非線形システム・線形システム・線形化・微分方程式について。

私は機械系の大学に通ってるのですが、線形システムや非線形システムというのがよく分かりません。
授業で、ある関数f(x)について、f(x1+x2)=f(x1)+f(x2)が成立するのが線形で、成立しないものが非線形だという事は習い、納得出来ました。
しかし実際にどんなシステム(現象?運動?)が線形なのか、非線形なのかというイメージが全く湧きません。

よく色んな人の研究発表の場で、質問者が「これは非線形になると思うんですけど~」とか言っ...続きを読む

Aベストアンサー

線型システムってのは、
f が線型(一次関数)だってことじゃなく、
f が線型微分方程式を満たすという意味
で言います。

線型微分方程式ってのは、
f の導関数 f, f', f'', f''', … に
それぞれ x の関数を掛けて足したものが =0
という形の方程式のことです。

Qフリーソフトはなぜフリーで使えるのですか?

私は便利なフリーソフトをたくさん使っています。しかし、なぜ便利なフリーソフトがあるのに、市販されている同じような機能を持ったものが売れるのでしょうか?フリーソフトを使うことの弊害はありますか?

フリーソフトを提供してくれる人は、なぜお金を取ろうとしないのでしょうか?何のために作成しているのでしょうか?
初心者ですがよろしくお願いいたします

Aベストアンサー

>市販されている同じような機能を持ったものが売れるのでしょうか?
>フリーソフトを使うことの弊害はありますか?

市販のソフトを開発するのに工数がかかるのは、バグ取りすることです。通常の処理をして正しく動作するプログラムはそれなりに作ることができますが、イレギュラー操作しても問題無いように処理するのは、いろいろな事例をつぶす必要があります。
又、OSのバージョン対応も必要です。今でもWin98でも動くことを要求するユーザーはそれなりにいるしWinME、Win2000、XP、VISTA、全てで動作するように(あるいはどのOSでは動作しないかの検証をすることに)処理するバグ取り(バグとは言わないかな)も大変です。

フリーならこれらが多少いい加減でも、メイン機能が正しく動けば使う方も文句言わないと思いますが、有料ソフトの場合バグがあれば文句が沢山でます。だから高機能を持ったソフトだけどフリーという方がたくさんいらっしゃると思います。

>フリーソフトを提供してくれる人は、なぜお金を取ろうとしないので
>しょうか?
これは趣味だからなのでは(^_^;)
フリーソフトを作成される方は、自分で興味を持ってプログラムを勉強して、いろいろな事ができるようになります。そしてそれなりの機能を持ったプログラムが完成すると自分で使うわけですが、それだけでは満足できなくなるように思います。多くの人に使ってもらって自分はこんなことができると認めてもらったり、又自分では気づかないソフトの問題点を指摘してもらって更に完成度を高め、市販のプログラムにもひけを取らないソフトを完成させることで自己満足を得るし、それを利用するユーザーからは感謝される。
自分でプログラム開発して自分で使っているだけではこの喜びは味わえないのではないでしょうか。

フリーソフトは本当に便利なものが沢山ありますよね。フリーソフトの作者に感謝して使っていきたいと思います。

>市販されている同じような機能を持ったものが売れるのでしょうか?
>フリーソフトを使うことの弊害はありますか?

市販のソフトを開発するのに工数がかかるのは、バグ取りすることです。通常の処理をして正しく動作するプログラムはそれなりに作ることができますが、イレギュラー操作しても問題無いように処理するのは、いろいろな事例をつぶす必要があります。
又、OSのバージョン対応も必要です。今でもWin98でも動くことを要求するユーザーはそれなりにいるしWinME、Win2000、XP、VISTA、全てで動作する...続きを読む

Q線形代数の証明問題がわかりません

ベクトルの問題で、自力ではどうにもできない問題があるのでよろしく願いします。

三つのベクトルA,B,Cが同一平面内にあるとき次式が成り立つこと示せ。
1)A・(B×C)=0
2)pA+qB+rC=0 (p,q,rは少なくとも二つは0でない実数)

1)はわかるので2)をよろしくお願いします。

Aベストアンサー

「A,B,Cはゼロベクトルではない」てのが仮定されてないか?

三つのベクトルA,B,Cが同一平面内にあるとき
つまり,
A,B,Cは一次従属
だから,
pA+qB+rC=0 (p,q,rの少なくとも一つは0ではない)
もし,p,q,rのうち,二つが0だとすると,
A,B,Cのうちどれかが0になるので
p,q,rの少なくとも二つは0ではない.


人気Q&Aランキング

おすすめ情報