Задачки по комбинаторике и терверу

[kvit]

Для желающих размять мозги и/или вспомнить студенчество...

задачки по комбинаторике и теории вероятностей

ответы не гуглим, пробуем думать самостоятельно... )))

[kvit]

задача дня

сколькими способами можно замостить дорожку размером 2хN прямоугольными плитками размером 2х1?

[Лис]

сколькими способами
Вот блин.
В тупик сразу же...

[Red]

задача дня

сколькими способами можно замостить дорожку размером 2хN прямоугольными плитками размером 2х1?

Сирениуса зови)
Это его фишка.
Придет , будет у тебя в теме дым коромыслом))
Ссылку ему брось)

[kvit]

@Red, думаю, @Сирениус, не придёт... :D

[kvit]

@Red, кстати, про замощение дорожек вроде тебе по проф. деятельности близко, нет??? давай тоже подключайся... )))

[Сирениус]

Это его фишка.
Леди, ты же во всему прочему инженер-строитель, обязана знать школьную комбинаторику = N!
Вот тебе другая классическая задача, дано:
Колода 52 листа (без джокеров) хорошо перетасованных игральных карт, продемонстрируй мне прям здесь сейчас событие, вероятность наступления которого исчезающе мала, приблизительно равная 8,0658175170818 в степени минус 67 (по Стирлингу).

[Шпилька]

Прогоните меня отсюда?!)))

[kvit]

@Шпилька, привет, зачем, давай тоже думай)))

[kvit]

знать школьную комбинаторику = N!если это ответ на мою задачку, то неверно... проверяется на простейшем случае с N=3, т.е. надо замостить прямоугольник 2х3

N!=3!=1*2*3=6

если плитка стоит вертикально, то один вариант, условно обозначим |||
если две плитки лежат горизонтально, то еще два варианта
=|
|=

итого 3, не 6

если же считать плитки различными (пронумерованными), то 6 дает первый вариант |||, а эти варианты =| , |= также надо поперебрать, итого тоже 3! не получится

[kvit]

задача дня с уточненным условием)))

Сколькими способами можно замостить дорожку размером 2хN прямоугольными плитками размером 2х1?

Дополнение. Плитки считаются неразличимыми, различие может быть только в расположении плитки - вертикально или горизонтально.

[Сирениус]

если это ответ на мою задачку, то неверно...
Не косите, исходные задачи были "сколькими способами можно замостить дорожку", а не прямоугольник. Дорожка выкладывает плиткой в один ряд.

[kvit]

Дорожка выкладывает плиткой в один ряд


без проблем, еще пара уточнений )))


задача дня с уточненными условиями)))

Сколькими способами можно замостить прямоугольник размером 2хN прямоугольными плитками размером 2х1?

Дополнения. Плитки считаются неразличимыми, различие может быть только в расположении плитки - вертикально или горизонтально. Реверсные варианты укладки считаются различными

[Сирениус]

Сколькими способами можно замостить прямоугольник размером 2хN прямоугольными плитками размером 2х1?
Дополнения. Плитки считаются неразличимыми
одним способом.

[kvit]

одним способом.
почему? выше приводил варианты

[kvit]

кстати говоря, можно рассмотреть разные варианты задачи, с учетом реверса и без учета

[kvit]

N=3
вариантов 3
|||
=|
|=

N=4
вариантов 5
||||
=||
|=|
||=
==


а если реверсивные варианты считать одним вариантом, т.е. получающиеся симметрией справа-налево, то для

N=3 будет 2 варианта
а для N=4 - 4 варианта

[Сирениус]

почему?
Потому что исходное условие (Плитки считаются неразличимыми) - плитки не имеют индивидуального отличительного признака. Иными словами: любая выкладка принципиально неотличима от всех возможных остальных.

[kvit]

Потому что исходное условие (Плитки считаются неразличимыми) - плитки не имеют индивидуального отличительного признака. Иными словами: любая выкладка принципиально неотличима от всех возможных остальных.

все верно, плитки - не имеют

положение плитки - имеет значение

различие может быть только в расположении плитки - вертикально или горизонтально.

[Шпилька]

@Шпилька, привет, зачем, давай тоже думай)))
Шутка-минутка?))

[Сирениус]

положение плитки - имеет значение
Конкретно какое?
И сколько еще N- заходов вам потребуется, чтобы наконец научится с первого раз формулировать исходные необходимо и достаточно.

[kvit]

Конкретно какое?в условии всё сказано


И сколько еще N- заходов вам потребуется, чтобы наконец научится с первого раз формулировать исходные необходимо и достаточно.
для вменяемых слушателей достаточно первого варианта... максимум - второго...

