Telefonnummer (matematik)

Den här artikeln handlar om heltalssekvensen. För telefonens nätverksadress, se Telefonnummer .

Den fullständiga grafen K ₄ har tio matchningar, motsvarande värdet T (4) = 10 för det fjärde telefonnumret.

I matematik bildar telefonnumren eller involutionstalen en sekvens av heltal som räknar hur n personer kan kopplas samman genom telefonsamtal från person till person. Dessa siffror beskriver också antalet matchningar ( Hosoya-indexet ) för en komplett graf på n hörn, antalet permutationer på n element som är involutioner , summan av absoluta värden av koefficienterna för de hermitiska polynomen , antalet unga standardtablåer med n celler, och summan av graderna av de irreducibla representationerna av den symmetriska gruppen . Involutionstal studerades första gången 1800 av Heinrich August Rothe , som gav en återfallsekvation med vilken de kan beräknas, vilket ger värdena (med början från n = 0 )

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... (sekvens A000085 i OEIS ).

Ansökningar

John Riordan ger följande förklaring till dessa nummer: anta att n personer prenumererar på en telefontjänst som kan koppla ihop två av dem genom ett samtal, men inte kan ringa ett enda samtal som kopplar samman fler än två personer. Hur många olika anslutningsmönster är möjliga? Till exempel, med tre abonnenter, finns det tre sätt att bilda ett enda telefonsamtal, och ett ytterligare mönster där inga samtal görs, för totalt fyra mönster. Av denna anledning kallas siffrorna som räknar hur många mönster som är möjliga ibland telefonnumren.

Varje mönster av parvisa kopplingar mellan n personer definierar en involution , en permutation av människorna som är dess egen invers. I denna permutation byts var och en av två personer som ringer till varandra, och de personer som inte är inblandade i samtalen förblir fasta på plats. Omvänt har varje möjlig involution formen av en uppsättning parvisa byten av denna typ. Därför räknar telefonnumren även involutioner. Problemet med att räkna involutioner var det ursprungliga kombinatoriska uppräkningsproblemet som studerades av Rothe 1800 och dessa tal har också kallats involutionstal.

I grafteorin kallas en delmängd av kanterna på en graf som vidrör varje vertex högst en gång en matchning . Att räkna matchningarna av en given graf är viktigt i kemisk grafteori , där graferna modellerar molekyler och antalet matchningar är Hosoya-indexet . Det största möjliga Hosoya-indexet för en n -vertexgraf ges av de fullständiga graferna , för vilka alla mönster av parvisa anslutningar är möjliga; Hosoya-indexet för en komplett graf på n hörn är alltså detsamma som det n :te telefonnumret.

En vanlig Young-tablå

Ett Ferrers-diagram är en geometrisk form som bildas av en samling av n kvadrater i planet, grupperade i en polyomino med en horisontell övre kant, en vertikal vänsterkant och en enda monoton kedja av kanter från övre högra till vänster nere. En standard Young-tablå bildas genom att siffrorna från 1 till n placeras i dessa rutor på ett sådant sätt att talen ökar från vänster till höger och uppifrån och ned genom hela tablåen. Enligt Robinson-Schensted-korrespondensen motsvarar permutationer en-mot-en med ordnade par av standard Young-tablåer . Att invertera en permutation motsvarar att byta de två tablåerna, och så motsvarar de självinversa permutationerna enstaka tablåer, parade med sig själva. Därmed räknar telefonnumren även antalet Unga tablåer med n rutor. I representationsteorin motsvarar Ferrers-diagrammen de irreducibla representationerna av den symmetriska gruppen av permutationer, och Young-tablåerna med en given form utgör grunden för den irreducibla representationen med den formen. Därför ger telefonnumren summan av graderna av de irreducerbara representationerna.

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

En diagonalsymmetrisk icke-attackerande placering av åtta torn på ett schackbräde

