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 (4)

6
votes
5answers
250 views

Permute “aaaaabbbbbccccc” so that no two identical letters are adjacent

This is a follow up question to Application of PIE. How many strings with the letters "aaaaabbbbbccccc" are there so that no two identical letters are adjacent?
0
votes
0answers
69 views

Rado Theorem How do I use it?

Can someone tell me how Rado theorem and/or Ramsey theorem apply to the following problem? Find the smallest positive integer n that satisfies the following: We can color each positive integer with ...
-3
votes
0answers
63 views

Colors Problem: Given Equation [duplicate]

What is the smallest positive integer $n$ that satisfies the following condition: We can color each positive integer with one of those $n$ colors such that the equation $w + 6x = 2y + 3z$ has no ...
2
votes
1answer
76 views

Minimum number of ways to color each integer

I have seen this problem floating around for a while but with no answer. Since the USAMTS deadline has passed, I would really like to see an answer for this. The farthest I got with this was that $n ...
1
vote
1answer
23 views

Transportation mininum cost problem

I've got a bit stuck trying to solve the following problem: A number of transport companies each offer various means of transportation, for example company A offers: ...
0
votes
1answer
38 views

Prove $\binom{N}{k}=\frac{N^k}{k!}\left(1+O(\frac{1}{N})\right)$ when $N \rightarrow\infty$

Can someone help prove the following: $\binom{N}{k}=\frac{N^k}{k!}\left(1+O(\frac{1}{N})\right)$ when $N \rightarrow\infty$. Thanks in advance!
0
votes
3answers
65 views

Probability of Permutations/Combinations

How do you set up the formula for the probability of a permutation/combination? Question: If you have a group of candy with $2$ Snickers, $4$ Kit Kats, and $2$ Butterfingers and you take two pieces ...
2
votes
4answers
71 views

Combination question?

I have question it is a practise question for my textbook. You are given $5$ books and $7$ bookshelves. How many ways are there to place these books on the shelves? (Order matters). I checked the ...
3
votes
1answer
86 views

Some combinatorial identity.

Let $a_1 \ge 0$ and $a_2 \ge 0$ be real numbers and let $n_1 \ge 0$ and $n_2 \ge 0$ be integers. Finally let $m\ge 1$ be another integer. By using the method of generating functions I have shown that ...
18
votes
1answer
600 views

How to prove a double sum is always an integer?

I have verified the following double sum is always an integer for $s$ up to $1000$ via Maple. But I can not prove it. Proofs, hints, or references are all welcome. Thanks! ...
-1
votes
0answers
33 views

Difference between two expressions for combinations with repetition.

