For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

0
votes
0answers
90 views

Solutions to recurrence relations

Consider functions $s_{m},c_{m},d_{m}$ defined by the following recurrence relations $$s_{1}=n$$ $$c_{1}=s$$ $$d_{1}=0$$ $$s_{2}=n$$ $$c_{2}=s-n$$ $$d_{2}=d$$ $s,n, d$ are integers. If $c_{m}>...
4
votes
1answer
98 views

Solutions to $a_1+2a_2+\cdots+ka_k = 1979$

For $k = 1,2,\ldots$ consider the $k$-tuples $(a_1,a_2,\ldots,a_k)$ of positive integers such that $$a_1+2a_2+\cdots+ka_k = 1979.$$ Show that there are as many such $k$-tuples with odd $k$ as there ...
1
vote
2answers
56 views

Creating a league schedule for camp

I searched around for similar questions, but none seem to fit this. I am making a league schedule for camp and I want that each team will play every other team approximately the same number of times (...
3
votes
2answers
104 views

How many positive integers from set $\{1,2…,10^{30}\}$ can't be represented as 2nd, 3rd, or 5th power of some positive integer?

An interesting problem I ran across. My guess is that it can be solved somehow using inclusion-exclusion principle. It would be a fun thing to learn how to do this, so I could use that knowledge in ...
0
votes
0answers
15 views

Decomposition of an element of the convex hull

Let natural numbers $ 2 \le c_m \mid c_{m-1} \mid \ldots \mid c_1 $ and $ C \in \mathbb{N} $ with $ C\ge c_1 $ be given, and define $ P:=\operatorname{conv}\left\lbrace x \in \mathbb{Z}^m_{\ge 0} \, \...
2
votes
2answers
54 views

How many ways are there to add up odd integers to 20?

How many ways are there to add up odd integers to 20? Here, $1+19$ is one solution, $19+1$ is a different solution, and $1+1+\dots+1$ counts as just one solution.
0
votes
1answer
57 views

Incompressible countable Total-ordering implies well-ordering i

A totally-ordered set (S,<) is incompressible if $(S,<) \cong (T,<)$ and $S \supseteq T$ implies $S = T$. Is it true that if $S$ is incompressible countable and totally-ordered then $S$ is ...
0
votes
1answer
63 views

Number Theory and p-Remainder Numbers

In order to submit the problem, here it comes the definition we are interested in. Given any natural number $N = a_{n}a_{n-1}\ldots a_{1}$ and some natural $p > 1$, we will designate a p-remainder ...
0
votes
2answers
38 views

Number of ways to arrange $8$ rooks on a chessboard

Find the number of ways to arrange $8$ rooks on a chessboard such that no two of them attack other? I was thinking it would be $64 \times 49 \times 36 \times 25 \times 16 \times 9\times 4 \times 1$, ...
4
votes
0answers
45 views

Proof verification: Mantel's theorem

if a graph $G=(V,E)$ on $n$ vertices contains no triangles than it contains at most $n^2/4$ edges. Proof: Let v$\in$V be a vertex of maximum degree k. since G contains no triangles, there are no ...
1
vote
2answers
43 views

Different ways to create a 5 different digit integer

The number of ways to create a five digit integer such that all of the digits are different is $9 \cdot 9 \cdot 8 \cdot 7 \cdot 6 = 27216$. However, if I select the numbers from the ones digits first, ...
0
votes
1answer
23 views

Covering a uniform hypergraph with complete $r$-partite hypergraphs

In combinatorial terms, I was wondering how many complete $r$-partite $k$-uniform hypergraphs are needed to cover the edges of the complete $n$-vertex $k$-uniform hypergraph $\binom{[n]}{k}$. An $r$-...
1
vote
4answers
95 views

“Perfect ten” dice game

I have been modelling a dice game, trying to tweak the parameters to make it reasonably close to fair. The rules are as follows: The player pays a \$1 game fee. Then she throws one normal die ...
0
votes
0answers
70 views

Number Theory and p-Progressive Numbers

Before proposing the problem itself, it shall be profitable to define $b_{p}(k) = k^{p}$. In other words, the sequence $b_{p}(k)$ is an arithmetic progression of order p. For the sake of our purposes, ...
2
votes
3answers
176 views

Coin problem: 11 coins, 7 fake ones [closed]

There are 11 coins, 4 real, 7 counterfeit, the weights of the counterfeit ones are different for each counterfeit coin and different from the weight of the real coin. What is the minimal number of ...
3
votes
4answers
53 views

Finding the number of vertices in a complete graph without finding the roots of a quadratic

I'm taking a class where we are often asked to answer questions like the following: If G is a complete graph with 105 edges, how many vertices does G have? If I were to solve this question, I ...
1
vote
2answers
32 views

How many five-digit numbers are there that have number 4 as at least one digit?

How many five-digit numbers are there that have number 4 as at least one digit? How to do this? I don't know how to start.
5
votes
2answers
79 views

How to find $\sum_{A \subset S} (\min A)$ and $\sum_{A \subset S} (\max A)$ if $S=\{1,2,…,n\}$?

Here, $\min A$ and $\max A$ denote the minimum and maximum element respectively of the set $A$. So I have to calculate how many subsets of S have min/max element $1$, how many subsets have min/max ...
6
votes
3answers
64 views

Positive integer solution to equation $(x_1+x_2+x_3)(y_1+y_2+y_3+y_4)=15$

What is the total number of positive integer solution to the equation $(x_1+x_2+x_3)(y_1+y_2+y_3+y_4)=15$ a) 20 $\qquad$ $\qquad$ $\qquad$ $\qquad$ b) 18 c) 10 $\qquad$ $\qquad$ $\qquad$ $\qquad$ ...
2
votes
2answers
41 views

