Правило суммы в комбинаторике: Ошибка 403 — доступ запрещён

Содержание

определение, примеры с решением задач

п.1. Правило суммы

Пусть множество A состоит из n элементов, а множество B состоит из m элементов. При этом множества не пересекаются, A ∩ B = ∅.
Тогда общий набор, множество A ∪ B состоит из n + m элементов.
Выбрать один элемент a ∈ A ИЛИ b ∈ B можно n + m способами.

Например:
На подносе лежит 5 слив и 4 абрикоса.
Сколькими способами можно выбрать фрукт с подноса?
Всего фруктов: 5 + 4 = 9. Значит – 9 способов.

п.2. Правило произведения

Пусть множество A состоит из n элементов, а множество B состоит из m элементов. При этом множества не пересекаются, A ∩ B = ∅.
Тогда множество всех возможных упорядоченных пар (a, b) = A · B состоит из n · m элементов.
Выбрать упорядоченную пару a ∈ A И b ∈ B можно n · m способами.

Например:
Сколько всего двузначных четных чисел?
В двузначном числе на первом месте могут быть цифры {1; 2; … 9}, n = 9
В двузначном четном числе на втором месте могут быть цифры {0; 2; … 8}, m = 5
Всего nm = 9 · 5 = 45 чисел.

п.3. Исключение «двойного учета» для неупорядоченных пар

При составлении пар порядок бывает неважен: (a, b) или (b, a), – главное, составить пару. В таком случае, например, пары (1; 2) и (2; 1) – одно и то же.
Поэтому правило произведения для неупорядоченных пар:

Пусть множество A состоит из n элементов, а множество B состоит из m элементов. При этом множества не пересекаются, A ∩ B = ∅.
Тогда множество всех возможных неупорядоченных пар (a, b) ≡ (b, a) состоит из \(\mathrm{\frac{n\cdot m}{2}}\) элементов.
Выбрать неупорядоченную пару a ∈ A И b ∈ B можно (n · m)/2 способами.

Например:
В саду поспевает 7 видов фруктов. Было решено сварить компот из любых двух фруктов. Сколько всего различных компотов можно сварить?
Первый фрукт можно выбрать n = 7 способами.
Второй фрукт можно выбрать m = 6 способами.
В данном случае 2 фрукта образуют неупорядоченную пару – неважно, в каком порядке их бросать в кастрюлю. Поэтому \(\mathrm{N=\frac{7\cdot 6}{2}=21}\).
Ответ: 21 различных компотов.

п.4. Примеры

Пример 1. О 4-значном пин-коде карты известно, что первая и последняя цифры у него одинаковые, вторая и третья – разные, и не равны первой цифре.
Сколько всего вариантов такого пин-кода?

В начале и в конце одновременно используются цифры {0;1;…;9}, n = 10
На второй позиции могут использоваться все цифры, кроме уже использованной на первом месте, m = 9
На третьей позиции могут использоваться все цифры, кроме уже использованных на первом и втором месте, k = 8
По правилу произведения общее количество наборов: N = nmk = 10·9·8 = 720.
Ответ: 720 вариантов.

Пример 2. Сколько всего 3-значных чисел, у которых ровно две цифры.
а) семёрки; б) нули?

а) Варианты расстановки семёрок:
77x, x ≠ 7 – таких чисел 9
7×7, x ≠ 7 – таких чисел также 9
x77, x ≠ 7 – таких чисел 8 (слева не может стоять 0)
По правилу суммы: 9 + 9 + 8 = 26

б) Вариант расстановки нулей только x00, x ≠ 0 – таких чисел 9
Других вариантов нет.
Ответ: а) 26 чисел; б) 9 чисел.

Пример 3. На экзамене будет 5 задач по 5 разным темам. Каждая задача берется из списка, в котором 8 задач по теме. Вася умеет решать по 3 задачи из каждой темы.
Сколько всего вариантов билетов может быть на экзамене?
Сколько существует вариантов билетов, за которые Вася получит 5 баллов?
Сколько существует вариантов билетов, в которых Вася не решит ни одной задачи?

