All Questions
133
questions
1
vote
0
answers
39
views
Counting matrix paths for (n,m>2) matrices
Given a $n\times m$ matrix with $k$ elements inside it, I need to calculate the number of arrangements of those $k$ elements that form at least 1 path from the top to bottom matrix row composed of the ...
- 159
6
votes
0
answers
215
views
The sequence $0, 0, 1, 1, 3, 10, 52, 459, 1271, 10094, 63133,...$
Let $a_0$ be a permutation on $\{1, 2, ...,N\}$ (i.e. $a_0 \in S_N$) . For $n \geq 0$:
If $a_n(i+1) \geq a_n(i)$, then $a_{n+1}(i) = a_n(i+1) - a_n(i)$.
Otherwise, $a_{n+1}(i) = a_n(i+1) + a_n(i)$.
$...
- 1,029
1
vote
1
answer
1k
views
How to compute the Möbius function
I have no clue how to begin this problem. It involves computing the Möbius inversion function $\mu$. This problem comes from Stanley's $\textit{Enumerative Combinatorics}$, vol 1, problem 70, Chapter ...
- 23.1k
2
votes
2
answers
500
views
Finding distinct integer solutions to $x_1 + x_2 + ...+ x_r = n$
How many different (distinct $x_i$) non-negative integer solutions does the equation $x_1 + x_2 + ...+ x_r = n$ have?
We know that it has $n+r-1 \choose r-1$ non negative solutions. But how many are ...
- 11
2
votes
2
answers
705
views
Upper bound for the strict partition on K summands
In number theory and combinatorics, a partition of a positive integer $n$, also called an integer partition, is a way of writing $n$ as a sum of positive integers. Partitions into distinct parts are ...
- 191
2
votes
2
answers
110
views
Counting integers $n \leq x$ such that $rad(n)=r$
Let $r$ be the largest square-free integer that divides $n$. Then $$r = \operatorname{rad}(n)=\prod_{\substack{p\mid n\\p\text{ prime}}}p$$ $r$ is called the "radical" of $n$, or the square-...
- 23
2
votes
1
answer
183
views
given 20 diff jewelry, wear 5 per day. proof that after 267 days at least one pair of jewelry would be wear in 15 diff days.
Given 20 different jewels.
which 5 of them can be wear per single day.
proof that after 267 days, there would be at least one pair of jewelry that wears together (in other combination) in 15 ...
CommunityBot
- 1
0
votes
0
answers
73
views
Counting integers in the Thue-Morse sequence
Let's call the infinite Thue-Morse sequence $T$. Define $\delta (n)$ to be $1$ if the binary representation of $n$ appears in $T$ and $0$ otherwise. Let $$F(n)=\sum_{i=1}^n\delta(i)$$
$\delta(7)=0$ , $...
- 1,022
2
votes
0
answers
35
views
Linear extension of a divisors set
For a number $N$, let $S_N$ be its set of divisors, and let $C(N)$ be the number of arrangements of $S_N$ in which every divisor itself appears after all of its divisors.
$C(12)=5$, because of the ...
- 1,022
2
votes
1
answer
339
views
Behrend's construction on large 3-AP-free set
Theorem (Behrend's construction)
There exists a constant $C>0$ such that for every positive integer
$N$, there exists a $3$-AP-free $A\subseteq[N]$ with $|A|\geq
Ne^{-C\sqrt{\log N}}$.
Proof. Let $...
- 2,251
1
vote
1
answer
244
views
Farkas' lemma for variables in the natural numbers
A lot of questions regarding the Farkas' lemma has already been done here. Most of them seems to be related to consequences of the Farkas' lemma, for example, see [1, 2, 3]. This means that the ...
- 4,835
1
vote
1
answer
159
views
Deza-Frankl-Singhi theorem
Let $p$ be a prime number and $A$ b a system of $(2p-1)$ element subsets of of an $n$-element set such that no two sets in $A$ intersect in precisely $p-1$ elements. I would like to prove that
$$|A|\...
- 9,080
5
votes
1
answer
208
views
If you write down all the numbers from 1 to n, how many digits would you have written down?
I've seen the question for numbers like 50, 100 or 1000, but not for $n$. Although I found a formula that might be the answer, but I don't know the name of it or the proof for it. I couldn't find it ...
- 126k
6
votes
0
answers
121
views
Count number of ways to distribute n distinct positive integers into $r$ identical bins such that the product of integers in each bin is $\le M$
Problem Statement:
We have $n$ distinct positive integers say $a_1,a_2....a_n$ and a given integer value $M$.
We have to count number of ways to distribute these integers to $r$ identical bins subject ...
CommunityBot
- 1
7
votes
1
answer
344
views
Combinatorics With Relations
The twelvefold way offers a framework for counting functions, under various conditions which can be expressed as n-fold Cartesian Products of the function's domain, function, and codomain attributes. ...
- 8,096