Anzahl der Vereinbarungen

stimmen
4

Angenommen , wir haben n Elemente, ein 1 , a 2 , ..., a n , die in einem Kreis angeordnet sind . Das heißt, ein 2 ist zwischen einer 1 und einer 3 , a 3 ist zwischen einem 2 und einem 4 , a n ist zwischen einem n -1 und eine 1 , und so weiter.

Jedes Element kann nehmen den Wert von entweder 1 oder 0 zwei Anordnungen unterschiedlich sind , wenn es entsprechend einem i unterscheiden ‚s , deren Werte. Wenn zum Beispiel n = 3 ist , (1, 0, 0) und (0, 1, 0) , sind verschiedene Anordnungen, auch wenn sie unter Rotation oder Reflexion isomorph sein können.

Da es n Elemente, von denen jedes zwei Werte annehmen kann, ist die Gesamtzahl der Anordnungen 2 n .

Hier ist die Frage:

Wie viele Anordnungen möglich sind, so dass keine zwei benachbarten Elemente haben beide den Wert 1? Wenn es hilft, sollten Sie nur Fälle , in denen n > 3.

Ich frage hier aus mehreren Gründen:

  1. Diese entstand, während ich eine Programmierproblemlösung
  2. Es klingt wie das Problem profitieren von der Booleschen Logik / Bit-Arithmetik
  3. Vielleicht gibt es keine geschlossene Lösung.
Veröffentlicht am 10/12/2008 um 00:41
quelle vom benutzer
In anderen Sprachen...                            


4 antworten

stimmen
10

Lassen Sie uns zuerst fragen, die Frage „wie viele 0-1 Sequenzen der Länge n gibt es keine zwei aufeinander folgenden 1s?“ Lassen Sie die Antwort A (n) sein. Wir haben A (0) = 1 (leere Sequenz), A (1) = 2 ( "0" und "1") und A (2) = 3 ( "00", "01" und "10", aber nicht "11").

Um es einfacher , eine Wiederholung zu schreiben, werden wir eine (n) als die Summe von zwei Zahlen berechnet:
b (n), die Anzahl solcher Sequenzen , die mit einer 0 zu beenden, und
C (n), die Anzahl solcher Sequenzen , die mit einem 1 zu beenden.

Dann B (n) = A (n-1) (nehmen eine solche Sequenz der Länge n-1, und Anhängen A 0)
und C (n) = B (n-1) (denn wenn man eine 1 an der Position n , müssen Sie ein 0 bei n-1 haben.)
Die A gibt (n) = B (n) + C (n) = A (n-1) + B (n-1) A (n-1) = + A (n-2). Nun sollte es bekannt sein :-)

A (n) ist einfach die Fibonacci - Zahl F n + 2 , wo die Fibonacci - Sequenz definiert ist durch
F 0 = 0, F 1 = 1 und F n + 2 = F n + 1 + F n für n ≥ 0.

Nun zu Ihrer Frage. Wir werden die Anzahl von Anordnungen mit einer Zählung 1 = 0 und 1 = 1 getrennt. Für ersteres a 2 ... a n kann eine beliebige Sequenz überhaupt sein (ohne konsekutive 1s), so ist die Zahl A (n-1) = F n + 1 . Für letztere wir haben müssen 2 = 0, und dann wurde eine 3 ... a n ist eine beliebige Sequenz , ohne aufeinanderfolgende 1en , die mit einem 0 endet , also B (n-2) = A (n-3) = F N- 1 .

So ist die Antwort F n + 1 + F n-1 .

Eigentlich kann man sogar noch weiter gehen als diese Antwort. Beachten Sie, dass , wenn Sie rufen Sie die Antwort als
G (n) = F n + 1 + F n-1 , dann
G (n + 1) = F n + 2 + F n und
G (n + 2) = F n + 3 + F n + 1 , so dass auch G (n) erfüllt die gleiche wie die Rezidiv Fibonacci - Folge! [Eigentlich jede lineare Kombination von Fibonacci-ähnlichen Sequenzen die gleiche Wiederholung erfüllen, so dass alle es ist nicht so überraschend.] So ein anderer Weg , um die Antworten zu berechnen wäre mit:
G (2) = 3
G (3) = 4
G ( n) = G (n-1) + G (n-2) für n ≥ 4.

Und nun können Sie auch die Verwendung geschlossene Form F n = (α nn ) / (α-β) (wobei α und β ist (1 ± √5) / 2, die Wurzeln von x 2 -x-1 = 0), erhalten
G (n) = ((1 + √5) / 2) n + ((1-√5) / 2) n .
[Sie können den zweiten Term ignorieren , weil es auf 0 für große n ganz in der Nähe ist, in der Tat G (n) ist die nächste ganze Zahl zu ((1 + √5) / 2) n für alle n ≥ 2.]

Beantwortet am 10/12/2008 um 01:00
quelle vom benutzer

stimmen
1

Ich beschloss, ein kleines Skript zerhacken, um es auszuprobieren:

#!/usr/bin/python
import sys

# thx google 
bstr_pos = lambda n: n>0 and bstr_pos(n>>1)+str(n&1) or ""

def arrangements(n):
    count = 0
    for v in range(0, pow(2,n)-1):
        bin = bstr_pos(v).rjust(n, '0')
        if not ( bin.find("11")!=-1 or ( bin[0]=='1' and bin[-1]=='1' ) ):
            count += 1
            print bin
    print "Total = " + str(count)

arrangements(int(sys.argv[1]))

Das Ausführen dieses für 5, gab mir insgesamt 11 Möglichkeiten mit 00000, 00001, 00010, 00100, 00101, 01000, 01001, 01010, 10000, 10010, 10100.

PS - Entschuldigen Sie das nicht () in dem obigen Code.

Beantwortet am 10/12/2008 um 01:14
quelle vom benutzer

stimmen
0

Dieses Problem ist sehr ähnlich wie Zeckendorf Darstellungen . Ich kann nicht eine offensichtliche Art und Weise finde Zeckendorf Theorem aufgrund der Zirkularität Einschränkung, aber die Fibonacci - Zahlen sind offensichtlich sehr weit verbreitet in diesem Problem anzuwenden.

Beantwortet am 10/12/2008 um 01:38
quelle vom benutzer

stimmen
0

Werfen meiner naiven Skript in die Mischung. Reichlich Gelegenheit für Teilergebnisse zwischenspeichern, aber es lief schnell genug für kleine n, dass ich nicht gestört.

def arcCombinations(n, lastDigitMustBeZero):
    """Takes the length of the remaining arc of the circle, and computes
       the number of legal combinations.
       The last digit may be restricted to 0 (because the first digit is a 1)"""

    if n == 1: 
        if lastDigitMustBeZero:
            return 1 # only legal answer is 0
        else:
            return 2 # could be 1 or 0.
    elif n == 2:
        if lastDigitMustBeZero:
            return 2 # could be 00 or 10
        else:
            return 3 # could be 10, 01 or 00
    else:
        # Could be a 1, in which case next item is a zero.
        return (
            arcCombinations(n-2, lastDigitMustBeZero) # If it starts 10
            + arcCombinations(n-1, lastDigitMustBeZero) # If it starts 0
            )

def circleCombinations(n):
    """Computes the number of legal combinations for a given circle size."""

    # Handle case where it starts with 0 or with 1.
    total = (
            arcCombinations(n-1,True) # Number of combinations where first digit is a 1.
            +
            arcCombinations(n-1,False) # Number of combinations where first digit is a 0.
        )
    return total


print circleCombinations(13)
Beantwortet am 10/12/2008 um 01:16
quelle vom benutzer

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more