Hjälp med denna (mängdlära?)

Bestäm antalet 6-siffriga tal som inte har följden 17. T ex 4713, 1572 är tillålna 4-siffriga tal men 1723,3175,0254 är inte tillåtna.

so far så fattar jaga tt ngt ska vara:

17****,*17***,**17**,...,****17 där får man antalet det med 17 en gång i sig men sen finns det ju 1717**,17*17* och 17**17 också men även 171717..

sen stopp

sexsiffriga tal kan skrivas på (10^7-1) sätt, dra nu bort överflödet

Antalet sexsiffriga tal =9*10^5
Du måste minska alla som har ”17” minst en gång,
Sedan ska du plussa alla som har ”17” minst två gånger,
och till slut minska alla som har ”17” tre gånger.
Först de som har ”17” minst en gång. Först de som har ”17 i början.
17**** -> 10^4 gånger
Andra tillsammans -> 4*9*10^3
De som har ”17” två gånger, första i början.
C(4,2) *10^2
De som har ”17” två gånger men inte i början.
9*C(5,2)*10
De som har ”17” tre gånger, de är bara en 171717.
Antalet som frågades:
9*10^5-(10^4+4*9*10^3)+( C(4,2) *10^2+ 9*C(5,2)*10)-1=855499

Blir det inte 854569?

Det finns 999999-99999 = 900000 sexsiffriga tal. För varje tal du räknat upp, ****17....17**** finns ett antal sätt att välja ****.

Beräkna antalet tal som innehåller 17 minst en gång.

För ****17, ***17*,**17**, *17*** finns 9000 sätt vardera (9999-999, första siffran x kan inte vara 0, då är det inte ett sexsiffrigt tal).
För 17**** 10000 sätt.

Det blir totalt 4*9000+10000=46000 tal.

Men i denna mängd finns dubletter som innehåller 17 flera gånger och alltså räknas dubbelt: *17*17 *1717*, **1717 samt 1717**, 17*17*, 17**17.
För de tre första kan ** väljas på 99-9 = 90 sätt vardera = 270 dubletter.
För de tre senare kan ** väljas på 100 sätt vardera = 300 dubletter.

Dessutom finns ett tal, 171717, som räknas tre gånger i "grundräkningen" (som 17****, **17** och ****17), alltså skall 2 av dem räknas bort.
Men samma tal finns även med tre gånger i "dubletterna" (**1717, 17**17 och 1717**) och ska alltså läggas till tre gånger.

ANtalet tal som inntehåller 17 blir då 46000-270-300-2+3=45431

Svaret borde bli 900000-45431=854569.

Det blev fel, men som tur svarade Piggekott rätt.
Jag skulle ha skrivit.
9*10^5-(10^4+4*9*10^3)+3 *10^2+ 9*3*10)-1=854569
1 och 7 kan inte väljas hur som helst, som jag hade räknat tidigare ovanför, utan måste vara "17".

Hur hade man gjort om det var antalet 7 siffriga tal då?

import string
count=0
for i in range (1000000,10000000):
x=str(i)
if (x.find('17')>=0):
count=count+1
print 9000000-count

Woot?

Jag försöker igen.
Antalet sjusiffriga tal =9*10^6
Du måste minska alla som har ”17” minst en gång,
Sedan ska du plussa alla som har ”17” minst två gånger,
och till slut minska alla som har ”17” tre gånger.
De som har ”17” minst en gång. Först de som har ”17” i början.
17***** -> 10^5 gånger
Andra tillsammans -> 5*9*10^4
De som har ”17” två gånger, första ”17” i början.
C(4,1) *10^3
De som har ”17” två gånger men inte i början.
9*C(4,2)*10^2
De som har ”17” tre gånger, den första i början.
3*10
Och 9 där ingen är i början.
Antalet som frågades:
9*10^6- 10^5-5*9*10^4 + C(4,1) *10^3+9*C(4,2)*10^2-39)=
8459361
Hoppas någon kontrollerar resultatet.

8459361 stämmer.


Det var en programsnutt i Python som räknar ut antalet. Något liknande funkar i de flesta språk. Fast börjar man komma upp i fler siffror tar det lång tid...

Ska man räkna ut flera på det där sättet så kan det vara lämpligt att skapa en rekursionsformel att använda sig av. Låt a_n vara antalet n siffriga tal som inte innehåller 17 och inte slutar på 1, samt låt b_n vara antalet som slutar på 1. Vi söker alltså vad a_n + b_n är. Nu är a_1 = 8 och b_1 = 1, samt att man kan inse att

a_{n + 1} = 9a_n + 8b_n
b_{n + 1} = a_n + b_n

Denna rekursion inser man helt enkelt genom att tänka på vilka tal man kan lägga på i slutet av de tal man redan har (lite luddigt formulerat kanske, men aja). Detta kan man vidare göra så att man låter A vara matrisen [9 8; 1 1] och v_n = [a_n; b_n], då kan man skriva rekursionen som

v_{n + 1} = Av_n

och utvecklar man denna rekursion så får man att

v_{n + 1} = Av_n = A^2 v_{n - 1} = A^(n - 1) v_1 = A^n [8; 1]

så för att få reda på hur många n siffriga tal det finns som inte innhåller 17 så ska man alltså beräkna vad [1 1] v_n = [1 1] A^(n - 1) [8; 1] är och det enda som egentligen blir problemet är att beräkna vad A^(n - 1) är. Detta kan man göra genom att diagonalisera A och på så sätt få fram en sluten formel för antalet n siffriga tal som inte innehåller 17 om man nu vill det. Men aja, det blir helt enkelt för jobbigt att göra så använder man sig av något program för att beräkna detta så får man att antalet 7 siffriga tal blir som redan nämnts 8459361 stycken.

Insåg att det inte blev så klurig att finna en exakt lösning på problemet. En sluten formel är

a_n = (1/2 + 1/√(6)) * (5 + 2√(6))^n + (1/2 - 1/√(6)) * (5 - 2√(6))^n

med reservation för att jag tänkt fel och lämnar det som övning att komma fram till det här (jag använde mig av min tidigare lösning).