En lineær kæde er lavet af 20 identiske links. Hvert link kan laves i 7 forskellige farver. Hvor mange fysisk forskellige kæder er der?

En lineær kæde er lavet af 20 identiske links. Hvert link kan laves i 7 forskellige farver. Hvor mange fysisk forskellige kæder er der?
Anonim

For hver af 20 links er der 7 valg, hver gang valget er uafhængigt af tidligere valg, så vi kan tage produktet.

Samlet antal valg = #7*7*7…*7 = = 7^(20)#

Men da kæden kan vendes, skal vi tælle forskellige sekvenser.

For det første tæller vi antallet af symmetriske sekvenser: dvs. sidste 10 links tager spejlbilledet af de første 10 links.

Antal symmetriske sekvenser = antal måder, så vælg først 10 links = #7^(10)#

Bortset fra disse symmetriske sekvenser kan de ikke-symmetriske sekvenser omdannes for at producere en ny kæde. Det betyder, at kun halvdelen af ikke-symmetriske sekvenser er unikke.

Antal unikke sekvenser = (Antal ikke-symmetriske) / 2 + Antal symmetriske sekvenser

#= (7^20 - 7^10)/2 + 7^10 = 39896133290043625#