Articles of combinatorics

The primes $s$ of the form $6m+1$ and the greatest common divisor of $2s(s-1)$

I had trouble coming up with a good title. Let $\psi(s) = 2s(s-1)$. I write $(\psi(s),\psi(s+2))$ to be the greatest common divisor of $\psi(s)$ and $\psi(s+2)$. Then if $s$ is prime and $(\psi(s),\psi(s+2))=12$ we have that $s=6m+1$ for some positive integer $m$. Conversely if $s=6m+1$ is prime then $(\psi(s),\psi(s+2))=12$. I would like to solve this […]

A question on primes and equal products

Is the following statement true; “For any odd prime number $p$ , any set of $p-1$ consecutive integers can not be partitioned into two subsets such that the elements of the two sets have equal product.” ( I think I read somewhere that Erdos proved it but now I can not remember where I read […]

How many ways are there of coloring the vertices of a regular $n$-gon

How many ways are there of coloring the vertices of a regular $n$-gon with all $p$ colors ($n,p \ge 2$), such that each vertex is given one color, and every color isn’t used for two adjacent vertices? If in a way to color not necessarily use all $p$ colors, then the answer is $a_n=(-1)^n(p-1)+(p-1)^n\;.$ If […]

Recurrence equation question

My question (which has been edited) relates to the following recurrence relation: $$a_{j+2}=\frac{2 a_{j}}{j}$$ The book which I am reading says that the (approximate) solution is given by: $$a_{j}=\frac{C}{(j/2)!}$$ (I think there was an assumption of large $j$, too) Could anyone give me a hand to understand how to arrive at this solution or give […]

$\binom{n}{k}\binom{n}{n – k}$ vs $\binom{n}{k}$ – Differences? Similarities?

So the # of ways to choose an $n$ set with $k$ kiwis is $\binom{n}{k}\binom{n}{n – k} = \binom{n}{k}^2$. AlexR wrote No, picking exactly $k$ kiwis means you discount the $n-k$ remaining kiwis, but you still have to chose $n-k$ figs out of $n$, wich is the second factor. $1.$ I don’t apprehend AlexR’s answer […]

Distributing $k$ distinct items among $r$ distinct groups without ordering

Calculate the number of ways of distributing $k$ distinct items among $r$ distinct groups such that each group receives at least $a$ and at most $b$ items and internal arrangement of items within groups doesn’t matter. For example suppose there are 2 groups and 3 items A, B, C. The distributions (AB, C) and (BA, […]

Secret Santa Combinatorics with couples

I have researched this site and find several secret Santa related questions but none that I can find that relates to couples. If there are three couples (6 people) and no one can draw their own name or the name of their significant other, how many ways can this be done? Thanks in advance.

Count $k$-subsets with at least $d>1$ different elements (pairwise)

The problem of counting the number of $k$-subsets in a set of size $n$ is well known. The answer is ${n \choose k}$. But here, I want $k$-subsets with the property that any two of them have at least $d$ different elements. If we take the set $S = \{1, 2, 3, 4, 5, 6\}$ […]

Count a Partial Equivalence Relations on a set

A Partial Equivalence Relation is a relation that is symmetric and transitive, and to count the number of equivalence relations on a set exists Bell Numbers, my question is How I can count the number of Partial Equivalence Relations on a set $\{ 1, \cdots , n\} $?

Permutations and Combinations? 3 digit number…

1) Make a 3 digit even number without repeated digits, using 0, 4, 5 , 6, 7. Also the first digit cannot be 0. 2)Arrange 12 books in a line, 4 of which are english, 3 of which are science, and 5 calculus, so that all books of same subject are adjacent.