В экзамене по каждой теме n = 8 вариантов выбора задачи. По правилу произведения всего возможно N = 8⁵ = 32768 вариантов билетов.
Вася готов решать k = 3 задачи по каждой теме. По правилу произведения всего он сможет полностью решить K = 3⁵ = 243 вариантов.
Вася не готов решать m = 8 – 3 = 5 задач по каждой теме. По правилу произведения всего он вообще не сможет решить M = 5⁵ = 3125 вариантов.
Ответ: 32768; 243; 3125.

Пример 4. Каких пятизначных чисел больше: тех, что не делятся на 5, или таких, у которых ни первая, ни вторая слева цифры – не пятёрки?

Сколько всего пятизначных чисел? На первом месте – 9 вариантов цифр, на четырёх последующих – по 10 вариантов. Итого: N = 9 · 10⁴ = 90000 чисел.
Признак делимости на 5: последняя цифра 5 или 0.
Количество чисел с последней цифрой 5: M₁ = 9 · 10³ · 1 = 9000.
Аналогично, с последним 0: M₂ = 9 · 10³ · 1 = 9000.
Итого, чисел, которые не делятся на 5:
M = N – (M₁ + M₂) = 90000 – 2 · 9000 = 72000.
Сколько всего пятизначных чисел, у которых ни первая, ни вторая слева цифры – не пятёрки? На первом месте – 8 вариантов цифр, на втором – 9 вариантов. На остальных – по 10 вариантов.
Итого: K = 8 · 9 · 10³ = 72000 чисел.
Получаем: M = K – искомых чисел поровну.
Ответ: их поровну.

Пример 5*. На глобусе проведено 17 параллелей и 24 меридиана. На сколько частей разделена поверхность глобуса?

Возьмём неразмеченный глобус. Проведем экватор.
Поверхность глобуса разделилась на 2 части.
Добавим еще одну параллель. Поверхность разделилась на 3 части.
Мы видим, что n параллелей делит поверхность на N = n + 1 частей.
Соответственно, для 17 параллелей, N = 18 частей.

Опять берём неразмеченный глобус. Проведем меридиан.
Поверхность глобуса разделилась на 2 части.
Добавим ещё один меридиан. Поверхность разделилась на 4 части.
Мы видим, что m меридианов делит поверхность на M = 2m частей.
Соответственно, для 24 меридианов, M = 48 частей.
Общее количество частей по правилу произведения (с исключением «двойного учета», т.к. нам всё равно: мы сначала проводили параллели, а потом – меридианы, или наоборот): \(\mathrm{\frac{NM}{2}=\frac{48\cdot 18}{2}=432}\).
Ответ: 432 части.

Правила суммы и произведения

1.Правило суммы: если объект А может быть выбран n способами, а объект В – m способами, то выбор «А или В» может быть осуществлен n+m способами.

Пример. Если на одной полке книжного шкафа стоит 30 различных книг, а на другой — 40 различных книг (и не таких, как на первой полке), то выбрать одну книгу из стоящих на этих полках можно 30+40=70 способами.

При использовании правила сложения нужно следить, чтобы ни один из способов выбора объекта А не совпадал с каким-нибудь способом выбора объекта В, т. е. чтобы ни одна комбинация не попала сразу в два класса. Если такие совпадения имеются, правило сложения в ранее сформулированной форме утрачивает силу, и мы получаем m + n – k способов выбора, где k — число совпадений.

2. Общее правило суммы: Если объект А можно выбрать m способами, а объект В — n способами, причем при k способах одновременно выбираются и А и В, то выбор «А или В» можно осуществить m + n – k способами.

Пример. Сколько чисел в первой сотне, не делящихся ни на 2, ни на 3?

Решение: Легче вычислить сначала количество чисел первой сотни, делящихся на 2 или на 3. Каждое второе число в натуральном ряде делится на 2, каждое третье— на 3. Поэтому в первой сотне есть 50 чисел, делящихся на 2, и 33 числа (неполное частное от деления 100 на 3), делящихся на 3. Но среди первых и вторых имеются числа, делящиеся и на 2, и на 3, т. е. делящиеся на 6. На 6 делится каждое шестое число в натуральном ряде. Если 100 разделить на 6, то неполное частное будет равняться 16, т. е. 16 чисел в первой сотне делится на 6. Итак, количество чисел в первой сотне, делящихся на 2 или на 3, равно 50 + 33 – 16 = 67. Все остальные не делятся ни на 2, ни на 3. Этих чисел 100 – 67 = 33.

