All Questions
96
questions
44
votes
3
answers
10k
views
How do I count the subsets of a set whose number of elements is divisible by 3? 4?
Let $S$ be a set of size $n$. There is an easy way to count the number of subsets with an even number of elements. Algebraically, it comes from the fact that
$\displaystyle \sum_{k=0}^{n} {n \...
- 432k
32
votes
3
answers
5k
views
When is $\binom{n}{k}$ divisible by $n$?
Is there any way of determining if $\binom{n}{k} \equiv 0\pmod{n}$. Note that I am aware of the case when $n =p$ a prime. Other than that there does not seem to be any sort of pattern (I checked up ...
- 2,106
30
votes
8
answers
3k
views
An identity for the factorial function
A friend of mine was doodling with numbers arranged somewhat reminiscent of Pascal's Triangle, where the first row was $ 1^{n-1} \ \ 2^{n-1} \ \cdots \ n^{n-1} $ and subsequent rows were computed by ...
user279515
27
votes
2
answers
1k
views
A nice formula for the Thue–Morse sequence
The Thue–Morse sequence$^{[1]}$$\!^{[2]}$ $t_n$ is an infinite binary sequence constructed by starting with $t_0=0$ and successively appending the binary complement of the sequence obtained so far:
$$\...
- 47.3k
27
votes
1
answer
1k
views
What is the sum of the binomial coefficients ${n\choose p}$ over prime numbers?
What is known about the asymptotic order and/or lower and upper bound of the sum of the binomial coefficients
$$
S_n = {n\choose 2} + {n\choose 3} + {n\choose 5} + \cdots + {n\choose p}
$$
where the ...
- 20.8k
25
votes
1
answer
994
views
$f(x)=\sum_{t}{x \choose t}{n-x \choose k-t}$ - even or odd?
The following function popped in my research:
$$f(x)=\sum_{\array{0\le t\le k \\ t\equiv_p a}}{x \choose t}{n-x \choose k-t}$$
Where:
$n,k$ are natural numbers and $k\le n$.
$t$ is taken over all ...
- 19.4k
19
votes
4
answers
518
views
"Binomiable" numbers
Is there a nice criterion to determine whether a given natural $m$ can be written as a binomial number $\binom{n}{k}$ with $1 < k < n-1$?
I've been thinking on this problem with a friend and ...
- 889
14
votes
1
answer
352
views
are there known cases where $\binom{n}{k}$ is a perfect prime power?
I was wondering about cases where $\binom{n}{k}=p^j$ with $p$ a prime (nontrivially, so that $ n-k>1$ and $n \neq p^j$.) I had the terrible idea of checking binomial expansions
$$(x+y)^n \equiv x^n+...
- 21k
12
votes
2
answers
602
views
If a power of 2 divides a number, under what conditions does it divide a binomial coefficient involving the number that it divides?
We have had many questions here about the divisibility of $\binom{n}{k}$, many of them dealing with divisibility by powers of primes, or expressions involving the $\textrm{gcd}(n,k)$ (I originally ...
- 1,068
11
votes
8
answers
17k
views
Proof of binomial coefficient formula.
How can we prove that the number of ways choosing $k$ elements among $n$ is $\frac{n!}{k!(n-k)!} = \binom{n}{k}$ with $k\leq n$?
This is an accepted fact in every book but i couldn't find a ...
- 9,173
10
votes
0
answers
357
views
Dissecting the complexity of prime numbers
Each prime number greater than $9$, written in base $10$, ends with one of the four digits $1,3,7,9$. Therefore, each ten can be classified according to which of these four digits, summed to the ten, ...
user559615
9
votes
1
answer
563
views
Binomial Congruence
How can we show that $\dbinom{pm}{pn}\equiv\dbinom{m}{n}\pmod {p^3}$ where $m$ and $n$ are nonnegative integers and $p$ is a prime such that $p \geq 5$ ? I can do it for $\mod p^2$ but I am stuck here....
- 111
8
votes
5
answers
312
views
Show that $ \sum_{k=0}^{n} \binom{2n+1}{2k} 3^k $ is divisible by $2^n$
I want to prove that
$$
\sum_{k=0}^{n} \binom{2n+1}{2k} 3^k = \sum_{k=0}^{2n} \binom{2n}{k} 3^{\lceil k/2 \rceil}
$$
is divisible by $2^n$.
I tried induction the following way
\begin{align*}
\...
- 18.2k
8
votes
1
answer
172
views
Largest power of $p$ which divides $F_p=\binom{p^{n+1}}{p^n}-\binom{p^{n}}{p^{n-1}}$ [closed]
I would like to know your comments in order to obtain the largest power of the prime number $p$ which divides
$$
F_p=\binom{p^{n+1}}{p^n}-\binom{p^{n}}{p^{n-1}}.
$$
I proved the largest power that ...
- 649
8
votes
2
answers
434
views
$\binom{2p-1}{p-1}\equiv 1\pmod{\! p^2}$ implies $\binom{ap}{bp}\equiv\binom{a}{b}\pmod{\! p^2}$; where $p>3$ is a prime?
From $\binom{2p-1}{p-1}\equiv 1\pmod{\! p^2}$ how does one get $\binom{ap}{bp}\equiv\binom{a}{b}\pmod{\! p^2},\,\forall a,b \in \mathbb N,\, a>b$; where $p>3$ is a prime ?
user228168