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)

1
vote
1answer
10 views

Looking for a recurrence relation ot combinatorial way to calculate initial number

A flock of birds migrating south flies above seven lakes. Half of the birds in the flock, plus half a bird(I'm guessing the initial flock contained an odd number of birds, say 5, so in the first lake ...
-5
votes
0answers
24 views

circular derangement related to round table [duplicate]

N people are invited to a dinner party and they are sitting on a round table. Each person is sitting on a chair there are exactly N chairs. So each person has exactly two neighboring chairs, one on ...
3
votes
0answers
51 views

Probability of $m$ out of $n$ rolls of a die being among the numbers $1,2,\ldots,m-1$, for some $m$.

Suppose I have a $k$ sided die with the numbers $1,2,\ldots,k$ on each side, and that I roll it $n$ times ($n<k$). What is the probability that there exists an $m\leq n$, so that $m$ of the $n$ ...
12
votes
9answers
2k views

How many ways can seven people sit around a circular table?

How many ways seven people can sit around a circular table? For first, I thought it was $7!$ (the number of ways of sitting in seven chairs), but the answer is $(7-1)!$. I don't understand how ...
0
votes
1answer
32 views

Finding the total number of members in a club with multiple committees [on hold]

In ISI club each member is on two committees and any two committees have exactly one member in common. There are five committees. How many members does ISI club have?
10
votes
1answer
120 views

No sum of three numbers equals another number in set

Consider the set $S=\{1,2,\ldots,1000\}$. What is the maximum size of a subset $S'$ such that for any distinct $a,b,c,d\in S'$, we have $a+b+c\neq d$? We can choose $S'=\{333,334,335,\ldots,1000\}$, ...
0
votes
1answer
51 views

Circular arrangement and inclusion-exclusion principle

$4$ people are invited to a dinner party and they are sitting on a round table. Each person is sitting on a chair there are exactly $4$ chairs. So each person has exactly two neighboring chairs, one ...
-2
votes
1answer
44 views

Show that $x\cdot x(k) = x(k+1) + k\cdot x(k)$ [on hold]

Show that $x\cdot x(k) = x(k+1) + k\cdot x(k)$ where $x(n)$ is the falling factorial. $$x(n) = x(x-1)(x-2) \cdots (x-n+1)$$ $$x(k+1)+kx(k) = (x)(x-1)(x-2)\cdots(x-k+2) + ...
2
votes
0answers
41 views

Edges of a permutohedron

Consider a permutohedron $P_n$ (this is a polytope which is a convex hull of $n!$ points, which are obtained from $(1,2,...,n)$ by all possible permutations of coordinates). I have to prove the ...
4
votes
1answer
83 views

The Island in the Miracle Sea. (Christmas edition)

To all of you who love math like me, I have this puzzling riddle that I hope you find interesting : On Christmas Eve just after midnight, Santa was riding his sleigh over the Miracle Sea when ...
0
votes
1answer
28 views

Extension of hypercube

I understand the notion of a hypercube as a graph with vertex set $\{0,1\}^{n}$ and an edge between two vertices if their vertices differ in one co-ordinate is there an extensive body of work on the ...
1
vote
3answers
60 views

Why is this combinatoric solution not correct?

I'm trying to solve the following problem: Balls of the colors red, orange, yellow, green, blue, indigo, violet (7 colors, 1 ball per color) are placed into 4 different boxes A,B,C,D so that no box ...
5
votes
0answers
86 views

A set of 19 numbers that are at most 93, and a set of 93 numbers that are at most 19, have equal sumsets [on hold]

If $x_1, x_2, ..., x_{19}$ are natural numbers lower or equal than 93 and $y_1, y_2, ..., y_{93}$ are natural numbers lower or equal than 19 then there is a non zero sum of some $x_i$ which is equal ...
0
votes
2answers
32 views

distribution probability question involving binary functions for certain n<2^10

For any positive integer n, let G(n) be the number of pairs of adjacent bits in the binary representation of n which are different. For example, G(10)=3 because the bits of $1010_2$ change at all ...
0
votes
1answer
53 views

Marriage theorem. Proof. [on hold]

I am asking for advice: Let G be the bipartite graph $(V_1, E, V_2)$ with each vertex in $V$, of degree at least $d (> 0)$ and each vertex in $V_2$ of degree $d$ or less. Show that if each vertex ...
1
vote
1answer
26 views

Find every possible distribution of the x elements considering a constraint on one of them

Considering a number r of triplets { a, c, i } I'd like to know which procedure / math field should I use to calculate every ...
3
votes
2answers
90 views

Christmas protocol

Since holiday season is coming, here is a little practical-purpose combinatorics question. Lots of group of friends or families practice the random variant of Secret Santa, where each member buys a ...
3
votes
3answers
277 views

Method for Counting the Divisors of a number

I need to find the number of divisors of 600. Is there any other way to solve the problem, apart from writing them down and counting??
1
vote
2answers
66 views

Combinatorics in a Party.

There are 12 persons in a dinner party, they are to be arranged on two sides of a rectangular table. Supposing that the master and the mistress of the house have are always facing each other, and ...
5
votes
1answer
90 views

Solving a circular permutation problem with recursion

N people are invited to a dinner party, and they are sitting at a round table. Each person is sitting on a chair; there are exactly N chairs. So each person has exactly two neighboring chairs, one on ...
-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 ...
1
vote
2answers
44 views

Permutation and combination theory

The number of ways of distributing 12 identical oranges among 4 children so that every child gets atleast 1 and no child more than 4 is
-8
votes
1answer
38 views

Number theory system [on hold]

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
2
votes
1answer
55 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 ...
-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
31 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 ...
7
votes
6answers
322 views

Prove that $\binom n2 + \binom {n-1}2$ is always a perfect square

Prove that if $n$ is a positive integer and $n >1$: $$\binom n2 + \binom {n-1}2$$ is always a perfect square. I know we need to turn that into a binomial, but I can't follow how. Please note I'm ...
1
vote
0answers
31 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
2answers
49 views

Forming a committee

Suppose a committee must be formed from a group of 15 professors and 10 administrators. How many committees can be formed if the committee must consist of 5 professors and 5 administrators? Update 1: ...
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 ...
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$] $=$ ...
-3
votes
0answers
36 views

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

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 ...
1
vote
1answer
26 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
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 ...
4
votes
1answer
35 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
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 ...
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 ...
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.
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?
2
votes
1answer
58 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}$$
0
votes
2answers
41 views

Algebra of Combinations.

How many solutions are there to the equation $$ x_{1} + x_{2} + x_{3} + x_{4} = 28\ {\large ?}\qquad\mbox{if}\qquad x_{1} \geq 3\,,\ x_{2} \geq 3\,,\ x_{3} \geq 5\ \mbox{and}\ x_{4} \geq 5. $$ $x_{1}, ...
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 ...
0
votes
1answer
28 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}. $$ ...
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 ...
1
vote
1answer
35 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}$.
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. ...
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$ ...
2
votes
1answer
67 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 ...