3.Правило произведения: если объект а может быть выбран n способами и после каждого из таких выборов объект в – m способами, то выбор «а и в» в указанном порядке может быть осуществлен n*m способами.

Пример. В школьной столовой на первое можно заказать борщ, солянку, грибной суп, на второе — мясо с макаронами, рыбу с картошкой, курицу с рисом, а на третье — чай и компот. Сколько различных обедов можно составить из указанных блюд?

Решение: Первое блюдо можно выбрать одно из трех (борщ, солянку или грибной суп), второе блюдо тоже одно из трех (мясо с макаронами, рыбу с картошкой или курицу с рисом), на десерт только два варианта (чай или компот). Используя правило произведения, получаем: 3х3х2=18.

Пример. В классе 25 человек. Сколькими способами:

а) можно распределить между ними два различных учебника;

б) можно распределить между ними два различных учебника так, чтобы никто не получил оба учебника;

Решение: а) Первый учебник может получить любой из 25 учащихся.Кто бы ни получил первый учебник, второй может достаться снова любому из 25, ведь в условии не сказано, что каждый должен получить не более одного учебника. Всего имеем 25* 25 = 625 способов.

б) В отличие от предыдущего задания, никто не должен получить оба учебника. Поэтому для каждого из 25 вариантов выбора обладателя первого учебника есть 24 способа выбора обладателя второго учебника. Всего имеем 25*24 = 600 способов.

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

Пример. Сколькими способами из 28 костей домино можно выбрать две кости так, чтобы их можно было приложить друг к другу (т. е. чтобы какое-то число очков встретилось на обеих костях)?

Решение. Сначала выберем одну кость. Это можно сделать 28 способами. При этом в случаях выбранная кость окажется «дублем», т.е. костью вида 00, 11, 22, 33,44 , 55 ,66, а в 21 случае — костью с различными числами очков (например, 05, 13 и т.д.).В первом случае вторую кость можно выбрать 6 способами (например, если на первом шагу выбрана кость 11, то на втором шагу можно взять одну из костей 01, 12, 13, 14, 15, 16).Во втором же случае вторую кость можно выбирать 12 способами (для кости 35 подойдут кости 03, 13, 23, 33, 34, 36, 05, 15, 25, 45, 55, 56). По правилу произведения в первом случае получаем 7*6=42 выбора, а во втором 21*12=252 выбора. Значит по правилу суммы получаем 42+252=294 способов выбора пары.

Пример. Сколько существует четырехзначных чисел, у которых все цифры нечетные? Сколько существует четырехзначных чисел, в записи которых есть хотя бы одна четная цифра?

Решение. Всего нечетных цифр — пять, поэтому выбор k-й цифры числа может быть сделан n_к=5 способами (к=1, 2, 3, 4), а количество четырехзначных чисел, у которых все цифры нечетные, равно 5*5*5*5=625. Чтобы ответить на второй вопрос, проще не определять последовательно, сколько существует чисел, в записи которых ровно одна четная цифра, две цифры, три цифры, четыре цифры, а воспользоваться полученным ответом на первый вопрос. Все четырехзначные числа, а их 9999-999=9000, делятся на две группы: те, в записи которых все цифры нечетные, и те, в записи которых есть хотя бы одна четная цифра. Следовательно, количество чисел второго типа равно 9000-625=8375.

Пример. Из города А в город В ведут пять дорог, а из города В в город С — три дороги. Пусть, кроме того, из города А в город D можно попасть двумя путями, из D в C — четырьмя (рис.1). Сколькими способами можно добраться из А в С?

Рис. 1. Варианты перемещения между городами

Решение: Возможны два случая: путь из А в С проходит через город В или через город D. В каждом из этих случаев число возможных маршрутов легко подсчитать, воспользовавшись правилом произведения. В первом случае имеется 5*3 = 15 маршрутов; во втором — 2*4 = 8. Складывая, получаем общее число маршрутов: 15 + 8 = 23.

Правило суммы и произведения – это общие правила решения комбинаторных задач. Кроме них в комбинаторике пользуются формулами для подсчета числа отдельных видов соединений, которые встречаются наиболее часто.

Правило суммы | Brilliant Math & Science Wiki

