je ne suis pas d'accord avec la fonction donnée dans l'exercice 1.11 (Chapitre 1 de Galois Theory, Ian Stewart)
ennoncé:
Let P(n) be the number of way to arrange n zeros and ones in a row,
given that ones occur in group of three or more.
Show that P(n)=2*P(n-1) - P(n-2) + P(n-4)
il me restait seulement cet exercice du chapitre 1 , que je n'avais pas su resoudre auparavant.
Pour moi cette formule est fausse, mais peut etre ais-je mal compris la question ?
moi je trouve la formule suivante, qui elle est generale quelque soit p>=2 (petit p =nombre de 1 consecutifs)
si n<=2*p alors P(n)=2^(n-p)*(1 + (n-p)/2) (on ne peut trouver 2 sequences de >= p bits dupliquées dans un meme mot tant que n<=2*p)
si n> 2*p alors P(n)=2*P(n-1,p) - P(n-p-1,p) + 2^(n-p-1).
je joints un lien sur un fichier GoogleDoc qui tente d'expliquer mon raisonnement pour les deux formules.
ais je le droit de l'appeler preuve ? (pour moi cela en est une), mais elle n'utilise pas l'algebre mais un
"raisonnement d'analyse Graphique " sur la structure des mots binaires.
ou dois je appeler la formule simple conjecture ? j'ai tenter de montrer mon raisonnement pour
quelque cas S(n,p) je prefere l'appeler S(n,p) plutôt que P(n,p).
je me demande si l'utilisation des formule de combinatoires ne permettrait pas une preuve plus elegante.
Preuve Graphique
ci dessous le code Python que j'ai utilisé pour verifier. Je l'utilise dans la VM sageMath.
j'ai trouvé cette fonction, en raisonnant sur la structure du fichier créé par la fonction Python:
writeBinPowFile(p,fname), elle se trouve dans le code joint ci dessous.
code :
- Code: Tout sélectionner
import numpy
from matplotlib import pyplot
def bitLen(n):
length = 0
while (n):
n >>= 1
length += 1
return(length)
def CountContiguousPacquet(n):
# this function return a list of length P_n if P_n packets
# and the value in the list is the length of differents packets
#example:CountContiguousPacquet(int('110000110011101',2))
#return [1, 3, 2, 2]
count=0
pA=[ ]
for i in range(0, bitLen(n)+1):
if n & 1 :
count+=1
else:
if count > 0 :
pA.append(count)
count=0
n >>= 1
return(pA)
def ContiguousPacquetSup(pA,p):
# this function count the number of packet >=p
# in the list pA
# example pA=[1, 3, 2, 2]
count=0
#print "pA:",pA
for element in pA:
if element >= p :
#print element
count+=1
return(count)
def writeBinPowFile(p,fname):
# fill up a text file with binary string 0 to 2^p - 1
NbMax=2^p
with open(fname+"2p"+ str(p)+".txt", "w") as text_file:
for nb in range(0, NbMax, 1):
text_file.write(format(nb, 'b').zfill(p)+'\n') # base 2
#print format(nb, 'b').zfill(10)
return ("Done")
#writeBinPowFile(8,"toto")
#forget()
#print "count:",CountContiguousPacquet(int('110000110011101',2))
#r=ContiguousPacquetSup(CountContiguousPacquet(int('110000110011101',2)),4)
#print "count:",CountContiguousPacquet(int('110000110011101',2))
#r=ContiguousPacquetSup(CountContiguousPacquet(int('110000110011101',2)),4)
count=0
# this list count all sequence >= p of contiguous bits (could have x sequence >=p in the same word)
tabCount=[]
# this list count all word of length n with at least a sequence >= p of contiguous bits present in it
tabCountAtLeast=[]
def EffectiveCountSupP():
# this function effectively count the possibles sequences >=p in a word of length n
# it is not a calculation, simply countage
for N in [2^N for N in range(p, Nmax, 1)]:
print N
count=0
countAtLeast=0
n=bitLen(N)-1
for j in range(0,N):
count =count + ContiguousPacquetSup(CountContiguousPacquet(j),p) # count all packet > p in the word n
if ContiguousPacquetSup(CountContiguousPacquet(j),p) > 0 :
countAtLeast+=1 # at least one packet > p in the word n
#print "countAtLeast:", countAtLeast
#print "count:",count," p:",p ," n:",n ," pn2n:",CalcContiguousPacquetSupDup(n,p) ," j:",j," bin j:",bin(j)," proba:",count/2^(n-1)
tabCount.append(count)
tabCountAtLeast.append(countAtLeast)
return (tabCount,tabCountAtLeast)
Nmax=17
p=3
print "p:",p," Count all sequences >= p in all the words of length n: ",p," to ",Nmax-1
tabCount,tabCountAtLeast= EffectiveCountSupP()
print ('effective count all seq >=p, count duplicates in a same word)')
show(tabCount)
print ('effective count, no duplicates')
show(tabCountAtLeast)
# Recursive fonction
def S(n,p):
if n<=2*p:
# first formula below count all sequences of contiguous >=p bits
# if x sequences of contiguous >=p bits in a same word of length n -> increment counter =+x
# it is used when n>= 2*p because it is not possible of finding duplicates when
# number of possible p contiguous 1 in a word of length n
# 2^(n-p) + (sum {0 to (n-p-1)(included)} of 2^(n-p-1)) =2^(n-p)*(1 + (n-p)/2)=n*2^(n-p-1) + 2^(n-p) - p*2^(n-p-1)
return 2^(n-p)*(1 + (n-p)/2)
else:
# second formula below does not count duplicates in the same word in all the possible words of n length
# if x sequences of contiguous >=p bits in a word of length n -> increment du counter =+1
return 2*S(n-1,p) - S(n-p-1,p) + 2^(n-p-1)
sTab=[]
sTabD=[] #derivative Tab
sTabQ=[] #consecutive quotient Tab
sTabP=[] #Probabilities
for n in range (p,Nmax):
sTab.append(S(n,p))
for i in range (0,len(sTab)-1):
sTabD.append(sTab[i+1]-sTab[i])
sTabQ.append(sTab[i+1]/sTab[i])
for i in range (0,len(sTab)):
sTabP.append( sTab[i]/(2^(p+i)) )
print(' JPO Calculation ')
show(sTab)
print(' Derivative ')
show(sTabD)
print(' Quotient ')
show(sTabQ)
print(' Probabilities ')
show(sTabP)
# Ian Stewart Formula
def IanS(n,p):
if n<=2*p:
# first formula below count all sequences of contiguous >=p bits
# if x sequences of contiguous >=p bits in a same word of length n -> increment counter =+x
# it is used when n <= 2*p because it is not possible of finding duplicates when n <= 2*p
# number of possible p contiguous 1 in a word of length n
# 2^(n-p) + (sum {0 to (n-p-1)} of 2^(n-p-1)) =2^(n-p)*(1 + (n-p)/2)
return 2^(n-p)*(1 + (n-p)/2)
else:
# Ian Stewart formula below
return 2*IanS(n-1,p) - IanS(n-2,p) + IanS(n-4,p)
sIanTab=[]
for n in range (p,Nmax):
sIanTab.append(IanS(n,p))
print(' Ian Stewart Calculation')
show(sIanTab)
# show Probabilities S(n,p)/(2^(n))
x = numpy.arange(len(sTabP))
x+=p # start at n=p
yQ = list(map(float, sTabP)) # convert array stabP rational values in float
fig = pyplot.figure()
ax = fig.add_subplot(111)
ax.set_ylim(0,max(yQ))
pyplot.plot(x,yQ)
for i,j in zip(x,yQ):
ax.annotate(str(j),xy=(i,j))
pyplot.ylabel('Probabilities')
pyplot.xlabel('n (word length)')
pyplot.title('S(n,p)/(2^(n)) Versus n') # subplot 211 title
pyplot.show()
# show quotient S(n,p)/S(n-1,p)
x = numpy.arange(len(sTabQ))
x+=p # start at n=p
#yD = sTabD
yQ = sTabQ
fig = pyplot.figure()
ax = fig.add_subplot(111)
ax.set_ylim(1,max(yQ))
#pyplot.plot(x,yD)
pyplot.plot(x,yQ)
#for i,j in zip(x,yD):
# ax.annotate(str(j),xy=(i,j))
for i,j in zip(x,yQ):
ax.annotate(str(j),xy=(i,j))
pyplot.ylabel('S(n,p)/S(n-1,p)')
pyplot.xlabel('n (word length)')
pyplot.title('S(n,p)/S(n-1,p) Versus n') # subplot 211 title
pyplot.show()
par