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)

5
votes
3answers
198 views

Permutation: Distribute 10 distinct items in 3 boxes: one box contain odd number, one box even number object , and all boxes at least one item.

I wish to distribute $10$ distinct toys to my children $A, B$ and $C$. Each child must get at least one toy, but $A$ must receive an even number of toys, while $C$ must receive an odd number. ...
0
votes
1answer
59 views

Prove $\sum_{k=m}^n {k \choose m} = {n+1 \choose m+1}$ [duplicate]

I am trying to determine whether $\sum_{k=m}^n {k \choose m} = {n+1 \choose m+1}$, so far I am assuming that this is a false statement, but was wondering if there was a proof indicating this is a true ...
0
votes
1answer
88 views

How many quadrilaterals can be made with these line segments if circles can be inscribed in the quadrilaterals made$?$

There are $8$ line segments of lengths(in cm) $1,2,3,4,5,6,7,8$.How many quadrilaterals can be made with these line segments if circles can be inscribed in the quadrilaterals made$?$ I made a try ...
0
votes
1answer
33 views

The minimum number of ordered pairs $(x,y)$so that two pairs will be identical.

There are two sets $A=\left\{a_1,a_2,a_3,...,a_m\right\}$ and $B=\left\{b_1,b_2,b_3,...,b_n\right\}$ of real numbers.The minimum number of ordered pairs $(x,y),x\in A,y\in B$ that must be written,is......
1
vote
1answer
76 views

Prove that if $n\geq1$ then $\binom{2n}{2}=$ [duplicate]

