Bijective proof (original) (raw)
In combinatorics, bijective proof is a proof technique for proving that two sets have equally many elements, or that the sets in two combinatorial classes have equal size, by finding a bijective function that maps one set one-to-one onto the other. This technique can be useful as a way of finding a formula for the number of elements of certain sets, by corresponding them with other sets that are easier to count. Additionally, the nature of the bijection itself often provides powerful insights into each or both of the sets.
| Property | Value | |||
|---|---|---|---|---|
| dbo:abstract | In combinatorics, bijective proof is a proof technique for proving that two sets have equally many elements, or that the sets in two combinatorial classes have equal size, by finding a bijective function that maps one set one-to-one onto the other. This technique can be useful as a way of finding a formula for the number of elements of certain sets, by corresponding them with other sets that are easier to count. Additionally, the nature of the bijection itself often provides powerful insights into each or both of the sets. (en) Zenbaketa bikoitza konbinatorian erabili ohi den frogapen metodoa da, non multzo baten zenbaketa bi era ezberdinetara egiten den, suertatzen diren bi adierazpenak berdinak direla egiaztatzeko. (eu) En mathématiques, une preuve par bijection (ou démonstration par bijection) est une technique de démonstration qui consiste à obtenir l'égalité de deux expressions entières en exhibant une bijection entre deux ensembles dont les deux expressions sont les cardinaux. Autrement dit, on examine deux ensembles finis X et Y, on les dénombre et au moyen d'une bijection de X sur Y, on en déduit que les résultats des comptages sont égaux. On présente souvent la démonstration en disant qu'on a transformé le problème de dénombrement en un problème équivalent. La branche de la combinatoire qui étudie particulièrement les démonstrations par bijection s'appelle la combinatoire bijective. (fr) Una dimostrazione mediante biiezione è un genere di dimostrazione utilizzata in combinatoria che ha come scopo una uguaglianza di due espressioni enumerative che forniscono le cardinalità di due insiemi finiti X e Y consiste nella determinazione di una funzione biiettiva dalla quale si può dedurre immediatamente . Spesso la funzione β viene individuata precisando due costruzioni: una B che trasforma un qualsiasi elemento x di X in un elemento di Y con il ruolo di β(x) e una G che trasforma un qualsiasi elemento y di Y in un elemento di X e tale da fornire la funzione inversa della β. Questo modo di procedere viene adottato in molte situazioni nelle quali serve conoscere la cardinalità di un insieme X tendenzialmente "complesso" e/o "nuovo" e la esistenza della biiezione β permette di ottenere dalla cardinalità di un insieme più semplice, o precedentemente conosciuto. In molti casi la conoscenza della β consente di ottenere una consapevolezza molto maggiore della struttura dei due insiemi e ad individuare un livello di astrazione superiore al quale entrambi gli insiemi si possono ricondurre con una più chiara visione dei problemi che riguardano i due insiemi. Negli ultimi decenni si sono trovate numerose dimostrazione mediante biiezione le quali hanno portato rilevanti avanzamenti per la combinatoria. (it) Биективное доказательство — это техника доказательства, при которой находится биективная функция f : A → B между двумя конечными множествами A и B или сохраняющая размер биективная функция между двумя , чем доказывается одинаковость числа элементов, |A | = | B | . Место, где техника полезна — когда мы хотим знать размер A, но не можем найти прямого пути подсчёта элементов множества. В этом случае установление биекции между A и некоторым множеством B решает задачу, если число элементов множества B вычислить проще. Другое полезное свойство этой техники — природа биекции само по себе часто даёт мощную информацию о каждом из двух множеств. (ru) Бієкти́вне дове́дення — це техніка доведення, за якої знаходиться бієктивна функція f : A → B між двома скінченними множинами A і B або бієктивна функція, що зберігає розмір, між двома , чим доводиться однаковість числа елементів, |
| dbo:wikiPageExternalLink | http://mathworld.wolfram.com/Garsia-MilneInvolutionPrinciple.html https://wayback.archive-it.org/all/20151023194824/http:/www.math.vt.edu/people/nloehr/bijbook.html https://web.archive.org/web/20031104095246/http:/www.math.temple.edu/~zeilberg/mamarim/mamarimPDF/ohara.pdf http://www.crcpress.com http://www.math.dartmouth.edu/~doyle/docs/three/three.pdf https://www.math.ucla.edu/~pak/papers/psurvey.pdf http://www.emis.de/journals/DMTCS/volumes/abstracts/pdfpapers/dm010104.pdf http://www.emis.de/journals/EJC/Volume_4/PDF/v4i1r20.pdf | |||
| dbo:wikiPageID | 917006 (xsd:integer) | |||
| dbo:wikiPageLength | 7290 (xsd:nonNegativeInteger) | |||
| dbo:wikiPageRevisionID | 1085237414 (xsd:integer) | |||
| dbo:wikiPageWikiLink | dbr:Schröder–Bernstein_theorem dbr:Binomial_theorem dbc:Enumerative_combinatorics dbr:Pentagonal_number_theorem dbr:Double_counting_(proof_technique) dbr:Prüfer_sequence dbc:Articles_containing_proofs dbr:Complement_(set_theory) dbr:MathWorld dbr:Combination dbr:Combinatorial_class dbr:Combinatorial_principles dbr:Combinatorial_proof dbr:Combinatorics dbr:Igor_Pak dbr:Cayley's_formula dbr:William_Burnside dbr:Number_theory dbr:Partition_(number_theory) dbr:Discrete_mathematics dbr:Graph_theory dbr:Mathematical_proof dbc:Mathematical_proofs dbr:John_Horton_Conway dbr:Labeled_tree dbr:Doron_Zeilberger dbr:Injective_function dbr:Onto dbr:Catalan_number dbr:Categorification dbr:Symmetric_group dbr:Functional_notation dbr:Robinson-Schensted_algorithm dbr:Bijective_function dbr:Young_diagram | |||
| dbp:wikiPageUsesTemplate | dbt:ISBN dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description | |||
| dct:subject | dbc:Enumerative_combinatorics dbc:Articles_containing_proofs dbc:Mathematical_proofs | |||
| gold:hypernym | dbr:Technique | |||
| rdf:type | dbo:TopicalConcept yago:WikicatMathematicalProofs yago:Abstraction100002137 yago:Argument106648724 yago:Communication100033020 yago:Evidence106643408 yago:Indication106797169 yago:MathematicalProof106647864 yago:Proof106647614 | |||
| rdfs:comment | In combinatorics, bijective proof is a proof technique for proving that two sets have equally many elements, or that the sets in two combinatorial classes have equal size, by finding a bijective function that maps one set one-to-one onto the other. This technique can be useful as a way of finding a formula for the number of elements of certain sets, by corresponding them with other sets that are easier to count. Additionally, the nature of the bijection itself often provides powerful insights into each or both of the sets. (en) Zenbaketa bikoitza konbinatorian erabili ohi den frogapen metodoa da, non multzo baten zenbaketa bi era ezberdinetara egiten den, suertatzen diren bi adierazpenak berdinak direla egiaztatzeko. (eu) Биективное доказательство — это техника доказательства, при которой находится биективная функция f : A → B между двумя конечными множествами A и B или сохраняющая размер биективная функция между двумя , чем доказывается одинаковость числа элементов, |A | = | B | . Место, где техника полезна — когда мы хотим знать размер A, но не можем найти прямого пути подсчёта элементов множества. В этом случае установление биекции между A и некоторым множеством B решает задачу, если число элементов множества B вычислить проще. Другое полезное свойство этой техники — природа биекции само по себе часто даёт мощную информацию о каждом из двух множеств. (ru) Бієкти́вне дове́дення — це техніка доведення, за якої знаходиться бієктивна функція f : A → B між двома скінченними множинами A і B або бієктивна функція, що зберігає розмір, між двома , чим доводиться однаковість числа елементів, |
| rdfs:label | Bijective proof (en) Zenbaketa bikoitz (konbinatoria) (eu) Preuve par bijection (fr) Dimostrazione mediante biiezione (it) Биективное доказательство (ru) 双射法 (zh) Бієктивне доведення (uk) | |||
| owl:sameAs | freebase:Bijective proof yago-res:Bijective proof wikidata:Bijective proof dbpedia-eu:Bijective proof dbpedia-fa:Bijective proof dbpedia-fr:Bijective proof dbpedia-it:Bijective proof dbpedia-ru:Bijective proof dbpedia-uk:Bijective proof dbpedia-zh:Bijective proof https://global.dbpedia.org/id/4nfVZ | |||
| prov:wasDerivedFrom | wikipedia-en:Bijective_proof?oldid=1085237414&ns=0 | |||
| foaf:isPrimaryTopicOf | wikipedia-en:Bijective_proof | |||
| is dbo:wikiPageWikiLink of | dbr:Proofs_That_Really_Count dbr:MacMahon's_master_theorem dbr:Bipartite_double_cover dbr:Curtis_Greene dbr:Double_counting_(proof_technique) dbr:Pseudoforest dbr:Ordered_Bell_number dbr:Combinatorial_class dbr:Combinatorial_principles dbr:Combinatorial_proof dbr:Combinatorial_species dbr:Combinatorics dbr:Igor_Pak dbr:Cayley's_formula dbr:Eulerian_path dbr:Schröder–Hipparchus_number dbr:Bijection dbr:Rodica_Simion dbr:Directed_acyclic_graph dbr:Double_factorial dbr:BEST_theorem dbr:Catalan_number dbr:Outline_of_combinatorics dbr:Outline_of_discrete_mathematics dbr:Polite_number | |||
| is foaf:primaryTopic of | wikipedia-en:Bijective_proof |