This tag is for basic 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 (5)

1
vote
3answers
69 views

Draw 4 cards where: 3 cards same suit and remaining card of different suit

Four cards are drawn from a standard 52-card deck without replacement. Find the probability that exactly 3 cards are of the same suit and the remaining card is of a different suit. What I did: ...
0
votes
1answer
80 views

Pascal's Triangle

My question is the following; Q: Prove that if we move straight down in Pascal’s Triangle (visiting every other row), then the numbers we see are increasing. Found an answer but that doesn't count ...
1
vote
2answers
61 views

Solve for the number of students who took an exam.

An exam consisted of $28$ problems. Each student solved $7$ problems correctly. For every pair of problems solved, there are exactly $2$ students who solved them correctly. How many students took the ...
3
votes
1answer
47 views

Proving a Binomial Identity

Can you please help me with problem 25. I need to prove that $f(n+1)=2 f(n)$, where $f(n)$ is the LHS of the expression, from there on I can do it my self. I have tried using the binominal theorem ...
0
votes
2answers
51 views

Number of positive integral solution of product $x_{1} \cdot x_{2} \cdot x_{3}\cdot x_{4}\cdot x_{5}=1050$ is

The number of positive integral solution of product $x_{1} \cdot x_{2} \cdot x_{3}\cdot x_{4}\cdot x_{5}=1050$ is $\bf{My\; Try}::$ Given $x_{1}\cdot x_{2}\cdot x_{3}\cdot x_{4}\cdot x_{5} = 2 ...
1
vote
3answers
51 views

Letters of the word $\bf{“ALASKA”}$ can be arranged in a circle (Diff. b/w clockwise & Anticlockwise.)

(1): Numbers of ways in which all the letters of the word $\bf{"ALASKA"}$ can be arranged in a circle distinguishing between the clockwise and anticlockwise arrangements, is (2): Numbers of ways in ...
0
votes
2answers
20 views

Choosing a committee with a constraint - where is my reasoning wrong?

Okay, this is an example from Challenge and Trill of Pre-college Mathematics by Krishnamurthy et al. In how many ways can we form a committee of three from a group of 10 men and 8 women, so that ...
5
votes
1answer
64 views

Application of Davenport theorem

