Задача по математика!

[Гост]

Един шеф пише всеки ден по 8 писма и ги номерира в реда 1, 2, 3,..., 8. Когато напише писко, той го поставя най-отгоре в една кутия. Когато секретарката му е свободна, тя взема най-горното писмо от кутията и го печати. Понякога секретарката успява да отпечати писмото преди шефът да постави следващото, а понякога той успява да постави едно или повече писма през това време. Секретарката винаги успява да отпечати всички писма до края на работния си ден.
Една пермутация на числата от 1 до 8 ще наричаме печатна, ако е възможно писмата да бъдат отпечатени в този ред. Колко са всички печатни пермутации?

[ptj]

[tex]P(n)=2.P(n-1)\Rightarrow P(8)=2^7[/tex]

[inveidar]

[tex]P(n)=2.P(n-1)\Rightarrow P(8)=2^7[/tex]

viewtopic.php?f=34&t=16989&p=71462&hilit=%D0%95%D0%B4%D0%B8%D0%BD+%D1%88%D0%B5%D1%84+%D0%BF%D0%B8%D1%88%D0%B5+%D0%B2%D1%81%D0%B5%D0%BA%D0%B8+%D0%B4%D0%B5%D0%BD+%D0%BF%D0%BE+8+%D0%BF%D0%B8%D1%81%D0%BC%D0%B0#p71462

[drago]

Я, тази задача отново. Все си мислих, че някой е сгрешил като я сложил в този раздел, но за втори път, явно образованието е напреднало и в 6-ти се учат числа на Каталан. Не че съм против, но има много по-фундаментални неща дето трябва да предшестват това.

[inveidar]

Я, тази задача отново. Все си мислих, че някой е сгрешил като я сложил в този раздел, но за втори път, явно образованието е напреднало и в 6-ти се учат числа на Каталан. Не че съм против, но има много по-фундаментални неща дето трябва да предшестват това.

Не, не се учат. Учат се учениците да броят различни неща по различен начин.

[drago]

Аха, напомня ми за Остап Бендер, който за да спечели някой лев(рубла), се направил на известен гросмайстор и дал сенас по шах на едновременна игра на 30 дъски.(Остап нищо не разбирал от шах). След първите пет хода се оказало, че на една част от дъските играе сициалианска партия, на друга- Испанска, на трета- дамски гамбит..., но Остап въобще си нямал и представа за това!

Та като си мисля, вероятно най-достъпно решение за 6-ти клас е следното:
Нека писмата са [tex]n[/tex] на брой. Да означим с [tex]c_n[/tex] броя на печатните комбинации. Нека последното писмо, което взема секретарката е [tex]k[/tex]-тото, [tex]1\leq k \leq n[/tex]. Значи ситуацията е следната, когато шефа постави [tex]k[/tex]- тото писмо, секретарката е взела вече всичко до [tex]k-1[/tex]-вото вкл. и кутията е празна. След което, все едно сме в начална ситуация, но с [tex]n-k[/tex] писма. Така, че броя на тези възможности са [tex]c_{k-1} \cdot c_{n-k}[/tex]. Остава да сумираме по [tex]k[/tex] и получаваме рекурентната формула:

[tex]c_n = \sum_{k=1}^n c_{k-1}c_{n-k}[/tex].

Това е известна рекурентна формула за числата на Каталан, но в момента и ние като Остап си нямамe и идея за това. Сега от тук нататък има 3 възможности. Наи-близко до 6-ти клас е, като използваме горното, последователно да намерим [tex]c_2,c_3,\dots,c_8[/tex]. Най-естественото, но не най-елементарното е да се възлолзваме от пораждащи ф-ии и директно да намери на кокло е равно [tex]c_n[/tex]. Най-простото е може би да докажем по индукция, че [tex]c_n=\frac{1}{n+1}\binom{2n}{n}[/tex], но затова трябва да знаем този факт.

Ако някой вижда нещо по-лесно, нека сподели.