Nahasmen (konbinatoria)

Wikipedia(e)tik
Hona jo: nabigazioa, Bilatu

Konbinatorian, nahasmena multzo bateko elementuen permutazio bat da, non inongo elementurik ez dagoen bere jatorrizko kokapenean, hau da, nahasmena puntu finkorik 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 azpifaktoriala da.

Nahasmen partzialak ere badaude, non zenbait puntu finko edo kointzidentzia onartzen den. Nahasmen partzialen kopuruak zenbatzen dituzten formulak kointzidentzia zenbakiak 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.

Nahasmenen kopurua[aldatu | aldatu iturburu kodea]

n elementuko multzo baterako, nahasmen edo puntu finkorik gabeko permutazioen kopurua honela kalkulatzen da, azpifaktorialaren ikurrez ere irudika daitekeela:

d_n = !n = n! \sum_{i=0}^n \frac{(-1)^i}{i!}

Horrela, n=0-rekin hasita, nahasmenen kopuru hauek ditugu ondoz ondoko elementu kopuruetarako:

1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, ...