Prove that if $n\geq1$ then $$\binom{2n}{n}=\sum_{k=0}^{n}(\binom{n}{k})^2$$ This is what I have so far: By the Binomial Theorem: $$\binom{2n}{n}=\frac{(2n)!}{(2n-2)!n!}=\frac{2n!~}{n^2(n-1)^2(n-...
1
vote
2answers
60 views

Number of squares and rectangles in a box

Consider the above picture . Total number of rectangles and squares can be determined using $\binom m2\binom n2$ ,where $m$ represents number of lines in horizontal and $n$ represents the same but in ...
1
vote
2answers
41 views

$m$ red and $n$ blue balls in a bag. Probability of acquiring a run of $k$ balls without replacement.

I have a bag containing $m$ red and $n$ blue balls. I draw balls one by one without replacement. Say I wish to find the probability of acquiring a run of $k$ balls, without replacement, before ...
2
votes
3answers
44 views

Prove that $\sum_{r=1}^n r\binom n r^2 = n\binom{2n-1}{n-1}$ [duplicate]

Prove that $\sum_{r=1}^n r\binom n r^2 = n\binom{2n-1}{n-1}$ I tried: $\sum_{r=1}^n r\binom n r^2 = n\sum_{r=1}^n \binom {n-1}{r-1}\binom n r$ using the identity $\binom n r = \frac n r \binom {n-1}{...
2
votes
2answers
290 views

In how many ways can you arrange all coins in a row?

A jar contains 5 quarters, 2 nickels, and 4 pennies. In how many ways can you arrange all coins in a row so that each arrangement: (1) begins with a quarter? (2) all quarters together? ...
3
votes
3answers
179 views

How many nonnegative integer solutions does the following equation have: $x + y + z = 15$

How many nonnegative integer solutions does the following equation have: $x + y + z = 15$ (1) if $1 \le x \le 6$ (2) if $x \ge 2$ and $y \le 3$ (3) if $x \ge 3$, $y \ge 2$, and $1 \le ...
0
votes
1answer
44 views

Number of ways to create “trios” from the numbers $1{-}20$

Lets say you have the numbers $1{-}20$: $$1,2,3,4....19,20$$ and you need to create trios (combinations of three different numbers, order ignored). How many different ways can you arrange these ...
0
votes
1answer
32 views

Alternate definition of bijection: If $f$ and $g$ are both injective, then $f$ is bijective.

Suppose $f: A \to B$ and $g: B \to A$ where $g(f(a))=a$ for all $a \in A$, and $f(g(b))=b$ for all $b \in B$. We know that since $f$ has a left inverse, it is injective. But notice that $g$ also has ...
1
vote
3answers
148 views

How many ways are there to arrange five cards in a row so that each arrangement begins or ends with a club?

How many ways are there to arrange five cards in a row so that each arrangement (1) begins or ends with a club? (2) contains exactly two kings? I have an idea of where to start with Question ...
0
votes
1answer
169 views

prove by induction that $\sum_{k=0}^n {n \choose k} = 2^n$ [duplicate]

I have proved previously that $\sum_{k=0}^n {n \choose k} = 2^n$ by using the binomial theorem. I was wondering, however if it were possible to solve this using a proof of induction.
4
votes
4answers
2k views

Ways to arrange the letters in **BOOKKEEPER** if vowels must appear in alphabetical order?

Question How many different ways can I arrange the letters in BOOKKEEPER if vowels must appear in alphabetical order? How many different ways can I arrange the vowels? That would be 1 way. No I ...
0
votes
1answer
38 views

ways to distribute 12 distinct books to 6 kids so that each one gets the same number of books

I know off the bat that each kid gets two books. Then I do the following, $${12 \choose 2}{10 \choose 2}{8 \choose 2}{6 \choose 2}{4 \choose 2}{2 \choose 2}$$ I was told that I didn't have to divide ...
0
votes
0answers
23 views

Sorting by k-ary Comparisons

I found this paper and was trying to decipher it to derive the minimum number of sortings of n elements with k elements in each query that would solve for the entire linear order. The paper defines: ...
2
votes
1answer
50 views

Drawing balls from urn with unequal probability

Consider an urn that has $n$ numbered balls such that the probability of drawing ball $i$ is $p_i$. We keep drawing balls from the urn with replacement until we have seen all the balls. What is the ...
1
vote
2answers
44 views

Combinatorial Probability Proof for Dice Rolls

Here is my solution: There are $\binom{6}{2}$ ways for two numbers to appear. On each of the 4 rolls of the die, there are two possible outcomes giving $\binom{6}{2}$$\cdot$$2^4$ possible outcomes ...
3
votes
2answers
60 views

Prove that the probability that the sum of the digits used leaves the remainder 2 when divided by $4$ is $\frac{1}{4}.$

A number of 5 digits is written down at random.Prove that the probability that the sum of the digits used leaves the remainder 2 when divided by $4$ is $\frac{1}{4}.$ The sum of digits must be like 6,...
2
votes
1answer
86 views

Choosing $100$ numbers in which one of the chosen number is divisible by another one

Prove that if $100$ integers are chosen from $1,2, \ldots, 200$, and one of the integers chosen is less than $15$, then there are two chosen numbers such that one of them is divisible by the other....
0
votes
2answers
32 views

Simple permutations

In how many ways can the letters of the word E L E E M O S Y N A R Y be arranged so that the S is always immediately followed by a Y ? the answer was 11*10!/3! how is that the answer? Is it because ...
0
votes
0answers
41 views

Is the following statement about tree true?

For a rooted tree T of oder n, what is the probability of that T contains a balanced tree of order 7? For example, there are total of 719 rooted trees of order 10, IF among all those 719 rooted trees, ...
1
vote
2answers
91 views

Total possible ways to arrange 40 identical balls in 3 different boxes

How many ways are there to arrange 40 identical balls in 3 boxes, such that there is at least 1 ball in each box and the number of balls $n$ in a box is not a multiple of 10. I already know how to ...
-3
votes
1answer
40 views

Find maximum number of strings. [closed]

Given a Finite Automata with fix number of input symbols $k$. What is the maximum number of strings of maximum length $n$ it can accept. How to think about the ...
1
vote
0answers
26 views

Difference between power and falling power

I have the following question about the difference between a falling power equation and a very similar equation using normal power: Let $m$ and $C$ be some positive integer constants, where $C > m$,...
0
votes
2answers
53 views

John along with his wife,parents and four children of which two are boys and two are girls,put up at a rest house with four bed rooms for a night.

John along with his wife,parents and four children of which two are boys and two are girls,put up at a rest house with four bed rooms for a night.There are beds for two persons in each room.If either ...
0
votes
0answers
43 views

Symmetric system of equations given by sums of powers

Let $u_k = \alpha_1^k + \cdots + \alpha_n^k$, where $\alpha_i \in \mathbb{C}$ and $n \ge 1$. How do I find $\alpha_i$ given that $u_k = k$ for $k = 1, \dots, n$? If it helps, I suspect that $\...
0
votes
1answer
42 views

Urn Problem - Number of Permutations

I have a quick question and would be very gladful for any help. We view an Urn Problem, where we put back the balls after each drawing. Let $n \in \mathbb{N}$ be the number of balls in the urn and ...
0
votes
2answers
35 views

Combinatorics - Number of combinations when you know some of the numbers.

If you have a safety lock with 4 "fields" and numbers from 0-9 in each of them, the number of combinations possible in obviously $10^4$, but what if you know that exactly two of the numbers are 4? I ...
0
votes
1answer
28 views

Product of the digits occupying the five consecutive positions is divisible by $5$.

Find the number of permutations of $1,2,3,4,5,6,7,8$ taken all at a time without repetition in which the product of the digits occupying the five consecutive positions is divisible by $5$. In this ...
0
votes
0answers
24 views

Two 5-card straights and Trips from 14 of 52 cards

This task is the subtask of the overall calculation attempt of 3-combination hands when dealt 14 cards of the standard 52-card deck. In order to have trips as a 3-card hand we must have at least ...
1
vote
1answer
58 views

Using Combinatorial proof to conclude $\binom{2n}{n} = 2 \binom{2n-1}{n-1}$

The question given states: Let x be an element of a set A of size 2n. Among the n-element subsets of A count those containing x and those omitting x. Conclude that $\binom{2n}{n} = 2 \binom{2n-1}{n-1}...
1
vote
0answers
54 views

Combinatorics Reasoning

So i was given a question that begins like this. How many ways are there to buy 10 pieces of candy from an (unlimited) supply of three kinds: jelly beans, chocolate almonds and skittles with at least ...
0
votes
1answer
38 views

Calculate simple bound on coupon collector

I came across this paper which gives bounds on weighted coupon collector problem. This paper, in short, tries to prove various lower and upper bounds for the expected number of draws till we see all ...
0
votes
1answer
89 views

How many distinct codes of this specific form are there?

A coded message from a CIA operative to his Russian KGB counterpart is to be sent in the form Q4ET, where the first and last entries must be consonants; the second, an integer 1 through 9; and the ...
0
votes
1answer
88 views

Counting sets two different ways

I have been stuck on this problem and I was hopeing that someone could let me know if I am doing it right. k, m, n are integers $0 \le k \le m \le n$ $S$ is a set of size $n$ $n \choose k$${n - k}...
5
votes
1answer
54 views

Given Sequence of Numbers find number of combinations

I have the sequence of numbers $1,2,4,8,16,\ldots$. This is an infinite sequence. So my problem is that if I have any positive integer value, $x$, what are the possible ways that I can write $x$ as ...
1
vote
1answer
174 views

How many ways are there to choose 10 coins with at least 3 nickels but no more than 2 quarters?

A piggy bank contains 50 pennies, 40 nickels, 30 dimes, and 20 quarters. (1) How many ways are there to choose 10 coins with at least one of each type? (2) How many ways are there to choose 10 coins ...
0
votes
3answers
40 views

Divide set of numbers into twosub sets with equal totals

Given a finite sequence of natural numbers. Determine wether it is possible to divide the numbers into two sets such as totals of both sets are equal. Show one variant of such distribution. Is there ...
1
vote
0answers
38 views

Revealed preference rank rule: variation on horse race problem

Suppose there are x number of objects to be ranked. Then there are x[(x-1)/2] possible comparisons of these objects. Only subsets of x can be evaluated for comparisons and there is always one most and ...
0
votes
1answer
153 views

How many travel options does she have? [closed]

Meredith wants to visit Chicago, New York, Phoenix, San Diego, El Paso, San Antonio, San Jose, and Boston. If she decides to visit some, all, or none of these cities, how many travel options does she ...
1
vote
2answers
35 views

choosing N object from set of M>N maximizing overall ratio value/weight

I have a set of M objects each with a certain value and weight. From this set I want to take out N objects ($N<M$ of course) and maximize the ratio: total value of the N objects / total weight of ...
3
votes
1answer
101 views

Finding the number of non-decreasing sequences.

A sequence is non-decreasing if $k_1 \leq k_2 \leq k_3$. Now I need to find the number of non-decreasing sequences of length-$n$ sequences from $\{1,2,....m\}$ I basically see it as sum of the ...
0
votes
2answers
90 views

Permutations without repetition pattern (algorithm)

Disclaimer: I haven't done math in a decade. Sorry if this is not very scientific Hello, I am writing a computer program, that is supposed to return the number of all permutations of an input string,...
0
votes
2answers
60 views

what is the probability that the two tallest boys are in different teams?

If $22$ boys are randomly divided into two teams;containing $11$ boys each,then what is the probability that the two tallest boys are in different teams? Probability that the two tallest boys are in ...
1
vote
2answers
43 views

The number of ways in which a candidate can secure $40\%$ marks in the whole examination is $\binom{245}{240}-6\binom{144}{139}+15\binom{43}{38}$.

In a certain examination of $6$ papers each paper has $100$ marks as maximum marks.Show that the number of ways in which a candidate can secure $40\%$ marks in the whole examination is $\binom{245}{...
1
vote
1answer
41 views

Induction with floor limits

I ran into an exercise in a book that asked the following: Prove that $$S(n) = \sum_{\ell=0}^{[n/2]}\binom{n}{2\ell}p^{2\ell}(1-p)^{n-2\ell} = \frac{1+(1-2p)^n}{2},$$ where $[x] =$ the floor ...
1
vote
0answers
53 views

Degree/diameter problem for the even girth case

Let $G$ be a graph with girth $g$, minimal degree $\delta$, maximal degree $\Delta$, and diameter $D$. Define $$n_0(g,\delta) := \begin{cases} 1 + \delta + \delta(\delta-1) + \cdots + \delta(\delta-1)...
1
vote
1answer
32 views

$3$ variants of exam paper distributing in $2$ rows.

Three variants of exam paper are to be given to $12$ students. In how any ways can the students be placed in $2$ rows of $6$ each so that there should be no identical variants side by side ...