The Davenport theorem (or Cauchy-Davenport theorem for some authors ) states that for any two nonempty subsets $A$ and $B$ of the prime field $\mathbb Z/p\mathbb Z$ we have $$|A+B| ≥ \min(p, ...
3
votes
3answers
52 views

$5$ digit no. in which at least $3$ digits are identical.

The number of $5$-digit numbers that can be made with digits $\left\{1,2,3,4,5,6\right\}$ in which at least $3$ digits are identical is. $\bf{My\; Try::}$ No.,s in which at least $3$ digits are ...
22
votes
6answers
2k views

A beautiful game of gold and silver coins

A stack of silver coins is on the table. For each step we can either remove a silver coin and write the number of gold coins on a piece of paper, or we can add a gold coin and write the number of ...
0
votes
1answer
33 views

Combination with Repetitions and a bound on set

Emily really loves chocolate, but lately she has been indecisive on what kinds of chocolate to eat. She currently has a collection of various chocolate squares of 1 square inch, 2 square inches, and 3 ...
0
votes
3answers
58 views

Problem about sets of integers

Given 15 pairwisely different integers. Pat wrote all sums of 7 integers and Vova wrote all sums of 8 integers from this set. Can the set of sums of Pat be equivalent to the set of sums of Vova? I'm ...
0
votes
1answer
59 views

How many combinations can I make?

let $n \gt 1$ be an integer, and consider $n$ people; $P_1, P_2,..., P_n$ let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group have either one or two ...
1
vote
1answer
61 views

Combinatorics: fewest weighting possible.

I have trouble for this weighting problem: You are given 4 balls, all equal in weight except for one that is either heavier or lighter. You are also given a two-pan balance to use. In each use of ...
1
vote
2answers
35 views

Number of ways to paint a strip of $n$ slots using $k$ colors?

Suppose I have $k$ colors, all of which must be used at least once. How many distinct ways are there to paint a strip of $n$ slots with these $k$ colors? Stars and bars and multinomial coefficients ...
0
votes
2answers
33 views

Equality in Local LYM

The Local LYM inequality says the following : for all $A \subseteq [n]^{(r)}$, $$ \frac{|\partial A|}{\binom{n}{r-1}} \geq \frac{|A|}{\binom{n}{r}},$$ where $\partial A$ is the lower shadow of $A$ and ...
1
vote
1answer
38 views

solving a simple problem of combination , with different approach

I found a question and I have different approach to solve it , but unable to get the answer. Question :How many 3-digit numbers can be formed from the digits 2, 3, 5, 6, 7 and 9, which are divisible ...
2
votes
0answers
30 views

Find $f(n)$ in $\binom {2^n} {n^4} = (f(n)+ o(1))^n$

Task is to find $f(n)$ in the following equation: $\binom {2^n} {n^4} = (f(n)+ o(1))^n$ I've found that the problem is a bit over my head. I'm attaching my partial solution below: With use of the ...
3
votes
2answers
58 views

How many permutations of N integers with K pairs of numbers that can't be adjacent?

This is a computer science problem, I have a difficulty with the math part. There are $n$ integers $\{1, 2,\dots, n\}$ and $K$ pairs of numbers $(a, b)$; $a \ne b$; $a, b \le n$. No pairs are ...
0
votes
1answer
43 views

Combinatorics question. Where am I wrong in my reasoning?

A 5-card poker hand is said to be a full house if it consists of 3 cards of the same denomination and 2 other cards of the same denomination (of course, different from the first denomination). Thus, ...
0
votes
1answer
47 views

solving combinatorial problem using partition functions

How many natural numbers less than 99000 have the sum of the digits equal to 8. This is what I tried to do.Let $x_i$ be the ith digit for any $i \in \{1,2,3,4,5\}$. Ways of creating numbers less ...
0
votes
0answers
20 views

arranging three objects in six spaces

How many ways are there to arrange three objects in six spaces so no two objects are next to each other? I know the answer is 4 by doing it manually How can you tackle this problem using ...
-1
votes
1answer
37 views

number of integer solutions combinatorial problem

Find the number of integer solutions to $x_1+x_2+x_3+...+x_7=23$ subject to $x_1\gt0,x_2\ge3$ and $x_i\gt0$ for all $i\ge3$. This is the given answer in the book: Using the substitutions $y_1=x_1-1$ ...
0
votes
2answers
32 views

How do I count all values that satisfy X mod N=1 in the range [A,B]

I want to count how many values of x in range [A,B] give remainder of 1 when divided by N. Is there any formula I can apply?
0
votes
1answer
45 views

Calculate$ (n+m-1)C_n \mod 10^9+7$ efficiently

I want to calculate $(n+m-1)C_n \mod 1000000007$. where $n$ can be between $1$ and $10^9$. $m$ will not exceed $30$. How do I calculate it efficiently.
0
votes
3answers
60 views

Selecting groups of items: How many ways can we divide n students into groups of two?

I have a question very similar to the post in the link below. But, what do we do when we are given a variable for the total number of students, not a constant number? Here is the modified version of ...
-1
votes
0answers
36 views

Distribute coins among N persons [duplicate]

Suppose we have infinite number of coins.Now we need to give some coins to $N$ persons in such a way that product of the number of coins any two adjacent persons have, is not greater than $M$. ...
0
votes
1answer
46 views

Expected value for Head/Tails

There are $N$ coins placed in a line. A coin may be facing head/tail direction with $0.5$ probability. Now I need to find number of pairs of coins $(i,j)$ such that $i<j$ and on index $i$ , I ...
2
votes
1answer
84 views

Extremal set theory problem

What are good bounds(asymptotic bounds preferred) on the cardinality of the largest family $S$, of $m$-element subsets of an $n$-element set, if any pair of elements intersect in a set that has ...
-1
votes
1answer
58 views

probability n! please help it's the only question i don't know how to do on the homework [closed]

write n! in terms of (n-1)! I am not sure what it is asking. I have tried everythng.
5
votes
2answers
54 views

Choosing subsets to cover larger sets

I think this is probably known/easy, but I can't solve it. Consider the set $S=\{1,2,\ldots, n\}$, and let $a<b<n$. What is the minimum number $f(a,b)$ such that there exist $f(a,b)$ subsets of ...
-4
votes
3answers
83 views

Expected number of good pair of coins [closed]

N coins are being put in a line, each of them is either facing Heads or Tail with equal probability.A pair of indices (i,j) is called good coin pair if coin at index i is facing Heads, and coin at ...
2
votes
1answer
22 views

How many ways can I show integer-linear dependence of $n$ vectors with bounded coefficients?

Suppose I have $n$ vectors $(v_1, v_2, \cdots, v_n)$, lets say they are in $\Bbb{R}^2$ for concreteness but they could be in any vector space $V$ where $\dim V < n$. I'm wondering if there is a ...
2
votes
1answer
78 views

Find different sequences of game to find winner

Alice and Bob are having a racing competition to see who is the best runner. They don't want to decide this in a single race, so they choose a number N which is the minimum number of points one of ...
1
vote
1answer
141 views

Count ways to distribute candies

N students sit in a line, and each of them must be given at least one candy. Teacher wants to distribute the candies in such a way that the product of the number of candies any two adjacent students ...
6
votes
2answers
57 views

How many ways to arrange $8$ read beads and $32$ blue beads into a necklace such that at least $2$ blue beads between any $2$ red beads ?

Zaraki wants to use $8$ indistinguishable red beads and $32$ indistinguishable blue beads to make a necklace such that there are at least $2$ blue beads between any $2$ red beads. In how many ways can ...
1
vote
1answer
37 views

Prove that $\sum_0^n({nCr})^2=2nCn$

Prove that $\sum_{r=0}^n({nCr})^2=2nCn$ I don't know how to prove such probems. Any proof by combinatorics?
1
vote
2answers
140 views

Summation of Binomial Theorem

The binomial theorem formula: $$\sum\limits_{k=0}^{n} {n \choose k} = \sum\limits_{k=0}^{n}\frac{n!}{k!(n-k)!} = \sum\limits_{k=0}^{n}\frac{n(n-1)(n-2) \cdots (n-k+1)}{k(k-1) \cdots 2\cdot1}.$$ I am ...
0
votes
3answers
45 views

Probability and counting cards

The problem goes like this: "I am given 7 cards from a regular 52 playing card deck." "Find the probability that there are at least 3 of the cards equally high (e.g. that there are 3 or more jacks). ...
0
votes
1answer
29 views

subset of`{1, …, 2n-1}` contains two numbers `m` and `k` that m + k = 2n or m - k = 0

Let the set A be any subset of{1, ..., 2n-1} where | A | = n + 2. Now we have to prove that the set ...
0
votes
1answer
30 views

Expression of the thresold with expected degree in a Random Geometric Graph

$n$ points ($P_i$) are distributed uniformly on the surface of an unit radius sphere. 2 points are interconnected if the distance between them is $\le r$ (thresold). We call the degree of point $i$ ...
0
votes
0answers
23 views

Permutation combination question

Say that i have 4 variables: $X_1, X_2, X_3$ and $X_4$. and $Y$ is a function of these four variables which uses four operational symbols $(+,-,*,/)$. This could be: $X_1+X_2+X_3+X_4 $ ...
-1
votes
0answers
27 views

Consider the possible function $f : [7] \to [9]$ [duplicate]

How many have f(1) ≠ 5 and are one-to-one? How many have f(i) even, for all i? How many have rng(f) = {5, 6}?
2
votes
2answers
24 views

If $n>m$, then the number of $m$-cycles in $S_n$ is given by $\frac{n(n-1)(n-2)\cdots(n-m+1)}{m}$.

Show that if $n>m$, then the number of $m$-cycles in $S_n$ is given by $$\frac{n(n-1)(n-2)\cdots(n-m+1)}{m}.$$ My doubt Suppose I wish to count the number of $m-$cycles. Then I will get ...
0
votes
1answer
26 views

Combinatorical problem about consecutive values

I have the following problem, quoted directly from Biggs, Discrete Mathematics: A golfer has $d$ days to prepare for a tournament and must practice by playing at least one round each day. In order to ...
0
votes
1answer
42 views

Probabilities/combinations problem.

I am stuck for $4$ days in the following problem: We have $r$ containers and $n$ balls. Every container can contain from $0$ to $n$ balls. How many combinations exist to place the balls in the ...
0
votes
1answer
36 views

Functions involving codomains

Problem: Consider the possible $f: [7]\to[9]$ a) How many have $f(i) $even , for all i? b) How many have rng(f) = {5,6} As far problem a goes, I've only gotten to the answer = 4^7. However I'm not ...
3
votes
1answer
51 views

A inclusion -exclusion related problem

Cicada is an insect with large transparent eyes and well-veined wings similar to the "jar flies". The insects are thought to have evolved 1.8 million years ago during the Pleistocene epoch. There ...
0
votes
2answers
18 views

Counting bijections with a constraint

Let $A$$=${$1,2,3,4,5$} . Find the number of bijective functions $f:A\to$ $A$ if $f(1)=2$. I can't use the formula of bijective functions ( $n!$) , because the $f(1)=2$ is misleading me.