Derangement (original) (raw)
En matemàtiques combinatòries, un desarranjament és una permutació en la qual cap dels elements del conjunt no apareix en la seva posició original. És a dir, és una bijecció φ des d'un conjunt S a si mateix sense punts fixos: per a tot x en S, φ(x) ≠ x. Els nombres de desarranjaments per a conjunts de mida n, en variar n, s'anomenen "nombres de Montmort" o "nombres de desarranjament" (i es pot generalitzar a ); la funció que expressa aquest nombre com a funció del nombre d'elements del conjunt és la funció . El primer a estudiar el problema de comptar desarranjaments va ser el 1708; el va resoldre el 1713, igual que Nicholas Bernoulli al voltant de la mateixa època.
| Property | Value |
|---|---|
| dbo:abstract | En matemàtiques combinatòries, un desarranjament és una permutació en la qual cap dels elements del conjunt no apareix en la seva posició original. És a dir, és una bijecció φ des d'un conjunt S a si mateix sense punts fixos: per a tot x en S, φ(x) ≠ x. Els nombres de desarranjaments per a conjunts de mida n, en variar n, s'anomenen "nombres de Montmort" o "nombres de desarranjament" (i es pot generalitzar a ); la funció que expressa aquest nombre com a funció del nombre d'elements del conjunt és la funció . El primer a estudiar el problema de comptar desarranjaments va ser el 1708; el va resoldre el 1713, igual que Nicholas Bernoulli al voltant de la mateixa època. (ca) Eine fixpunktfreie Permutation oder Derangement (von französisch déranger „durcheinanderbringen“) ist in der Kombinatorik eine Permutation der Elemente einer Menge, sodass kein Element seine Ausgangsposition beibehält. Die Anzahl möglicher fixpunktfreier Permutationen einer Menge mit Elementen wird durch die Subfakultät angegeben. Für wachsendes strebt innerhalb der Menge der Permutationen von Elementen der Anteil der fixpunktfreien Permutationen sehr schnell gegen den Kehrwert der eulerschen Zahl . Sollen in einer Permutation manche der Elemente an ihrem alten Platz verbleiben, spricht man von einem partiellen Derangement, deren Anzahl durch die Rencontres-Zahlen ermittelt werden kann. (de) In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position. In other words, a derangement is a permutation that has no fixed points. The number of derangements of a set of size n is known as the subfactorial of n or the n-th derangement number or n-th de Montmort number. Notations for subfactorials in common use include !n, Dn, dn, or n¡. For n > 0, the subfactorial !n equals the nearest integer to n!/e, where n! denotes the factorial of n and e is Euler's number. The problem of counting derangements was first considered by Pierre Raymond de Montmort in 1708; he solved it in 1713, as did Nicholas Bernoulli at about the same time. (en) Konbinatorian, nahasmena multzo bateko elementuen permutazio bat da, non inongo elementurik ez dagoen bere jatorrizko kokapenean, hau da, nahasmena gabeko permutazio bat da. Adibidez, bedi ABCD multzo ordenatua, multzoko nahasmen guztiak zerrenda honetan agertzen direnak dira: BADC, BCDA, BDAC,CADB, CDAB, CDBA,DABC, DCAB, DCBA. Nahasmenen ebazkizuna elementu kopuru bati dagozkion nahasmenen kopurua zenbatzean datza. n elementuko multzo batean dauden nahasmenen kopurua n zenbakiaren da. Nahasmen partzialak ere badaude, non zenbait edo kointzidentzia onartzen den. Nahasmen partzialen kopuruak zenbatzen dituzten formulak dira. Nahasmenen ebazkizuna Pierre Raymond de Montmort matematikariak asmatu zuen, bere Essai d'analyse sur les jeux de hasard (euskaraz, Ausazko jokoen gaineko azterketarako entsegua) izeneko liburuan, 1708. urtean. Montmort berak ebatzi zuen ebazkizuna 5 urte geroago, 1713. urtean. (eu) En mathématiques, le problème des rencontres, ou problème de Montmort, ou encore problème des chapeaux, consiste à déterminer la probabilité que, n jetons numérotés de 1 à n ayant été mis au hasard dans des cases elles-mêmes numérotées de 1 à n, aucun jeton ne soit à sa place (ou celle de l'évènement contraire). De façon plus savante, c'est la recherche de la probabilité qu'une permutation prise au hasard soit un dérangement, c'est-à-dire ne possède pas de « rencontre », autrement dit de point fixe. Le problème des rencontres a été posé pour la première fois par Pierre Rémond de Montmort en 1708, qui l'a résolu en 1713, en même temps que Nicolas Bernoulli. (fr) 조합론에서 완전순열(영어: complete permutation) 또는 교란(영어: derangement 디레인지먼트[*])은 모든 원소의 위치를 바꾸는 순열이다. (ko) 完全順列（かんぜんじゅんれつ、英: complete permutations）、もしくは攪乱順列（かくらんじゅんれつ、英: derangement）とは、整数 1, 2, 3, …, n を要素とする順列において、i 番目 (i ≦ n) が i でない順列である。順列を置換とみると、完全順列は不動点の個数が 0 の置換に対応している。乱列、混乱順列ともいう。 (ja) In combinatoria vengono dette dismutazioni (o sconvolgimenti, o permutazioni complete) le permutazioni di un insieme che non fissano alcun elemento, ovvero tali che nessuno degli elementi dell'insieme iniziale compaia nella sua posizione originaria. Formalmente, se le permutazioni di un insieme X sono le funzioni biiettive , le dismutazioni di X sono le funzioni biiettive tali che . Si verifica facilmente che non esiste alcuna dismutazione per un insieme di un solo elemento, ne esiste 1 per un insieme di 2 elementi, 2 per un insieme di 3 elementi, 9 per uno di 4 elementi... Ad esempio, le 9 dismutazioni possibili della parola "ABCD" sono: BADC BCDA BDAC CADB CDAB CDBADABC DCAB DCBA (it) In de combinatoriek, een deelgebied van de wiskunde, is een derangement (van Frans: déranger, verstoren) een permutatie van de elementen van een verzameling waarbij geen van de elementen op z'n plaats blijft. Een derangement is dus een permutatie zonder dekpunt. Het aantal mogelijke derangementen van elementen is gedefinieerd als de subfaculteit van . Men noteert dit aantal ook als of en spreekt van derangementgetal of montmortgetal. Tot nu toe is er geen standaard notatie voor de subfaculteit; ook de notatie ¡ wordt wel gebruikt in plaats van . Het probleem van het tellen van het aantal derangementen werd in 1708 voor het eerst beschouwd door Pierre Raymond de Montmort, die het probleem oploste in 1713, ongeveer tegelijkertijd met Nicolaas Bernoulli. (nl) Em análise combinatória, um desarranjo, também conhecido como permutação caótica ou derangement (do francês) é uma espécie de permutação em que nenhum elemento do conjunto permanece na mesma posição. Formalmente falando, um desarranjo é uma bijeção em um conjunto finito que não possui pontos fixos. O número de diferentes desarranjos em um conjunto de n elementos é definido como o subfatorial de n e é denotado . O problema de contar desarranjos foi primeiramente considerado por em 1708 e resolvido em 1713. Nicholas Bernoulli obteve o mesmo resultado na mesma época. (pt) Nieporządek – permutacja elementów zbioru, która nie pozostawia żadnego elementu na swoim oryginalnym miejscu (innymi słowy nie posiada żadnego punktu stałego). Liczbę nieporządków danego n-elementowego zbioru oznacza się symbolem podsilni !n, n¡ lub (zwanej również „dolną silnią”). Problem zliczania nieporządków był rozważany przez Pierre’a Rémonda de Montmorta w 1708; podał on rozwiązanie w 1713, równolegle z Nicolausem Bernoullim. Stąd też innym określeniem nieporządków jest „liczby de Montmorta”. (pl) В комбинаторике беспорядком называется перестановка без неподвижных точек. (ru) Inom matematiken är ett derangemang eller derangement, en permutation utan fixpunkter på en mängd. Med andra ord är permutationen ett derangemang, om σ(x) inte är lika med x för något enda x i M. Om M är en ändlig mängd av storlek n, så är antalet derangemang på M för n = 1, 2, 3, 4, 5, 6, blir denna summa respektive 0, 1, 2, 9, 44, 265. Summan kan även beräknas rekursivt med formeln: , vilka tal kallas för De Montmort-tal. Summan kan beräknas medelst principen om inklusion-exklusion, där n! är fakulteten av n. För stora n betyder detta, att antalet derangemang ligger mycket nära n!/e, där e är basen för de naturliga logaritmerna. En ofta förekommande sannolikhetsteoretisk formulering av detta illustreras av följande berättelse, eller av någon av variant av den: Ett stort antal herrar har hängt av sig sina hattar inför en herrmiddag. Av någon orsak har herrarna när de skall åka hem inte längre lika stor sinnesnärvaro som förut, och därför tar var och en helt slumpmässigt en av hattarna. Fråga: Hur stor är sannolikheten att ingen herre kommer hem med sin egen hatt? Svaret på frågan är alltså "Nästan precis e-1". (Om antalet herrar var n, så är det exakta svaret summan ovan dividerad med n!, vilket är en i taylorutvecklingen av e-1.) (sv) 错排问题是组合数学中的问题之一。考虑一个有个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 个元素的错排数记为或。 研究一个排列错排个数的问题，叫做错排问题或称为更列问题。 最早研究错排问题的是尼古拉·伯努利和欧拉，因此历史上也称为伯努利-欧拉的装错信封的问题。这个问题有许多具体的版本，如在写信时将封信装到个不同的信封里，有多少种全部装错信封的情况？又比如四人各写一张贺年卡互相赠送，有多少种赠送方法？自己写的贺年卡不能送给自己，所以也是典型的错排问题。 (zh) В комбінаториці безладом називається перестановка без нерухомих точок, тобто жодний елемент не залишається на початковому місці. Число безладів множини з n елементів, зазвичай позначається Dn, dn, або !n, і називається «числом безладів» або «числом Монмора». (Ці числа узагальнюються числами, що відповідають числу зустрічей.) Функція субфакторіал (не плутайте з факторіалом n!) ставить у відповідність числу n число !n. Не існує стандартного позначення для субфакторіалу. Інколи позначають n¡ замість !n. Задача підрахунку числа безладів була уперше розглянута П'єром де Монмором у 1708; він розв'язав її у 1713, як це зробив Микола I Бернуллі приблизно в той же час. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/N!_v_!n.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.math.dartmouth.edu/~doyle/docs/menage/menage/menage.html http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Hassani/hassani5.html http://mathworld.wolfram.com/Derangement.html http://math.ucr.edu/home/baez/qg-winter2004/derangement.pdf |
| dbo:wikiPageID | 162132 (xsd:integer) |
| dbo:wikiPageInterLanguageLink | dbpedia-es:Subfactorial dbpedia-fr:Problème_des_rencontres |
| dbo:wikiPageLength | 27851 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1122558919 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Bell_number dbr:Ménage_problem dbc:Fixed_points_(mathematics) dbr:Permutation dbr:Rencontres_numbers dbr:Random_permutation_statistics dbc:Permutations dbr:Mathematics dbr:NP-complete dbr:Combinatorics dbc:Integer_sequences dbr:Fixed_point_(mathematics) dbr:Floor_function dbr:Probability dbr:Nearest_integer_function dbr:Laguerre_polynomials dbr:Big_O_notation dbr:Pierre_Raymond_de_Montmort dbr:Inclusion–exclusion_principle dbr:Incomplete_gamma_function dbr:Set_(mathematics) dbr:Nicolaus_I_Bernoulli dbr:Up_to dbr:Factorial dbr:Permutation_group dbr:Euler's_number dbr:Bell_numbers dbr:Inclusion-exclusion dbr:Derangements dbr:Semi-log dbr:Surjection dbr:V:Symmetric_group_S4 dbr:File:Complex_plot_for_derangement_real_between_-1_to_11.png dbr:File:Derangement4.png dbr:File:N!_v_!n.svg |
| dbp:wikiPageUsesTemplate | dbt:' dbt:Cite_web dbt:For dbt:Reflist dbt:Short_description dbt:Wiktionary |
| dct:subject | dbc:Fixed_points_(mathematics) dbc:Permutations dbc:Integer_sequences |
| rdfs:comment | En matemàtiques combinatòries, un desarranjament és una permutació en la qual cap dels elements del conjunt no apareix en la seva posició original. És a dir, és una bijecció φ des d'un conjunt S a si mateix sense punts fixos: per a tot x en S, φ(x) ≠ x. Els nombres de desarranjaments per a conjunts de mida n, en variar n, s'anomenen "nombres de Montmort" o "nombres de desarranjament" (i es pot generalitzar a ); la funció que expressa aquest nombre com a funció del nombre d'elements del conjunt és la funció . El primer a estudiar el problema de comptar desarranjaments va ser el 1708; el va resoldre el 1713, igual que Nicholas Bernoulli al voltant de la mateixa època. (ca) Eine fixpunktfreie Permutation oder Derangement (von französisch déranger „durcheinanderbringen“) ist in der Kombinatorik eine Permutation der Elemente einer Menge, sodass kein Element seine Ausgangsposition beibehält. Die Anzahl möglicher fixpunktfreier Permutationen einer Menge mit Elementen wird durch die Subfakultät angegeben. Für wachsendes strebt innerhalb der Menge der Permutationen von Elementen der Anteil der fixpunktfreien Permutationen sehr schnell gegen den Kehrwert der eulerschen Zahl . Sollen in einer Permutation manche der Elemente an ihrem alten Platz verbleiben, spricht man von einem partiellen Derangement, deren Anzahl durch die Rencontres-Zahlen ermittelt werden kann. (de) 조합론에서 완전순열(영어: complete permutation) 또는 교란(영어: derangement 디레인지먼트[*])은 모든 원소의 위치를 바꾸는 순열이다. (ko) 完全順列（かんぜんじゅんれつ、英: complete permutations）、もしくは攪乱順列（かくらんじゅんれつ、英: derangement）とは、整数 1, 2, 3, …, n を要素とする順列において、i 番目 (i ≦ n) が i でない順列である。順列を置換とみると、完全順列は不動点の個数が 0 の置換に対応している。乱列、混乱順列ともいう。 (ja) Em análise combinatória, um desarranjo, também conhecido como permutação caótica ou derangement (do francês) é uma espécie de permutação em que nenhum elemento do conjunto permanece na mesma posição. Formalmente falando, um desarranjo é uma bijeção em um conjunto finito que não possui pontos fixos. O número de diferentes desarranjos em um conjunto de n elementos é definido como o subfatorial de n e é denotado . O problema de contar desarranjos foi primeiramente considerado por em 1708 e resolvido em 1713. Nicholas Bernoulli obteve o mesmo resultado na mesma época. (pt) Nieporządek – permutacja elementów zbioru, która nie pozostawia żadnego elementu na swoim oryginalnym miejscu (innymi słowy nie posiada żadnego punktu stałego). Liczbę nieporządków danego n-elementowego zbioru oznacza się symbolem podsilni !n, n¡ lub (zwanej również „dolną silnią”). Problem zliczania nieporządków był rozważany przez Pierre’a Rémonda de Montmorta w 1708; podał on rozwiązanie w 1713, równolegle z Nicolausem Bernoullim. Stąd też innym określeniem nieporządków jest „liczby de Montmorta”. (pl) В комбинаторике беспорядком называется перестановка без неподвижных точек. (ru) 错排问题是组合数学中的问题之一。考虑一个有个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 个元素的错排数记为或。 研究一个排列错排个数的问题，叫做错排问题或称为更列问题。 最早研究错排问题的是尼古拉·伯努利和欧拉，因此历史上也称为伯努利-欧拉的装错信封的问题。这个问题有许多具体的版本，如在写信时将封信装到个不同的信封里，有多少种全部装错信封的情况？又比如四人各写一张贺年卡互相赠送，有多少种赠送方法？自己写的贺年卡不能送给自己，所以也是典型的错排问题。 (zh) In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position. In other words, a derangement is a permutation that has no fixed points. The number of derangements of a set of size n is known as the subfactorial of n or the n-th derangement number or n-th de Montmort number. Notations for subfactorials in common use include !n, Dn, dn, or n¡. For n > 0, the subfactorial !n equals the nearest integer to n!/e, where n! denotes the factorial of n and e is Euler's number. (en) Konbinatorian, nahasmena multzo bateko elementuen permutazio bat da, non inongo elementurik ez dagoen bere jatorrizko kokapenean, hau da, nahasmena gabeko permutazio bat da. Adibidez, bedi ABCD multzo ordenatua, multzoko nahasmen guztiak zerrenda honetan agertzen direnak dira: BADC, BCDA, BDAC,CADB, CDAB, CDBA,DABC, DCAB, DCBA. Nahasmenen ebazkizuna elementu kopuru bati dagozkion nahasmenen kopurua zenbatzean datza. n elementuko multzo batean dauden nahasmenen kopurua n zenbakiaren da. (eu) En mathématiques, le problème des rencontres, ou problème de Montmort, ou encore problème des chapeaux, consiste à déterminer la probabilité que, n jetons numérotés de 1 à n ayant été mis au hasard dans des cases elles-mêmes numérotées de 1 à n, aucun jeton ne soit à sa place (ou celle de l'évènement contraire). De façon plus savante, c'est la recherche de la probabilité qu'une permutation prise au hasard soit un dérangement, c'est-à-dire ne possède pas de « rencontre », autrement dit de point fixe. (fr) In combinatoria vengono dette dismutazioni (o sconvolgimenti, o permutazioni complete) le permutazioni di un insieme che non fissano alcun elemento, ovvero tali che nessuno degli elementi dell'insieme iniziale compaia nella sua posizione originaria. Formalmente, se le permutazioni di un insieme X sono le funzioni biiettive , le dismutazioni di X sono le funzioni biiettive tali che . Si verifica facilmente che non esiste alcuna dismutazione per un insieme di un solo elemento, ne esiste 1 per un insieme di 2 elementi, 2 per un insieme di 3 elementi, 9 per uno di 4 elementi... (it) In de combinatoriek, een deelgebied van de wiskunde, is een derangement (van Frans: déranger, verstoren) een permutatie van de elementen van een verzameling waarbij geen van de elementen op z'n plaats blijft. Een derangement is dus een permutatie zonder dekpunt. Het aantal mogelijke derangementen van elementen is gedefinieerd als de subfaculteit van . Men noteert dit aantal ook als of en spreekt van derangementgetal of montmortgetal. Tot nu toe is er geen standaard notatie voor de subfaculteit; ook de notatie ¡ wordt wel gebruikt in plaats van . (nl) В комбінаториці безладом називається перестановка без нерухомих точок, тобто жодний елемент не залишається на початковому місці. Число безладів множини з n елементів, зазвичай позначається Dn, dn, або !n, і називається «числом безладів» або «числом Монмора». (Ці числа узагальнюються числами, що відповідають числу зустрічей.) Функція субфакторіал (не плутайте з факторіалом n!) ставить у відповідність числу n число !n. Не існує стандартного позначення для субфакторіалу. Інколи позначають n¡ замість !n. (uk) Inom matematiken är ett derangemang eller derangement, en permutation utan fixpunkter på en mängd. Med andra ord är permutationen ett derangemang, om σ(x) inte är lika med x för något enda x i M. Om M är en ändlig mängd av storlek n, så är antalet derangemang på M för n = 1, 2, 3, 4, 5, 6, blir denna summa respektive 0, 1, 2, 9, 44, 265. Summan kan även beräknas rekursivt med formeln: , vilka tal kallas för De Montmort-tal. En ofta förekommande sannolikhetsteoretisk formulering av detta illustreras av följande berättelse, eller av någon av variant av den: (sv) |
| rdfs:label | Desarranjament (ca) Derangement (en) Fixpunktfreie Permutation (de) Nahasmen (konbinatoria) (eu) Problème des rencontres (fr) Dismutazione (matematica) (it) 完全順列 (ja) 완전순열 (ko) Derangement (nl) Nieporządek (pl) Desarranjo (pt) Беспорядок (перестановка) (ru) 错排问题 (zh) Безлад (перестановка) (uk) Derangemang (sv) |
| owl:sameAs | dbpedia-fr:Derangement freebase:Derangement wikidata:Derangement http://am.dbpedia.org/resource/ትርምስ dbpedia-ca:Derangement dbpedia-de:Derangement dbpedia-et:Derangement dbpedia-eu:Derangement dbpedia-fa:Derangement dbpedia-he:Derangement http://hi.dbpedia.org/resource/अपविन्यास dbpedia-it:Derangement dbpedia-ja:Derangement dbpedia-ka:Derangement dbpedia-ko:Derangement dbpedia-nl:Derangement dbpedia-pl:Derangement dbpedia-pt:Derangement dbpedia-ru:Derangement dbpedia-sk:Derangement dbpedia-sv:Derangement http://ta.dbpedia.org/resource/நிலைத்தபுள்ளிகளற்ற_வரிசைமாற்றம் dbpedia-uk:Derangement dbpedia-zh:Derangement https://global.dbpedia.org/id/FkjX |
| prov:wasDerivedFrom | wikipedia-en:Derangement?oldid=1122558919&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Complex_plot_for_derangement_real_between_-1_to_11.png wiki-commons:Special:FilePath/Derangement4.png wiki-commons:Special:FilePath/N!_v_!n.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Derangement |
| is dbo:wikiPageRedirects of | dbr:Hat-check_problem dbr:Derangements dbr:Sub-factorial dbr:Subfactorial |
| is dbo:wikiPageWikiLink of | dbr:Anna_Lubiw dbr:List_of_integer_sequences dbr:List_of_mathematical_symbols_by_subject dbr:Permutation dbr:Rencontres_numbers dbr:Index_of_combinatorics_articles dbr:List_of_permutation_topics dbr:List_of_representations_of_e dbr:Pearls_in_Graph_Theory dbr:Random_permutation_statistics dbr:!_(disambiguation) dbr:Mathematical_constant dbr:Mathematical_object dbr:Empty_set dbr:Frustration_(solitaire) dbr:Deranged dbr:Permanent_(mathematics) dbr:Advanced_Encryption_Standard dbr:44_(number) dbr:E_(mathematical_constant) dbr:Exponential_distribution dbr:Cayley's_mousetrap dbr:Glossary_of_order_theory dbr:Holonomic_function dbr:Sally_Cockburn dbr:Pierre_Remond_de_Montmort dbr:Inclusion–exclusion_principle dbr:Factorial dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Rook_polynomial dbr:William_Allen_Whitworth dbr:Hat-check_problem dbr:Derangements dbr:Sub-factorial dbr:Subfactorial |
| is foaf:primaryTopic of | wikipedia-en:Derangement |
