All Questions
Tagged with combinatorics number-theory
275
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
39
votes
7
answers
67k
views
In how many ways can a number be expressed as a sum of consecutive numbers? [duplicate]
All the positive numbers can be expressed as a sum of one, two or more consecutive positive integers. For example $9$ can be expressed in three such ways, $2+3+4$, $4+5$ or simply $9$. In how many ...
- 581
27
votes
1
answer
34k
views
The number of partitions of $n$ into distinct parts equals the number of partitions of $n$ into odd parts
This seems to be a common result. I've been trying to follow the bijective proof of it, which can be found easily online, but the explanations go over my head. It would be wonderful if you could give ...
- 497
16
votes
3
answers
969
views
Are there any Combinatoric proofs of Bertrand's postulate?
I feel like there must exist a combinatoric proof of a theorem like: There is a prime between $n$ and $2n$, or $p$ and $p^2$ or anything similar to this stronger than there is a prime between $p$ and $...
- 12.5k
11
votes
4
answers
19k
views
number of ordered partitions of integer
How to evaluate the number of ordered partitions of the positive integer $ 5 $?
Thanks!
- 5,622
10
votes
2
answers
1k
views
Number of solutions of $x_1+2x_2+\cdots+kx_k=n$?
Suppose $n$ be a given positive integer. Then the Diophantine equation $x=n$ has only $1$ solution. Just by inspection, I found that the Diophantine equation $x+2y=n$ has $\left\lfloor \dfrac{n}{2}+1\...
- 18.4k
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
22
votes
1
answer
28k
views
Counting ways to partition a set into fixed number of subsets
Suppose we have a finite set $S$ of cardinality $n$. In how many ways can we partition it into $k$-many non empty subsets?
Example: There is precisely one way to partition such a set into $n$-many ...
- 1,237
3
votes
3
answers
1k
views
How to prove formula for power sum
I simply used Newton's Interpolation method and some observation in pattern and i constructed formula for power sum.
Formula
Let's $n$ and $m$ are the integers with $n\geq 1$ and $m\geq 0$
$$\sum_{...
- 2,697
2
votes
1
answer
4k
views
Number of positive integral solutions of $a+b+c+d+e=20$ such that $a<b<c<d<e$ and $(a,b,c,d,e)$ is distinct
This is from a previous question paper for an entrance exam I am preparing for.
https://www.allen.ac.in/apps/exam-2014/jee-advanced-2014/pdf/JEE-Main-Advanced-P-I-Maths-Paper-with-solution.pdf (Link ...
- 53
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
5
votes
1
answer
3k
views
Pairs of numbers with a given LCM
How can we show that the number of pairs $(a,b)$ (where the pairs $(a, b)$ and $(b, a)$ are considered same) with $\operatorname{lcm}(a, b) = n$ is equal to
$$\displaystyle\frac{(2e_1+1)(2e_2+1)...(...
- 589
0
votes
3
answers
248
views
Counting non-negative integral solutions
I'm reading this passage and wondering why
Number of ways in which
k identical balls can be distributed into
n distinct boxes =
$$\binom {k+n-1}{n-1}$$
could someone explain it to me please?
- 175
17
votes
2
answers
3k
views
Minimum Cake Cutting for a Party
You are organizing a party. However, the number of guests to attend your party can be anything from $a_1$, $a_2$, $\ldots$, $a_n$, where the $a_i$'s are positive integers. You want to be prepared, ...
- 49.8k
7
votes
3
answers
576
views
Find all natural numbers $n > 1$ and $m > 1$ such that $1!3!5!\cdots(2n - 1)! = m!$
Find all natural numbers $n > 1$ and $m > 1$ such that $1!3!5!\cdots(2n - 1)! = m!$
I have been thinking about coming up with some inequalities which would narrow the possible range of pairs $(...
- 559
6
votes
2
answers
5k
views
Same number of partitions of a certain type?
Is there a quick explanation of why the number of partitions of $n$ such that no parts are divisible by $d$ is the same as the number of partitions of $n$ where no part is repeated $d$ or more times, ...
- 63
6
votes
1
answer
990
views
Is there any perfect squares that are also binomial coefficients?
Examining the Tartaglia's triangle, I have observed that all the squares were the trivial cases, that is, $\binom{n^2}1$ or $\binom{n^2}{n^2-1}$.
More formally:
Conjecture: If $\binom nm=k^2$ then $...
- 65.9k
6
votes
3
answers
236
views
How to prove $\sum\limits_{i=0}^{\lfloor\frac{r}{2}\rfloor}\binom{r}{i}\binom{r-i}{r-2i}2^{r-2i}=\binom{2r}{r}$
Please help me to prove $\sum\limits_{i=0}^{\lfloor r/2\rfloor}\binom{r}{i}\binom{r-i}{r-2i}2^{r-2i}=\binom{2r}{r}$. By computer search I have found these for r varies from 0 to 10000. How to prove ...
- 159
4
votes
2
answers
403
views
Maximum run in binary digit expansions
For numbers between $2^{k-1}$ and $2^{k}-1$, how many have a maximum run of $n$ identical digits in base $2$? For instance, $1000110101111001$ in base $2$ has a maximum run of 4.
See picture below ...
- 3,645
3
votes
2
answers
127
views
$\sum_{k=m}^{n}(-1)^k\binom{n}{k}\binom{k}{m}=0, n>m\geq 0$
I got quite some trouble trying to prove this.
$$\sum_{k=m}^{n}(-1)^k\binom{n}{k}\binom{k}{m}=0, n>m\geq 0$$
I tried using $$\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}$$ and then ...
- 378
2
votes
1
answer
365
views
Efficient computation of $\sum_{i=1}^{i=\left \lfloor {\sqrt{N}} \right \rfloor}\left \lfloor \frac{N}{i^{2}} \right \rfloor$
I have tried to find a closed form but did not succeed but is there an efficient way to calculate the following expression
$\sum_{i=1}^{i=\left \lfloor {\sqrt{N}} \right \rfloor}\left \lfloor \frac{N}...
- 37
0
votes
1
answer
1k
views
Polya's formula for determining the number of six-sided dice
Use Polya's enumeration to determine the number of six-sided dice that can be manufactured if each of three different labels must be placed on two of the faces.
Can you help me please to solve this ...
- 6,840
29
votes
3
answers
3k
views
When is $\binom{2n}{n}\cdot \frac{1}{2n}$ an integer?
In a recent question here, asking about the number of necklaces of $n$ white and $n$ black beads (reworded in terms of apples and oranges), one of the naive and incorrect answers was that as there are ...
- 80.2k
18
votes
1
answer
6k
views
What is the number of Sylow p subgroups in $S_p$?
I am reading the Wikipedia article entitiled Sylow theorems. This short segment of the article reads:
Part of Wilson's theorem states that
$(p-1)!$ is congruent to $-1$ (mod $p$) for every prime $p$....
- 3,711
15
votes
4
answers
1k
views
When is the number of areas obtained by cutting a circle with $n$ chords a power of $2$?
Also asked on MathOverflow: When is the number of areas obtained by cutting a circle with $n$ chords a power of $2$?
Introduction
Recently, a friend told me about the following interesting fact:
...
- 13.8k
15
votes
1
answer
8k
views
How to find the smallest number with just $0$ and $1$ which is divided by a given number?
Every positive integer divide some number whose representation (base $10$) contains only zeroes and ones. One can easily prove that using pigeonhole principle.
...
- 395
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
11
votes
3
answers
1k
views
Summation with combinations
Prove that $n$ divides $$\sum_{d \mid \gcd(n,k)} \mu(d) \binom{n/d}{k/d}$$ for every natural number $n$ and for every $k$ where $1 \leq k \leq n.$ Note: $\mu(n)$ denotes the Möbius function.
I have ...
- 15.6k
11
votes
5
answers
13k
views
How many non-negative integer solutions does the equation $3x + y + z = 24$ have?
If the equation is $x + y + z = 24$ then it is solvable with stars and bars theorem. But what to do if it is $3x + y + z = 24$?
- 3,146
7
votes
0
answers
189
views
Combinatorial interpretation of rational function on e
Over the last few weeks I have become obsessed with expressions like
$$
\frac{e+4 e^{2}+e^{3}}{(1-e)^{4}},
$$
$$
\frac{e+26 e^{2}+66 e^{3}+26 e^{4}+e^{5}}{(1-e)^{6}},
$$
or
$$
\frac{e+120 e^{2}+1191 e^...
