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
2answers
55 views
+50

There are 4 nickle coins and 4 half nickle coins. How many different options are there for the sum of 5 coins.

I have this exercise in combinatorics: In a drawer there are 4 nickle coins and 4 half nickle coins, bob takes out from the drawer 5 nickles, how many different options are there for the sum of ...
4
votes
1answer
59 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 ...
0
votes
0answers
28 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
2answers
346 views

Undergrad-level combinatorics texts easier than Stanley's Enumerative Combinatorics?

I am an undergrad, math major, and I had basic combinatorics class before (undergrad level.) Currently reading Stanley's Enumerative Combinatorics with other math folks. We have found this book ...
0
votes
0answers
53 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, ...
0
votes
1answer
44 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 ...
3
votes
3answers
84 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 ...
1
vote
2answers
42 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 (...
-1
votes
1answer
33 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 ...
6
votes
1answer
191 views

Number Theory and d-Self-Contained Numbers

Given any natural number $N = a_{n}a_{n-1}\ldots a_{1}$, let us associate to it the set $S_{N} = \bigcup_{j=1}^{n}\{(a_{j},j)\}$. We're going to define a d-self-contained number as any natural number ...
1
vote
1answer
100 views

Possible divisors of $s(2s+1)$ follow up question.

This question is related to this post:Possible divisors of $s(2s+1)$. I have some follow up questions which should be a new post. I write $\psi(s) = s(2s+1)$. We showed that for every prime $s$ that ...
3
votes
4answers
56 views

Probability of a die rolled three times yielding three even numbers

A die is rolled three times. What is the probability of obtaining three even numbers ? I've solved this problem calculating the number of total results: $$u=D'_{6,3}=6^3$$ and the number of ...
2
votes
1answer
57 views
0
votes
0answers
10 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:=conv\left\lbrace x \in \mathbb{Z}^m_{\ge 0} \, \middle| \, \...
2
votes
2answers
37 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
2answers
34 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$, ...
5
votes
3answers
265 views

Prove ten objects can be divided into two groups that balances each other when placed on the two pans of balance. [closed]

There are 10 objects with total weight 20, each of the weight being a positive integer. Given that none of the weights exceed 10, prove ten objects can be divided into two groups that balances each ...
1
vote
4answers
91 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 ...
4
votes
0answers
30 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
42 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, ...
5
votes
2answers
70 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 ...
0
votes
0answers
7 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
2answers
86 views

Coin problem: 11 coins, 7 fake ones

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 ...
16
votes
3answers
302 views

What is $\sum_{r=0}^n \frac{(-1)^r}{\binom{n}{r}}$?

Find a closed form expression for $$\sum_{r=0}^n \dfrac{(-1)^r}{\dbinom{n}{r}}$$ where $n$ is an even positive integer. I tried using binomial identities, but since the binomial coefficient ...
4
votes
4answers
66 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 ...
3
votes
4answers
49 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
1answer
24 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 ...
7
votes
4answers
695 views

Prove this using counting techniques: $\sum_{k=0}^{n}{\binom{2n+1}k} = 2^{2n}$

I recently came across a question while studying for an exam. I haven't been able to solve it. We had to prove: $$\sum_{k=0}^{n}{2n+1\choose k} = 2^{2n}$$ We had to use counting techniques. This was ...
2
votes
2answers
875 views

Number of solutions, $a+b+c=n$, $a\gt b\gt c\ge0$

Number of non negative integral solutions for $a + b + c = n$ Where $n$ is a positive integer are $$\binom{n + 3 - 1}{3 - 1}$$ But if a condition is there $a > b > c$ Is there any direct method ...
5
votes
5answers
328 views

Proving $\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$

Prove that $$\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$$ by computing the coefficient of $z^M$ in the identity $$(1 + z + z^2 + \cdots ) \cdot \frac{1}{(1-z)^{k+1}} = \frac1{(1-z)^{k+2}}.$$ I ...
-1
votes
1answer
31 views

what is the ordered triple of postive Integers, ABC = 2104000 [on hold]

What is the ordered triple of positive integers (a,b,c) satisfy abc = 2104000 Sorry but I do not know anything about this problem.
1
vote
2answers
27 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.
6
votes
3answers
60 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$ ...
1
vote
0answers
26 views

Relation of relative numbers of (restricted) ways to distribute identical / distinct objects into distinct bins

If want to know if the following inequality holds for general values of $s \leq n \ll m$. $$\frac{C_0(n,m,s)}{C_0(n,m)} \leq \frac{p(n,m,s)}{m^n}$$ $C_0(n,m) = \binom{n+m-1}{m-1}$ is the number of ...
3
votes
3answers
137 views

How many numbers between $1$ and $9999$ have sum of their digits equal to $8$? $16$?

How many numbers between $1$ and $9999$ have sum of their digits equal to $8$? $16$? Can someone tell me if I got the right answers? I solved both cases and I've got $148$ for $8$ and $633$ for $16$. ...
4
votes
1answer
70 views

How to distribute three kinds of things of $2n$ each equally in between two people?

I have been working on this problem from Arthur Engel's problem solving strategies and I need some help here. Here is the question. $2n$ objects each of $3$ kinds are given to two people in such a ...
2
votes
2answers
37 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
21 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 ...
3
votes
2answers
42 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 ...
0
votes
0answers
24 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 ...
1
vote
1answer
60 views

binomial coefficients difference? [on hold]

I need a difference of 2 binomial coefficients that would be equivalent to the following sum: $12\choose5$+$11\choose5$+$10\choose5$+$9\choose5$+$8\choose5$ How to answer this?
2
votes
3answers
42 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 ...
9
votes
1answer
348 views

How many partial derivatives does a multivariate polynomial have?

My motivation for this question is from the following toy example; define the (nondeterministic) finite automata generated by the nonconstant* polynomial $f(x_0 , \dots , x_n) \in \mathbb{Z} [x_0 , ...
1
vote
1answer
34 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
1answer
175 views

Is Lottery probability really the same for all combos?

http://justwebware.com/uklotto/uklotto.html Test run quickpick Test run 1,2,3,4,5,6 Test run (single digit,teens,twenties,twenties,thirties,forties) 1000 times or more each cycle for as many ...
-1
votes
0answers
27 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\...
3
votes
1answer
67 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 ...
1
vote
1answer
402 views

Circular Nonconsecutive Permutations

A carousel has eight seats, each representing a different animal. Eight girls are seated on the carousel facing forward (each girl looks at another girl's back). In how many ways can the girls change ...
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 ...
1
vote
3answers
37 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 ...