Правило суммы применяется только к взаимоисключающим вариантам выбора, то есть можно выбрать только один из вариантов. Чтобы определить, когда использовать правило суммы (в отличие от правила произведения), попробуйте перефразировать вопрос. Если вопрос можно перефразировать словом «или», это обычно указывает на то, что применяется правило суммы.

Мэри сегодня надела свою счастливую рубашку, и ей нужно выбрать одну из 3 красных и 4 синих юбок, которые она наденет с этой рубашкой. Сколько различных вариантов одежды для одной юбки у нее есть в течение дня?
Поскольку Мэри может носить одну из 3 красных юбок или одну из 4 синих юбок, выбор является взаимоисключающим и применяется правило суммы. Это дает в общей сложности \( 3 + 4 = 7 \) различных вариантов снаряжения. \( _\квадрат \)

12 16 23 28

В местном кинотеатре идут \(5\) боевики, \(7\) комедии и \(16\) драмы. Если вы идете в кинотеатр, чтобы посмотреть один фильм, сколько у вас есть вариантов, какой фильм посмотреть?

Рави идет в зоомагазин и обнаруживает, что в зоомагазине есть \(3\) рептилии, \(4\) птицы, \(5\) кролики и \(6\) рыбы. Если Рави может выбрать только одно животное в качестве питомца, сколько у него есть вариантов для питомца?
Поскольку Рави может выбрать рептилию, или птицу, или кролика, или рыбу, применяется правило суммы. Затем

есть \(3\) способа выбрать рептилию;
есть \(4\) способа выбрать птицу;
есть \(5\) способов выбрать кролика;
есть \(6\) способов выбрать рыбу.
По правилу суммы существует \(3+4+5+6=18\) способов выбрать питомца. \(_\квадрат\)

Крис играет в карточную игру, и в его руке есть три пятерки, два валета, два туза, одна девятка и один король. Если ему нужно выбрать одну карту для игры в следующем раунде, сколько у него есть вариантов выбора карты?
Так как Крис может играть \(5,\) или валетом, или тузом, или девяткой, или королем, применяется правило суммы. Затем
есть \(3\) способов выбрать \(5;\)
есть \(2\) способа выбрать Джека;
есть \(2\) способов выбрать туз;
есть \(1\) способ выбрать \(9;\)
есть \(1\) способ выбрать короля.
По правилу суммы найдется \(3+2+2+1+1=9\) способы выбора карты для игры в следующем раунде. \(_\квадрат\)

Когда подбрасываются \(6\) неразличимых одинаковых монет, сколько существует различных исходов?

Детали и предположения:

Два исхода одинаковы, если они содержат одинаковое количество решек.

В дилерском центре в городе Исаака продаются 10 красных грузовиков, 5 синих грузовиков, 3 красных автомобиля и 2 синих автомобиля. Если Исаак собирается купить ровно одну красную машину, сколько вариантов у него есть?
Красные автомобили — это 10 красных грузовиков и 3 красных автомобиля. Следовательно, всего имеется \( 10+3= 13 \) красных автомобилей.
\( _\квадрат \)

Учитывая полную колоду карт, сколько карт с черными лицами или красными и четными?
Поскольку есть 3 лицевых карты (валет, дама и король) и 5 четных карт (2, 4, 6, 8, 10), у нас есть следующее, соответствующее нашим критериям:
3 лицевые карты пиками
3 лицевые карты в трефах
5 четных в червах
5 пар в бриллиантах.
Таким образом, по правилу суммы существует \( 3 + 3 + 5 + 5 = 16 \) вариантов, которые будут работать. \(_\квадрат\)

Сколько неотрицательных целочисленных решений существует для следующего:
\[ -5 < x < 5\quad \text{ или }\quad 12 < x < 100 ?\]
Рассматривая каждое неравенство в отдельности, мы видим, что существует \( 4 — (-4) + 1 = 9 \) целочисленных решений уравнения \(-5 < x < 5\), но \(-4, -3, -2,\) и \(-1\) отрицательны, поэтому есть только \( 9-4=5 \).
Существует \( 99-13+1 = 87 \) целочисленных решений \( 12 < x < 100 \), и все они положительные.
Таким образом, по правилу суммы у нас есть \( 5 + 87 = 92\) возможных ответов. \(_\квадрат\)

Правило суммы и правило произведения Решение задач

Сандип Бхардвадж, Эндрю Эллинор, Пи Хан Го, и