I schackets matematik räknar telefonnumren antalet sätt att placera n torn på ett n × n schackbräde på ett sådant sätt att inga två torn angriper varandra (det så kallade åtta torkenpusslet ) , och på ett sådant sätt att torkens konfiguration är symmetrisk under en diagonal reflektion av brädan. Via Pólya uppräkningssatsen utgör dessa tal en av nyckelkomponenterna i en formel för det totala antalet "väsentligt olika" konfigurationer av n ömsesidigt icke-attackerande torn, där två konfigurationer räknas som väsentligt olika om det inte finns någon symmetri av tavla som tar det ena i det andra.

Matematiska egenskaper

Upprepning

Telefonnumren uppfyller repetitionsrelationen

$$T(n)=T(n-1)+(n-1)T(n-2) ,$$

publicerades första gången 1800 av Heinrich August Rothe , med vilken de lätt kan beräknas. Ett sätt att förklara detta återkommande är att dela upp T ( n ) -anslutningsmönstren för de n abonnenterna till ett telefonsystem i de mönster där den första personen inte ringer någon annan, och mönstren där den första personen ringer ett samtal . Det finns T ( n − 1) anslutningsmönster där den första personen kopplas bort, vilket förklarar den första termen av återkommande. Om den första personen är kopplad till någon finns det n − 1 val för den personen, och T ( n − 2) anslutningsmönster för de återstående n − 2 personerna, vilket förklarar den andra termen av återkommande.

Summeringsformel och approximation

Telefonnumren kan uttryckas exakt som en summering

$$T(n)=\summa _{k=0}^{\lfloor n/2\rfloor }{\binom {n}{2k}}(2k-1)!!=\summa _{k= 0}^{\lvåning n/2\rvåning }{\frac {n!}{2^{k}(n-2k)!k!}}.$$

I varje term av den första summan ger $k$ antalet matchade par, binomialkoefficienten ( $\displaystyle {\tbinom {n}{2k}}}$ räknar antalet sätt att välja de $2k$ elementen som ska matchas, och den dubbla faktorn

$$(2k-1)!!={\frac {(2k)!}{2^{k}\,k!}}$$

är produkten av de udda heltal upp till dess argument och räknar antalet sätt att helt matcha de 2 k valda elementen. Det följer av summeringsformeln och Stirlings approximation att, asymptotiskt ,

$$T(n)\sim \left({\frac {n}{e}}\right)^{n/2}{\frac {e^{\sqrt {n}}}{(4e)^ {1/4}}}\,.$$

Genererande funktion

Telefonnumrens exponentiellt genererande funktion är

$$\sum _{n=0}^{\infty }{\frac {T(n)x^{n}}{n!}}=\exp \left({\frac {x^{2} }{2}}+x\höger).$$

Med andra ord kan telefonnumren läsas av som koefficienterna för Taylor-serien av exp( x ² /2 + x ) , och det n: te telefonnumret är värdet noll av den n :te derivatan av denna funktion. Denna funktion är nära besläktad med den exponentiella genererande funktionen för Hermite-polynomen , som är de matchande polynomen i de fullständiga graferna. Summan av absoluta värden av koefficienterna för det n :e (probabilistens) hermitpolynom är det n :te telefonnumret, och telefonnumren kan också realiseras som vissa specialvärden för de hermitiska polynomen:

$$T(n)={\frac {{\mathit {He}}_{n}(i)}{i^{n}}}.$$

Primära faktorer

För stora värden på n är det n :te telefonnumret delbart med en stor potens av två , 2 ^{n /4 + O (1)} . Närmare bestämt är den 2-adiska ordningen (antalet faktorer av två i primtalsfaktoriseringen ) för T (4 k ) och för T (4 k + 1) k ; för T (4 k + 2) är det k + 1 och för T (4 k + 3) är det k + 2 .

För vilket primtal p som helst kan man testa om det finns ett telefonnummer som är delbart med p genom att beräkna upprepningen för sekvensen av telefonnummer, modulo p , tills man antingen når noll eller detekterar en cykel . De primtal som delar minst ett telefonnummer är

2, 5, 13, 19, 23, 29, 31, 43, 53, 59, ... (sekvens A264737 i OEIS )

De udda primtal i denna sekvens har kallats ineffektiva . Var och en av dem delar upp oändligt många telefonnummer.