Kombinatorikaufgabe

icarus2

Ich versuche gerade folgende Aufgabe zu lösen:
Wieviele Tripel von n-Bitstrings $(x,y,z) \in (\{0,1\}^n)^3$ gibt es, die die Eigenschaft haben, dass sich x und y in k Positionen und y und z in l Positionen unterscheiden?

Meiner erster Lösungsansatz war ${{n}\choose{k}} \cdot {{n}\choose{l}}$ . Aber ich glaube das stimmt nicht, da ich gewisse Tripel mehrfach zähle.
Kann mir jemand erklären wie ich die Aufgabe lösen kann?

Michael E.

Deine Lösung klingt auf den ersten Blick sinnvoll. Welche Tupel glaubst du denn doppelt zu zählen?

icarus2

Michael E. schrieb:

Deine Lösung klingt auf den ersten Blick sinnvoll. Welche Tupel glaubst du denn doppelt zu zählen?

Es war so: Ich habe die Lösung einem Assistenten gezeigt und dieser meinte, dass ich damit gewisse Tripel mehrfach zähle. Ich habe selber aber nicht ganz verstanden warum.
Der Assistent konnte dann die Aufgabe selber nicht lösen und meinte bloss, dass mein Vorschlag wohl falsch sei ^^

Ich probiere mal ein Beispiel.
n=2, k=l=1

Es gibt 4 verschiedene 2-Bit-Tupel. Wenn ich ein bestimmtes Auswähle, dann gibt es 2 verschiedene 2-Bit-Tupel, die sich in genau einem Bit vom ersten unterscheiden.

Für x habe ich 4 Möglichkeiten. Wenn ich ein x ausgewählt habe, kann ich 2 verschiedene y wählen. Wenn ich ein y ausgewählt habe, kann ich 2 verschiedene z wählen. Macht insgesamt 4*2*2 = 16 Möglichkeiten.

Das sind sogar viel mehr, als nach deinem Vorschlag rauskommen. Wenn meine Idee richtig ist, muss man das noch mit n und k und l umschreiben. Wenn ich Unsinn schreibe, würde ich meinen Post wegschmeissen.

Bashar

Kurztest: n=3, k=l=0. IOW drei beliebige Bitstrings der Länge 3 oder auch 9 beliebige Bits: 2^9 = 512. Nach deiner Variante kommt 1 raus.

edit: Das ist übrigens Unsinn. Wer Lust hat kann gerne drüber nachdenken wieso

Michael E.

icarus2: Deine Lösung stimmt für festes x. Du musst, um die Gesamtzahl zu erhalten, noch mit 2^n (= Anzahl Möglichkeiten für x) multiplizieren. Dann klappts auch mit den Kurztests, wenn man sie korrekt durchführt

Michael E.

Ein kurzer dreckiger Code bestätigt das:

def fac(n)
	return 1 if n == 0
	(1..n).inject(&:*)
end

def binom(n, k)
	fac(n) / (fac(k) * fac(n - k))
end

def expected_result(n, k, l)
	2**n * binom(n, k) * binom(n, l)
end

def i_to_bin_s(input, n)
  (0...n).map{|i| ((input / 2**i) % 2).to_s}.reverse.join
end

n = 6
pool = (0...(2**n)).map{|i| i_to_bin_s(i, n)}
tupels = pool.product(pool, pool)
histogram = (0..n).map{|i| Array.new(n+1, 0)}

for tupel in tupels
	diff1 = (0...n).select{|i| tupel[0][i] != tupel[1][i]}.size
	diff2 = (0...n).select{|i| tupel[1][i] != tupel[2][i]}.size
	histogram[diff1][diff2] += 1
end

for k in 0..n
	for l in 0..n
		if histogram[k][l] != expected_result(n, k, l)
			puts "k = #{k}, l = #{l}. expected: #{expected_result(n, k, l)}, real: #{histogram[k][l]}"
		end
	end
end

Es wird kein Fehler ausgegeben. Dein Tutor hat also Unrecht.

icarus2

Dann gibt es also $2^n {{n}\choose{k}} {{n}\choose{l}}$ Möglichkeiten. Ja, das scheint sinnvoll zu sein

Vielen Dank für eure Antworten

einfach:

für y gibt es 2^n Möglichkeiten

Für jeden dieser y-Bitstrings gibt es (n k) Mgl.keiten für x, und (n l) Mgl.keiten für y.

=> 2^n*(n k)*(n l)

Michael E.

Nur der Vollständigkeit halber als Fingerübung: dynamisches Programmieren: f(n,k,l) = 2(f(n-1,k,l) + f(n-1,k,l-1) + f(n-1,k-1,l) + f(n-1,k-1,l-1)).

def fac(n)
	return 1 if n == 0
	(1..n).inject(&:*)
end

def binom(n, k)
	fac(n) / (fac(k) * fac(n - k))
end

def expected_result(n, k, l)
	2**n * binom(n, k) * binom(n, l)
end

n = 20

dynamic = (0..n).map{|i| (0..n).map{|j| Array.new(n+1, 0)}}
dynamic[0][0][0] = 1
def dyn(n, k, l)
	return 0 if k < 0 or l < 0
	dynamic[i][k][l]
end

for i in 1..n
	for k in 0..i
		for l in 0..i
			dynamic[i][k][l] = 2 * (dynamic[i-1][k][l] + dynamic[i-1][k][l-1] + dynamic[i-1][k-1][l] + dynamic[i-1][k-1][l-1])
			if dynamic[i][k][l] != expected_result(i, k, l)
				puts "n = #{i}, k = #{k}, l = #{l}. expected: #{expected_result(i, k, l)}, dynamic: #{dynamic[i][k][l]}"
			end
		end
	end
end

oops:

Für jeden dieser y-Bitstrings gibt es (n k) Mgl.keiten für x, und (n l) Mgl.keiten für z