What's the probability of getting a pair of king and ace with the same suit?

First off, the answer that was given is $$\frac{{4\choose1}{2\choose2}{50\choose11}-{4\choose2}{4\choose4}{48\choose9}+{4\choose3}{6\choose6}{46\choose7}-{4\choose4}{8\choose8}{44\choose5}}{52\...
1
vote
0answers
23 views

Special case of Pieri-Rule

is there an "elementary" (read: short combinatorial) proof for the rule $$ s_\lambda \cdot s_{(1)} = \sum_{\mu} s_{\mu} $$ where $\mu$ ranges over all partitions obtained from $\lambda$ by adding a ...
1
vote
1answer
27 views

The coordinate difference of a nearest neighbor in a random set

Consider the following problem: $r$ vectors of length $t$ are drawn randomly, where each coordinate is an i.i.d Bernoulli random variable with success probability $$p_i , i=1...t.$$ What is the ...
0
votes
0answers
27 views

Number of possible ways to join n relations

The number of possible ways to join n relations r1⨝r2⨝r3.....⨝rn can have 3 distinct cases - If the join orders cannot change i.e. ri can only be joined to rj or any other intermediate relation ...
6
votes
4answers
85 views

How many ways a 9 digit number can be formed using the digits 1 t0 9 without repetition such that it is divisble by $11$.

How many ways a 9 digit number can be formed using the digits 1 t0 9 without repetition such that it is divisible by $11$. My attempt- A number is divisible by 11 if the alternating sum of its digit ...
1
vote
1answer
36 views

Maximize the number of non zero elements of a product of binary matrices.

I want to find two binary matrices $A$ of size $N \times M$ and $B$ of size $M \times N$ such that: $AB=C$ is a strictly lower-triangular matrix ($j \geq i \implies C_{ij}=0$) The number of ...
0
votes
0answers
33 views

All unique shapes from drawing lines between array of points

I have encountered this problem various times, but have never got my head around it. (I'm not very good in in problems like this...) Please don't blame me for not knowing specific math terms. (I ...
2
votes
3answers
56 views

Counting the number of subsets of a set of 2n elements satisfying some conditions.

Let $X =\{v_1, v_2,\cdots, v_n, v_{n+1},\cdots, v_{2n}\}$ be a set of $2n$ elements. I want to find the number of subsets of $X$ with $n$ elements such that both $v_i$ and $v_{n+i} $ are not together ...
-1
votes
0answers
29 views

For a set of positive integers $A$, does there exist some other set of positive integers $B$ such that some subset of $B$ sums to all $a\in A$

We ask, given a set of positive integers $A$ where each $a\in A$ $a>1$, does there exist some other set of positive integers $B$ such that for each positive integer $a\in A$ there exists $b_i\...
1
vote
0answers
30 views

Using the general ham sandwich theorem to proof Hobby-Rice

Matousek mentions that you can proof the continuous necklace theorem known as Hobby-Rice theorem via the continuous ham sandwich theorem. The continuous ham sandwich states: Let $\mu_1,\mu_2,...,\...
0
votes
0answers
30 views

Number of distinct integer-valued vector solution for $x_1 + x_2 + … + x_r = n$ [duplicate]

The Number Of Integer Solutions Of Equations $$x_1 + x_2 + ... + x_r = n$$ An approach is to find the number of distinct non-negative integer-valued vectors $(x_1,x_2,...,x_r)$ such that $$x_1 + x_2 +...
0
votes
0answers
13 views

how to calculate slack(u,v) in the Edmond's minimum weight matching algorithm (u and v are vertices of a graph)?

I am trying to execute the Edmond's minimum weight matching algorithm. As a reference, I am using a book titled "Combinatorial Optimization Theory and Algorithms" by Bernhard Korte and Jens Vygen. The ...
3
votes
2answers
49 views

Languages acceptable with just a single final state

For a given regular language $L$ we can always find a corresponding automaton with exactly one initial state, this is quite a common result and in most textbooks even non-deterministic automata are ...
-1
votes
1answer
44 views

If $G$ and $H$ are two graphs, then what does $G \Delta H$ indicate in graph theory?

I came across this notation in a book titled "Combinatorial Optimization Theory and Algorithms" by Bernhard Korte and Jens Vygen.
0
votes
1answer
43 views

Number of graphs having a specific structure

Let $\mathcal{N} = \{1,2,\ldots,N\}$ and $\mathcal{N}^i = \mathcal{N}\setminus \{i\} $. For each $i \in \mathcal{N}$ and for each $S \subset \mathcal{N}^i$, we have a vertex $C_i^S$. For example, if $...
3
votes
3answers
379 views

Arranging numbers around a square

In how many ways numbers 1 to 12 can be arranged on a sides of squares (5 places on each sides i.e 20 places total) leaving 8 places empty? I am getting answer as 12c5(selecting 5 numbers)*7c5(...
1
vote
2answers
68 views

Find the divisors of $5040$ in the Plato's dialogue “Theaetetus”

In the Plato's dialogue "Theaetetus", at a certain point, we have the following "problem" \begin{align*} 5040 &= 7! \\ &= 1\times 2 \times 3 \times 4 \times 5 \times 6 \times 7 \\ &= 2 \...
1
vote
3answers
44 views

Concerning The Number of Ways of Drawing a Full House vs. Two Pair

The Wikipedia entry for "Poker probability" gives the following result for the number of ways of drawing a full house: $$ \binom{13}{1} \binom{4}{3} \binom{12}{1} \binom{4}{2} = 3, 744. $$ The logic ...
1
vote
1answer
56 views

Closed form for $\sum_{k=0}^{m} {\binom {m}{k}} a^{k} (b+ck)^N$

Is there a closed form for the following? $$\sum_{k=0}^{m} {\binom {m}{k}} a^{k} (b+ck)^N$$ how about a pretty limit for large $b$. I have tried using the binomial expansion for the $(b+ck)^...
2
votes
0answers
49 views

Partitioning a set of integers (with Alice and Bob)

Let $ d_1,\ldots,d_n \in \mathbb{N}_{\ge 2} $ (not necessarily distinct) be given. Define $ D:=\operatorname{lcm}(d_1,\ldots,d_n) $ and $ d:=\sum_{i=1}^n d_i $. (1) Alice claims that whenever $ \...
2
votes
1answer
60 views

Another form of Menage Problem : Place 8 more cherries(maroon) removing berries(black) 1 from each row and each column. No of ways?

I tried to see it as a matrix where for a position (i,j) , i+j = 8, 9, 16 means you can't change that position. Any help?
0
votes
1answer
74 views

Binomial coefficient paths?

Here's a problem and my attempt to answer it: We want to get a binomial coefficient identity depending on grid walking. Starting from the bottom left corner and going to the top right corner. You can ...
1
vote
2answers
34 views

What is the chance of randomly generating a given 10-character sentence? [closed]

Suppose we have an alphabet of the following allowed characters: the lowercase letters $a$ through $z$ (26) the uppercase letters $A$ through $Z$ (26) the numerals $0$ through $9$ (10) the common ...
2
votes
1answer
64 views

The first step in the proof of the Pólya-Vinogradov Inequality.

The well-known Pólya-Vinogradov Inequality states: $$\forall m, n \in \mathbb{N}: \displaystyle \left|{\sum_{k \mathop = m}^{m+n} \left({\frac k p}\right)}\right| < \sqrt p \ \ln p,$$ where $\...
2
votes
1answer
64 views

Help in this little doubt in this proof from Hoffman and Kunze's Linear Algebra book

I'm reading Hoffman and Kunze's Linear Algebra book and on page 177 they stated and proved the following theorem: It's a big proof which I didn't understand only a very little part of it: I ...
3
votes
1answer
26 views

How to find combinations with two conditions, one of them dependent on the other?

How to find the number of combinatorial arrangements with two conditions, if one of the conditions is itself dependent on the second? The question below will make it clearer. The problem statement ...
3
votes
2answers
95 views

The number of positive integer solutions to the equation $x_1+x_2+…+x_n=n^2.$

I'm working on this problem. To solve it I need this lemma: Let $n\ge2, n\in \mathbb N$. Let $X$ be the number of solutions in positive integers to the equation $x_1+x_2+...+x_n=n^2$. Let $Y$ be ...
2
votes
1answer
19 views

Expectation of absolute sum of squared normal distributions

Let $u_i$ be a standard normal distribution for all $i$. All $u_i$'s are independent of each other. I want to compute the expectation of: $$| \sum_i u_i^2 \lambda_i |$$ Where $\lambda_i$ is real ...
1
vote
1answer
44 views

Expected number of couples having same number

I have $n_1$ red balls in a box $A$. These balls are numbered from $1, \cdots n_1$. Let make a copy version of box $A$, called box $D$ (It means that the box $D$ will contain $n_1$ red balls from $1, \...
0
votes
1answer
21 views

Expected sum of Hamming distances in set of random strings

Thee Hamming distance $H(S_1, S_2)$ between two binary strings $S_1, S_2$ of length $n$ is the number of positions on which the two strings disagree. It is straightforward to show that if $S_1, S_2$ ...
3
votes
1answer
68 views

Team grouping troubles

Imagine there are 12 teams, numbered 1 through 12. There are 10 games those teams can compete in, with two teams needed per game. There are 10 rounds, and it is important that after the 10 rounds are ...