Количество пар взаимно простых из комбинации n простых чисел

[Soul Friend]

Сколько взаимно простых чисел мы можем получить при $n$-ном количестве простых (не повторяющихся) чисел?
$a(1)=0$
$a(2)=1$
$a(3)=6$
$a(4)=17$
$a(5)=90$ ?(здесь не уверен правильно ли для $a(5)$, если правильно - то такой последовательности нет в OEIS)
Есть ли формула такой последовательности?
Выписывал каждую комбинацию вручную, закономерность пока не выявил.
На примере первых простых чисел:
$\{2\}$ - 0 пары не получается.
$\{2, 3\}$ - 1 одна пара.
$\{2, 3\}\{2, 5\}\{3, 5\}\{2\cdot 3, 5\}\{2\cdot 5, 3\}\{3\cdot 5, 2\}$ - 6 пар.
и.т.д.

[B@R5uk]

Почему комбинация 3 и 4 не считается?

[Soul Friend]

B@R5uk в сообщении #1373799 писал(а):

Почему комбинация 3 и 4 не считается?

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

[Shadow]

Сколькими способомами можно бросить $n$ пронумерованных шаров в 3-х пронумерованных ящиков так, что первый и второй - обязательно непустые? (Результат потом разделить на 2). Формула выводится легко, последовательность в OEIS есть, перепроверьте $a(4)$.

[Soul Friend]

да, ошибся, для $a(4)=25$ выходит, но всё равно не находится такая последовательность: 0,1, 6, 25.

Shadow в сообщении #1373818 писал(а):

Сколькими способомами можно бросить $n$ пронумерованных шаров в 3-х пронумерованных ящиков так, что первый и второй - обязательно непустые?

в двух ящиках, и это количество $n$ шаров тоже надо варьировать между собой без повторений их нумераций. Возможно, вы не то имеете ввиду.

[Otta]

Soul Friend в сообщении #1373828 писал(а):

Возможно, вы не то имеете ввиду.

Нет, имеется в виду именно то. И ящиков именно два. Подумайте почему.
Последовательность не находится - так Вам Shadow прямо сказал, что

Shadow в сообщении #1373818 писал(а):

Сколькими способомами можно бросить $n$ пронумерованных шаров в 3-х пронумерованных ящиков так, что первый и второй - обязательно непустые? (Результат потом разделить на 2).

(Выделено мной).
Она там одна такая, эта последовательность. И даже название у нее есть.

[Soul Friend]

Otta в сообщении #1373835 писал(а):

И ящиков именно два

Я и подправил что именно два.
Вот эту последовательность (0, 1, 6, 25, 90) нужно разделить на два ? Или наоборот умножить? Если делить или умножать значит нет конкретно именной той последовательности что я пишу, вы меня путаете.
Пока понял только что нужно вычислять суммы сумм сочетаний из $n$ элементов по $k$.

[Otta]

Soul Friend в сообщении #1373847 писал(а):

Я и подправил что именно два.

Нет. Два - это которые "первый и второй". Всего три.

Soul Friend в сообщении #1373847 писал(а):

Вот эту последовательность (0, 1, 6, 25, 90) нужно разделить на два ?

Потом разделить на два, потом, тогда получится Ваша из OEIS-овской.

[Soul Friend]

А зачем вообще нужен третьи ящик, если используются только две?
Для начала, (0, 1, 6, 25, 90) я правильно вычислил для $n=1, 2 ,3, 4, 5$ ?

[Otta]

Вот я и говорю: подумайте. Зачем первый? зачем второй? а что тогда в третьем?
Возьмите конкретный пример и на нем посмотрите. Скажем, $n=4$.
(Я могу сказать, мне не тяжело, но додумываться-то интереснее).

[Soul Friend]

Otta в сообщении #1373851 писал(а):

(Я могу сказать, мне не тяжело, но додумываться-то интереснее).