способствовал

Содержимое

Введение
Примеры
Решение проблем
Смотрите также

Правило суммы (принцип сложения) и правило произведения (принцип умножения) изложены ниже.

Правило суммы — Заявление:
Если есть \( n\) вариантов для одного действия и \( m\) вариантов для другого действия, и два действия не могут быть выполнены одновременно, то есть \( n+m\) способов выбрать одно этих действий.
Правила продукта — заявление:
Если есть \( n\) способов сделать что-то, а затем \( m\) способов сделать еще что-то, то есть \( n\× m\) способов выполнить оба этих действия.

Вот пример, основанный на вышеуказанных правилах.

Кэлвин хочет поехать в Милуоки. Он может выбрать из \(3\) автобусов или \(2\) поездов, чтобы отправиться из дома в центр Чикаго. Оттуда он может выбрать один из двух автобусов или трех поездов, чтобы отправиться в Милуоки. Сколько способов есть у Кальвина, чтобы добраться до Милуоки?
У него есть \(3 + 2=5\) способов добраться до центра Чикаго. (Правило суммы)
Отсюда у него есть \( 2+3=5\) способов добраться до Милуоки. (Правило суммы)
Следовательно, всего у него есть \( 5\times 5=25\) способов добраться до Милуоки. (Правило произведения) \(_\квадрат\)

Попробуйте решить следующие проблемы.

3 8 2 6

Есть 3 рейса из Калифорнии во Францию и 2 рейса из Франции в Индию. Санджит хочет полететь из Калифорнии во Францию, а затем в Индию.

Сколько вариантов его плана полета?

Ресторан предлагает 5 вариантов закусок, 10 вариантов основного блюда и 4 варианта десерта. Клиент может выбрать одно блюдо, два разных блюда или все три блюда. Предполагая, что все варианты еды доступны, сколько различных возможных блюд предлагает ресторан?

Примечание. Когда вы едите курс, вы выбираете только один из вариантов.

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

Кэлвин хочет поехать в Милуоки. Он может выбрать из \(3\) автобусов или \(2\) поездов, чтобы отправиться из дома в центр Чикаго. Оттуда он может выбрать один из двух автобусов или трех поездов, чтобы отправиться в Милуоки.
На этот раз он должен купить проездной билет на автобус (что позволит ему ездить только на автобусах) или билет на поезд (что позволит ему ездить только на поезде). Если у него есть деньги только на \(1\) из этих концессий, сколько у него есть способов добраться до Милуоки?
Если Кальвин купит проездной на автобусе, у него будет \( 3 \x 2=6\) способов добраться до Милуоки. (Правило произведения)
Если Кальвин покупает концессию на поезд, у него есть \( 2\x3=6\) способов добраться до Милуоки. (Правило произведения)
Следовательно, всего у него есть \(6+6=12\) способов добраться до Милуоки. (Правило суммы) \(_\квадрат\)

Шестеро друзей Энди, Бэнди, Кэнди, Денди, Энди и Фэнди хотят сесть в ряд в кинотеатре. Если доступно только шесть мест, сколькими способами мы можем посадить этих друзей?
На первое место у нас есть выбор любого из 6 друзей. После посадки первого человека на второе место у нас есть выбор любого из оставшихся 5 друзей. После посадки второго человека на третье место у нас есть выбор любого из оставшихся 4 друзей. После посадки третьего человека на четвертое место у нас есть выбор любого из оставшихся 3 друзей. После посадки четвертого человека на пятое место у нас есть выбор любого из оставшихся 2 друзей. После посадки пятого человека, на шестое место у нас есть выбор только из 1 оставшегося друга. Следовательно, по правилу произведения существует \( 6 х 5 х 4 х 3 х 2 х 1 = 720) способов рассадить этих 6 человек. \(_\квадрат\) 9b\), где \( a\) и \( b\) — целые числа, удовлетворяющие \( 0 \leq a \leq 4, 0 \leq b \leq 3\). Есть 5 возможностей для \(a\) и 4 возможности для \(b\), и, следовательно, есть \( 5 \times 4 = 20\) (правило произведения) положительных делителей 2000 во всех. \(_\квадрат\)

Следующие задачи познакомят вас с двумя правилами, описанными выше.

60 10 20 36