[Сирениус]

для вменяемых слушателей достаточно
принять ответ, который удовлетворяет условиям, даже если этот ответ - не соответствует их ожиданию.

[kvit]

принять ответ, который удовлетворяет условиям, даже если этот ответ - не соответствует их ожиданию.
ну, если в кайф давать банальные и тривиальные ответы на банальные и тривиальные постановки - не будем данному явлению препятствовать... ответ принимается, молодец, справился!!! :BB:

подождем ответы от других участников на более сложные постановки...

[Gurd]

Задача, на самом деле, очень интересная и действительно была понятна уже в первой формулировке. Но задача сложная. Не думаю, что я найду общую формулу, являющуюся ответом. Копаюсь в задаче чуть-чуть, лениво, когда есть время, но увы...

[Gurd]

(Продолжение моего предыдущего поста в этой теме)

Хотя подождите... Только что что-то начало получаться... Позднее отпишусь точнее...

[Сирениус]

банальные и тривиальные ответы
FYI в математике нет банальных/тривиальных ответов, есть удовлетворяющие НУ и противоречащие.

[Gurd]

Значит, так. Очень мало времени, поэтому без проверки, простите, если есть ошибка/ошибки. Начну с примеров.

Для N=10 искомая величина равна

10!/(0!×10!) + 9!/(1!×8!) + 8!/(2!×6!) + 7!/(3!×4!) + 6!/(4!×2!) + 5!/(5!×0!).

Для N=11 искомая величина равна

11!/(0!×11!) + 10!/(1!×9!) + 9!/(2!×7!) + 8!/(3!×5!) + 7!/(4!×3!) + 6!/(5!×1!).

Отсюда общие формулы, для чётного N и нечётного N отдельно.

Для чётного N искомая величина равна

сумме по k от N/2 до N с общим членом суммы (3N/2-k)!/((k-N/2)!×(2N-2k)!).

Для нечётного N искомая величина равна

сумме по k от (N+1)/2 до N с общим членом суммы ((3N+1)/2 - k)!/((k - (N+1)/2)!×(2N+1 - 2k)!).

[Red]

Я же говорила, что будет весело))

[kvit]

@Gurd, а свернуть можно ли? )))

[kvit]

Копаюсь в задаче чуть-чуть, лениво, когда есть время, но увы...я задачку решил, правда пришлось с карандашиком посидеть, да... )))

[Сирениус]

поэтому без проверки, простите, если есть ошибка/ошибки.
А напрасно! Пусть N=1, почему нет? И "ваша" формула для нечетных моментально приводит к абсурду, факториал отрицательных целых чисел - не существует в силу самого определения этой функции.

[Gurd]

А напрасно! Пусть N=1, почему нет? И "ваша" формула для нечетных моментально приводит к абсурду, факториал отрицательных целых числе - не существует в силу самого определения этой функции.

Ну что вы врёте, там не возникает факториала от отрицательного числа.


Для нечётного N искомая величина равна

сумме по k от (N+1)/2 до N с общим членом суммы ((3N+1)/2 - k)!/((k - (N+1)/2)!×(2N+1 - 2k)!).

Для N=1 моя формула даёт сумму по k от 1 до 1 с единственным членом 1!/(0!×1!)=1.

[Сирениус]

Я же говорила, что будет весело))
Леди, а ты мозги размять не хочешь? Ведь много лет серьезно занималась финансовой
/банковской деятельностью, теорвер/матсат знаешь неплохо, там и формут не надо, чиста на соображалку)))

[Сирениус]

вы врёте
Не я, а ваши выкладки. 0! также не существует, ибо факториал только для натуральных чисел 1,2...(N+1), к коим ноль не принадлежит.

[kvit]

Факториал нуля доопределяется, для единообразия записи комбинаторных формул, омг)))

[Сирениус]

Факториал нуля доопределяется
Нет, функцию факториала математики ввели в начале 19 века и именно для удобства решения комбинаторных счетных (!) задач, где есть вещественное количество (счета) предметов, при =0 факториал теряет математический смысл.

[kvit]

Нет, функцию факториала математики ввели в начале 19 века и именно для удобства решения комбинаторных счетных (!) задач, где есть вещественное количество (счета) предметов, при =0 факториал теряет математический смысл.Чушь!!! Могу зеркально вернуть совет сначала подтянуть теорию по вышке, а потом уже выступать с бредовыми утверждениями )))

[Сирениус]