Всё нормально, время есть, я подумаю.

[Soul Friend]

Для $n=4$ :
$(2, 3) (2, 5) (2, 7) (3, 5) (3, 7) (7, 5)$

$(2\cdot3, 5) (2\cdot3, 7) (2\cdot5, 3) ( 2\cdot5, 7)$ $(2\cdot7, 3) (2\cdot7, 5)$
$(3\cdot5, 2) (3\cdot5, 7) (3\cdot7, 2) (3\cdot7, 5)$
$(5\cdot7, 2) (5\cdot7, 3)$

$(2\cdot3, 5\cdot7) (2\cdot5, 3\cdot7) $$(2\cdot7,3\cdot5)$

$(2, 3\cdot5\cdot7) (3, 2\cdot5\cdot7)$$ (5, 2\cdot3\cdot7) (7, 2\cdot3\cdot5)$
Всего 25 комбинации.
Но по формуле выходит 34:
$(C_4^1 \cdot C_3^1)+(C_4^2 \cdot C_2^1)+(C_4^2 \cdot C_2^2)+(C_4^3 \cdot C_1^1)=34$

[Shadow]

Soul Friend в сообщении #1373912 писал(а):

Всего 25 комбинации.
Но по формуле выходит 34:

Soul Friend, по какой формуле? Формул пока я никаких не видел.

Soul Friend в сообщении #1373850 писал(а):

А зачем вообще нужен третьи ящик, если используются только две?

Правильно, но для трех простых ($2,3,5$) вы сами написали одно решение

Soul Friend в сообщении #1373743 писал(а):

$\{2, 3\}$

А где пятерка? Что с ней? Вы ее просто не использовали, да? А будет ли ошибкой, если скажем, что вы ее просто выбросили...в мусорный бак. И будет ли ошибкой, если этому "мусорному баку" окажем честь, назвав его ящиком "C"?

[Soul Friend]

Не могу понять, когда нужно делить на два, а когда не нужно. Имеется $n=4$ пронумерованных шара, и два ящика. Соответственно, четыре варианта размещения шаров в эти два ящика без учёта порядка шаров и ящиков (когда оба ящика не пусты):
(1,1) - в каждом ящике по одному шару.
(2, 1) - в одном ящике два шара, в другом один, далее (2, 2) и (3, 1).
Возьмём в пример случаи (2, 2) и (3, 1), когда нам не нужен будет третьи ящик:
для (2, 2) - число сочетаний (с учётом нумерации шаров, без учёта их порядка) равно 3, то есть результат $\frac{4!}{2!(4-2)!}=6$ делим на два (так как всего три таких сочетаний).
А вот когда (3, 1) , $\frac{4!}{3!(4-3!)}=4$ не делим, так как имеется 4 сочетания. Постом выше я написал, сгруппировав, эти сочитания.
Причины, когда в первом случае делим на два, а во втором - не делим ?

[Shadow]

Soul Friend в сообщении #1374379 писал(а):

Причины, когда в первом случае делим на два, а во втором - не делим ?

Не мы, а вы. И по каким причинам вы это делаете известно только вам.
Имеется $n$ пронумерованных шара, ящик А, ящик B и мусор С. Берем по порядку каждый шар и бросаем его в один из ящиков. Для каждого шара у нас 3 варианта, значит для $n$ шаров $3^n$ вариантов. Но ящик А должен быть непустым. Значит нужно исключить те варианты, когда бросали только в В и С. Сколько таких? Правильно $2^n$
Нужно исключить еще и когда В пустой - опять $2^n$, и добавить единичку, потому что вариант когда бросали только в С исключили два раза.
Итого $3^n-2\cdot 2^n+1$
Но ящики А и В именованные, тоест пары $(a,b)$ и $(b,a)$ будут считаться разными, а вы этого не хотите. Значит нужно разделить на 2. И формула принимает вид:

$\dfrac{3^n+1}{2}-2^n$