Сколько параллелограммов получится, если набор из 5 параллельных прямых пересечет набор из 4 параллельных прямых?

Детали и предположения

Все параллельные линии бесконечно удлиняются.

Если вы подсчитаете способы подъема на 3 ступени, вы обнаружите, что существует 4 способа подъема на 3 ступени. Представьте, что ноги человека настолько длинны, что он может подняться по 11 ступеням за раз. лезть вверх.

Тогда найдите количество способов, которыми вы можете подняться на 11 ступенек?

Бонус : Обобщите это для \(n\) шагов.

Трое детей, каждый в сопровождении опекуна, хотят поступить в школу. Princi хочет опросить всех 6 человек одного за другим при одном условии, что ни один ребенок не будет опрошен в присутствии его опекуна. Сколькими способами это можно сделать?

Этот раздел содержит задачи от простых до сложных. Попробуйте перечисленные задачи и улучшите свое понимание решения проблем.

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

Если кто-то покрасит снаружи куб \( 5 \times 5 \times 5 \) из \( 1 \times 1 \times 1 \) единичных кубов, сколько единичных кубов будет окрашено ровно с двух сторон?

По дороге в школу из дома 5 почтовых ящиков. Моя мама дала мне 13 (разных) писем для отправки. Если я могу отправить каждое письмо в любой почтовый ящик, каким захочу, сколькими способами я могу отправить письма?

В игре-побеге вы нашли замок с номерами от 1 до 60. Ранее вы нашли лист бумаги внутри прозрачной бутылки. На листе бумаги изображен замок и четыре подсказки:

1) Четыре числа завершают последовательность.

2) Нет двух одинаковых чисел.

3) Второе число вдвое больше третьего.

4) Третье число простое.

Сколько возможных комбинаций существует для замка?

Определите количество трехзначных положительных целых чисел, произведение цифр которых равно 144?

Даниэль хочет получить 100-дневную серию на Brilliant. org. Он планирует сделать это следующим образом:

В первый день он решает \(1\) задачу. На второй день он решает \(2\) задач. На третий день он решает \(3\) задач. Эта закономерность продолжается до \(10\)-го дня. В \(10\)-й день он решает \(1+0=1\) задачу. В \(11\)-й день он решает \(1+1=2\) задач. В общем, в \(\overline{ab}\)-й день он решает \(a+b\) задач. Наконец, на \(100\)-й день он решает \(1+0+0=1\) задачу, завершая свою серию.

Сколько всего задач он решил?

A Kaboobly Dooists — человек, который много занимается Kaboobly Doo.

Однажды зимним вечером к вам приходят четыре Kaboobly Dooists, Алиса, Боб, Чарльз и Дик. К сожалению, у вас не было для них ничего, кроме 5 яблок, 4 апельсинов и 3 манго. И вы не хотите тратить на них все 12 фруктов, так как хотите оставить 8 для себя. Итак, вы даете в общей сложности 4 фрукта, по одному фрукту каждому из них.

Сколькими способами это можно сделать?

Число 2014 состоит из 4 различных цифр; 1 цифра нечетная, а 3 цифры четные, из них одна цифра ноль.

Сколько четырехзначных чисел (первое не может быть 0) обладают этими свойствами?

Пусть \(n\) будет количеством целых чисел от \(1\) до \(97531\) (включительно), которые не содержат цифры \(2,4,6,8\). Каковы последние три цифры числа \(n\)?

Сколько существует упорядоченных пар \( (A, B) \), где \(A, B\) — подмножества \( \{ 1, 2, 3, 4, 5\} \), таких, что \ (|А\шапка В|=1\)?

Детали и предположения

Учащиеся, не знакомые с системой обозначений, могут обратиться к сообщению в блоге, посвященном системе обозначений, для получения определений.

Рассмотрим псевдо-палиндром:

\[БЫЛА ЭТО КОШКА, ЧТО Я ВИДЕЛ?\]

Сколькими способами можно прочитать \(БЫЛА ЭТО КОШКА, которую Я ВИДЕЛ\), если вы можете начать с любой \(W\ ) и двигаться только вправо, влево, вверх или вниз к соседним буквам? Имейте в виду, что каждый регистр можно учитывать дважды, поскольку это палиндром, и что одна и та же буква может использоваться более одного раза в каждой последовательности.