While attempting to solve problems that compute the number of combinations with repetition (ie, a store has 4 flavors of ice cream and you are picking 3 with repetitions allowed, how many ways can you ...
0
votes
2answers
93 views

In a unique Soccer series between Earthlings and Martians …

Suppose in a unique Soccer series between Earthlings and Martians, the tournament will continue till a team wins 5 matches. Then the number of ways the series can be won by Earthlings, if no match ...
2
votes
2answers
57 views

Limit of double sum involving binomials

I am trying to get a meaningful interpretation of the behaviour of the following double sum in the limit of a large $t$ and small $p$. I look at its value as a function of $\beta$. Here's the sum: ...
2
votes
1answer
59 views

Simplify a sum of binomial

Is it possible to have a closed form of the following sum: $$\sum_{i=0}^n\binom{n}{i}\binom{n+t-i}{n}$$
2
votes
1answer
56 views

Number of ways to place exactly two kings in each column such that no king attacks another

A regular King in a chess board can attack all its adjacent 8 cells (vertical, horizontal or diagonal). Now you are given a $10 \times n$ chessboard, your task is to place exactly two kings in each ...
-8
votes
1answer
39 views

Number theory system [closed]

The number of four digit numbers strictly greater than 4321 that can be formed from the digits 0,1,2,3,4,5 allowing for repetition of digits is
-1
votes
1answer
31 views

Good, free source for counting (combinations, permutations) and/or probability?

I'm a freshman CS major and find both of these topics really interesting, but I also find them difficult (I've been told this isn't much of a surprise!). I was hoping some of you could direct me ...
0
votes
2answers
32 views

Probability for smallest and greatest

You have to deposit money five times. What is the probability that the first is the greatest and the last is the smallest ? ( five deposits are all different). Answer : 1/20 I did total number of ...
2
votes
1answer
500 views

Probability of finding specific set of coloured balls within larger set of random-drawn balls

In this question I was helped with calculating the probability of drawing specific set of M coloured balls from a set of N coloured balls. Now I am looking for a solution for an extended problem: ...
1
vote
2answers
834 views

In how many ways can one divide 10 people into 4 unequally sized groups?

Many questions on this site involve counting the number of ways one can divide a set of n people into equally-sized groups, but how would one do so for unequally-sized groups? The answers for this ...
9
votes
1answer
68 views

How many positive integers of n digits chosen from the set {2,3,7,9} are divisible by 3?

I'm preparing myself for math competitions. And I am trying to solve this problem from the Romanian Mathematical Regional Contest “Traian Lalescu’', $2003$: Problem $\mathbf{7}$: How many positive ...
1
vote
0answers
54 views

Phase trasition of $f(x)$ on random graph $G(n,p(n))$

Random graph $G(n,p(n))$ and graph $H$, which shown below, are given. I'm in need to find $f(x) : f(x) > 0$, such as: if $lim_{n \to \infty}p(n)f(n) = 0$, then asymptotically almost surely G ...
0
votes
1answer
36 views

Solve the Recurrence

Solve the recurrence $a_k = 2a_{k-1} + 3a_{k-2}$, if $a_0 = 0$ and $a_1 = 8$. I understand how to get the generating function: $$G(x) = \sum_{k \geq0}a_kx^k = a_0 + a_1x + \sum_{k\geq 0}a_kx^k = 8x ...
2
votes
1answer
68 views

How many distinct integer solutions does the inequality $|x_{1}|+|x_{2}|+…+|x_{n}| \leq t$ have?

How many distinct integer solutions does the inequality $|x_{1}|+|x_{2}|+...+|x_{n}| \leq t$ have? We know that: $x_{i} \in Z,\ \forall i \ 0\leq i \leq n \ and \ t\geq0.\ $ I know that if we ...
1
vote
1answer
27 views

Geometric distribution example (making kids until couple has a boy and a girl), need explanation

So the condition is following: a man and a woman want to have kids : girl and a boy. They continue to make kids until they get both genders. What is the expected number of kids? As I remember, the ...
1
vote
0answers
18 views

Same problem solved with linearity of expectation and Hypergeometric distribution. Need explanation…

Here is the problem: There is population of size S. Select two independent samples A and B. A size = n B size = m. What is the expected overlap between A and B? $E$[overlap between $A$ and $B$] $=$ ...
0
votes
1answer
77 views

How to calculate the number of combinations of getting a pair in a deck of 52 cards?

I am confused over calculating the number of ways in which I can select a pair out of a deck of 52 cards, this is how I go about solving the problem, following the definition of a pair in card games, ...
3
votes
1answer
38 views

Ways of getting three of a kind in a 52 card deck

This question has probably been asked before, but just to be clear here, I am NOT asking for the answer, I know the answer. What i want to know is why my solution is not equivalent to the actual ...
10
votes
2answers
152 views

Sets $S_i$ such that $|S_i\cap S_j|\geq4$

Let $A=\{1,2,\ldots,1600\}$, and let $S_1,S_2,\ldots,S_{16000}$ be subsets of $A$ such that $|S_i|=80$ for all $i$. Show that for some $i\neq j$, we have $|S_i\cap S_j|\geq4$. I want to suppose for ...
4
votes
1answer
37 views

Number of ways to choose 6 books out of 20 books such that no 2 are adjacent books

I was trying to do the following question: Describe a bijection between ways of choosing 6 books out of 20 books so that no two adjacent books are selected and a 15-bit sequence with exactly 6 ...
1
vote
2answers
22 views

Total $3$-digit odd number combinations from $1,2,3,4,5,6$

How many three digit numbers can be formed from the digits $1,2,3,4,5$ and $6$, if each digit can only be used once? How many of these are odd numbers? How many are greater than $330$? I've ...
-3
votes
0answers
36 views

Great wisdom is need here…can YOU help? [closed]

a referendum is conducted with twenty five people given the chance to vote yes or no. each ballot box must contain at least 8 votes each how many possible outcomes are there? order of picks do not ...
0
votes
3answers
384 views

Counting arrays with gcd 1

I want to calculate the number of arrays of size $N$, such that for each of it's element $A_i, 1 \leq A_i \leq M$ holds, and gcd of elements of array is 1. Constraints: $1 \leq A_i \leq M$ and $A_i$ ...
1
vote
1answer
16 views

Probability of winning a game similar to bingo

I was trying to do the following question: I have attached the solutions and I am specifically confused about how they got the $${20 \choose 2}$$ the numerator of the first part. I usually post ...
3
votes
1answer
25 views

Combinatorics problem with “at least” condition

I had a regular combinatorcics exercise to solve and I thought it's possible to solve it in two ways but it turned out that only one way is correct. It is: A team of 4 students is to be selected for a ...
1
vote
1answer
20 views

What are the number of possible partitions of a set containing n elements?

This question rises immediately if we try to enumerate the number of possible equivalence relations on a set with n elements.
1
vote
3answers
2k views

The basic of the count

(a) A computer network consists of six computers. Each computer is directly connected to at least one of the other computers. Show that there are at least two computers in the network that are ...
0
votes
1answer
18 views

investing in three stocks with minimum investment

An investor wishes to invest up to ¤12K in three different stocks. Each investment must be made in units of ¤1K. How many different possible investment strategies does he have?
3
votes
1answer
42 views

Combinatorial Problem about putting foxes in a $n\times n$ table

Let $n$ be an integer with $n\geq 2$. $k$ foxes are put into $n \times n$ table, and each $1 \times 1$ square has at most $1$ fox. They are put in such a way that each $2 \times 2$ table has exactly ...
1
vote
1answer
24 views

Find number of pairs satisfying given absolute difference and product

If I'm given absolute difference of two numbers and their product, how can I determine the number of ordered pairs possible? What I have thought is - Total number of pairs possible may be 4, 2 or 0. ...
0
votes
1answer
29 views

Identity of sum of binomial coefficients

I'm struggling to understand the following derivation where $n$ is a positive integer. $$ \sum_{\ell=0}^n {n \choose \ell} 2^\ell \log 2^\ell = n \sum_{\ell=0}^{n-1} {n-1 \choose \ell} 2^{\ell+1}. $$ ...
1
vote
3answers
590 views

What does the “n choose multiple numbers” symbol stands for?

The question is: How many ways can you align 3 red balls, 2 blue balls and 2 yellow balls ...
3
votes
3answers
80 views

How do the answers to combinatorial problems change if instead of 4 different objects we have 4 identical ones?

I think I did the first parts of these correctly, but I really don't know about the last part? Could I just divide all my previous answers by $4!$ If you have $4$ children, $8$ unique fruit, and $8$ ...
0
votes
1answer
28 views

Why is my answer to this multichoose counting problem wrong?

I'm having trouble with the following problem: An ice-cream vendor sells eleven kinds of ice-cream. In how many different ways can I buy six cones, some or even all of which could be the same? I ...
0
votes
1answer
55 views

Combinations. x+y+z=12 [closed]

X+y+z=12 x,y,z are all greater or or equal to 0 and are integers No. of combinations of x,y,z are ............. *note-- (12,0,0) and (0,12,0) are treated as same Please solve this by using formulae ...
0
votes
2answers
21 views

Determine the number of integral solutions of the equation

Let ${x_1 + x_2 + x_3 + x_4}$ = 20 which satisfy: 1 $\leq$ $x_1$ $\leq$ 6, 0 $\leq$ $x_2$ $\leq$ 5, 4 $\leq$ $x_3$ $\leq$ 9, 2 $\leq$ $x_4$ $\leq$ 7. Determine the number of integral solutions. I ...
1
vote
1answer
36 views

Prove or disprove this lemma for Catalan Numbers

Prove or disprove that for all non-negative integers $n$ and $r$ with $r+1$ is less than or equal to $n$, $C(n,r+1)=C(n,r)\times\frac{n-r}{r+1}$.
4
votes
2answers
70 views

Probability of having always flipped more $H$ than $T$ in an infinite coin flip sequence

A biased coin has probability $p \in [0,1]$ of landing heads ($H$) and hence probability $1-p$ of landing tails ($T$). We will flip this coin infinitely many times, obtaining a sequence ...
1
vote
2answers
27 views

How many ways are there to place 7 distinct balls into 3 distinct boxes?

How many ways are there to place $7$ distinct balls into $3$ distinct boxes? is the question I'm confused about. The solution shows that the correct answer is $3^7$. I'm just confused why this is. ...
-1
votes
0answers
11 views

Counting problem: 4 members of a committee that must elect a prez and secretary, …? Use Addition Principle [closed]

A committee composed of Mo, Ty, Ma, and Le is to select a president and secretary. How many selections are there in which Ty is president or not an officer? Use the Addition Principle.