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 \...
- 429k
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
968
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,612
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,707
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