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
5 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
3answers
53 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
1answer
55 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
2answers
52 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 ...
0
votes
0answers
33 views

Number Theory Characterization Problem 2

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, ...
1
vote
2answers
62 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
301 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
62 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
46 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
18 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
693 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
327 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
25 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
58 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 ...
1
vote
2answers
35 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
19 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
41 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
23 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 ...
5
votes
1answer
173 views

Number Theory Characterization Problem

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 ...
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
174 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
66 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 ...
1
vote
2answers
64 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 \...
0
votes
1answer
43 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 ...
0
votes
0answers
24 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
25 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
10 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 ...
2
votes
2answers
74 views

Enumeration of primes

Given a prime number $p$, there is an associated number $n(p)$, giving its ranking in the sense that $n(2)=1$, $n(3)=2$, $n(5)=3$ etc. Is there a closed form expression for $n(p)$ in terms of $p$?
-1
votes
1answer
32 views

If G and H are two gaphs 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.
5
votes
1answer
143 views

Number of zeros in Fibonacci sequences mod $p$

We know that Fibonacci sequences are periodic in mod $m$. For example, for $p\equiv \pm 1 \pmod 5$ and $\pm 2 \pmod 5$ the periods for Fibonacci sequences modulo $p$ divide $p-1$ and $2p+2$ ...
6
votes
1answer
518 views

Different Perspectives of Multinomial Theorem & Partitions

There are 2 important interpretations of the multinomial theorem and coefficients. 1: Determining the number of ordered strings that can be formed using a set of letters. For example, with 1 m, 4 i'...
2
votes
1answer
60 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 $\...
0
votes
1answer
41 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 $...
1
vote
1answer
51 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)^...
0
votes
2answers
416 views

Determine the number of positive integer x where x<= 9,999,999 and the sum of the digits in x equals 31.

Determine the number of positive integer x where $$x\le 9,999,999$$ and the sum of the digits in x equals 31 How do you approach this question? TEXTBOOK SOLUTION: Let x be written in base 10. ...
3
votes
3answers
363 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(...
2
votes
0answers
44 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
51 views

Black are berries and maroon are cherries. Place 8 more cherries removing berries 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?