Чушь!!! Могу зеркально вернуть совет сначала подтянуть теорию по вышке, а потом уже выступать с бредовыми утверждениями )))
Зеркала не будет, ибо Начала Математики едины для всех, и я могу лишь посочувствовать вашим учителям,
которые преподавали вам предмет - сами того не зная.
Кстати, коль скоро вы считаете себя, компетентнее меня в математике - позвольте задать вопрос: имеем степенную функция вида "Х в степени Х", какое значение эта функция принимает при Х=0?

[kvit]

@Сирениус, а комплексные числа бывают? так, для себя, хочу оценить масштабы бедствия )))

[Сирениус]

а комплексные числа бывают?
Даже в каждой розетке ~220 вольт (rms)/1 фаза/50Гц вашего жилища. Если вы не в где иная частота/напряжение.

[kvit]

Ну и как решается вопрос с корнем из отрицательного числа, которого, как говорят нам Начала Математики, не бывает?

[kvit]

Кстати, коль скоро вы считаете себя, компетентнее меня в математике - позвольте задать вопрос: имеем степенную функция вида "Х в степени Х", какое значение эта функция принимает при Х=0?

Посчитать предел при Х->0 справа, т.к. для вещественных отрицательных неопределенно, соответственно предела слева не существует

[Red]

Леди, а ты мозги размять не хочешь? Ведь много лет серьезно занималась финансовой
/банковской деятельностью, теорвер/матсат знаешь неплохо, там и формут не надо, чиста на соображалку)))
Нееее, ребята.
Я в уголочке постою))))

[Red]

Я ж говорила, что будет дым коромыслом)))))

[kvit]

Посчитать предел при Х->0 справа, т.к. для вещественных отрицательных неопределенно, соответственно предела слева не существует
А дальше можно по разному - либо постулировать, что функция х^х в нуле не определена (как например, неопределен аргумент комплексного числа с нулевыми вещ. и мним. частью), либо доопределить функцию пределом

[Сирениус]

Посчитать предел при Х->0 справа
И? каков ответ?

[kvit]

@Сирениус, либо третий путь - рассмотреть в поле комплексных чисел, возможно там вообще складка и переход с листа на лист, но это я смогу только завтра посмотреть, сейчас в дороге )))

[Сирениус]

либо постулировать, что функция х^х в нуле не определена
Неверно, она не неопределена, она в принципе не существует, как и 0!, очень плохо вас учили основам математики. И не путайте постулаты - с волевой договоренностью (это тоже в математике есть)- разные вещи.

[Сирениус]

рассмотреть в поле комплексных чисел
Ничего не изменит.

[Gurd]

@Gurd, а свернуть можно ли? )))

Не нашла, как свернуть, и поэтому только теперь погуглила, точнее, пояндексила. Нашла только ответы в виде записей с C с верхними и нижними индексами. Это не называется свернуть, это называется только по-другому обозначить. Ну и ещё там было обозначение через [.] — целую часть числа — это тоже просто другое обозначение, которое я знала, но просто не захотела применять в своём посте, чтобы не усложнять ответ. Ну и ещё, возможно, там обратный к моему порядок слагаемых в сумме, что даёт чуть-чуть более экономную запись, но скрывает мысль, как получить ответ, это тоже фигня, а не свёртывание, я сознательно не стала этого делать.

Короче, в буквальном смысле свёртывания нет в Интернете, как я поняла. Сейчас отправлю этот пост и попробую не яндексить, а в буквальном смысле гуглить, с помощью Гугла, а не Яндекса, но уже сейчас не верю в ваше свёртывание.

(Добавлено позднее)
Погуглила в буквальном смысле. Нашла в Интернете решение через рекуррентное соотношение. Оно тоже неплохо, но я сознательно искала не рекуррентное соотношение, а явную формулу. Мои формулы лучше тем, что они задают искомую величину явно, а не рекуррентно. Хотя и моё решение хуже тем, что более громоздко.

[kvit]

@Gurd, я сейчас в отъезде, без компа и с плохой связью, вернусь, найду свое решение и выложу, сравним...

[Сирениус]

Я ж говорила, что будет дым коромыслом)))))
Леди, нее, в комбинаторике засад нет - она скучная и бесполезная, в Теорвере уже намного забавнее, но настоящая веселуха начинает в вычмате.
Берем произвольный треугольник с углом при одной из вершин = ПИ/2,т.е. прямоугольный. И аппроксимируем явойную гипотенузу ступенчатой функцией. Все вертикальные и горизонтальные отрезки ступенек - проецируем на катеты. Сумма вертикальных = длина одного катета, горизонтальных - другого соответственно. А потом уменьшаем размер ступеньки до нуля. И вуаля! Длина гипотенузы = сумма длин катетов без всяких квадратов! Пифагор летит на помойку))) и ведь фиг сходу поймешь - где засада)))