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
2answers
66 views

definition of a graph

I have two questions; What is the name of the graph (or circuit) which goes along the outer vertices of existing nodes. What will be the formal definition of that graph. for the ...
0
votes
1answer
78 views

Question with balloons!

I have $20$ different balloons numbered from $1$ to $20$. A. If I randomly split the balloons to pairs, when the order is not important, What is the probability that in each pair there will be an ...
1
vote
1answer
47 views

Question with cups!

OK this is a homework question, but I'm really having troubles and in need for help. I have 6 cups of different sizes and 6 plates when each plate suits one cup. If we randomly place the cups on ...
1
vote
1answer
24 views

Combinatorics Question, drawing from a pot

Four children write their name on a piece of paper, put these pieces of paper in a pot and then draw one piece of it after having mashed up the pieces. What is the probability that: a) Each child ...
1
vote
2answers
728 views

I can't figure out this combinatorics problem… Or at least why my solution doesn't work.

If the only contents of a container are 10 disks that are each numbered with a different positive integer from 1 through 10, inclusive. If 4 disks are to be selected one after the other, with each ...
1
vote
3answers
2k views

Recurrence relation for the number of $n$-digit ternary sequences with no consecutive $1$s or $2$s

Find the recurrence relation for the number of $n$-digit ternary sequences with no consecutive $1$'s or $2$'s. The solution is $$ a_n = a_{n-1} + 2a_{n-2} + 2a_{n-3} + 2a_{n-4} + \dots. \tag1 $$ ...
4
votes
2answers
119 views

How many $6$-digit positive integers are there in which the sum of the digits is at most $51$?

How many $6$-digit positive integers are there in which the sum of the digits is at most $51$?
1
vote
4answers
101 views

At least two semesters when this professor had identical teaching programs?

A college professor has been working for the same department for $30$ years. He taught two courses in each semester. The department offers $15$ different courses. Is it sure that there were at ...
6
votes
1answer
189 views

how to prove $\sum _{|k|\lt\sqrt m}\binom{2m}{m+k}\ge2^{2m-1}$

how to prove $$\sum _{|k|\lt\sqrt m}\binom{2m}{m+k}\ge2^{2m-1},\forall m\ge1$$ Thanks in advance .
4
votes
1answer
138 views

Probability and combinatorics on tetahedron faces.

Let it be a tetrahedron with the numbers $1$,$2$,$3$ and $4$ on its faces.The tetrahedron is launch $3$ times. Each time, the number that stays face down is registered. $1$)In total how many ...
2
votes
1answer
85 views

Proving a bipartite graph is never factor-critical

A graph is called to be factor-critical if $G-v$ has a perfect matching for any vertex $v$ of $G$. Prove that a bipartite graph is never factor-critical.
5
votes
3answers
81 views

Number of choices in a 52-set of cards

Given a set of 52 playing cards (4 suits, 13 cards of each type numbered 1-13). In how many sets of 5 cards there is a pair with the same number and a different suit (considering that the rest 3 ...
1
vote
1answer
101 views

Counting Boys and Girls in a Team

There are 12 children and are being divided into two teams to play a game. $(a)$ In how many ways can you divide 12 children, 6 boys and 6 girls, into two teams to play a game, if the teams are called ...
4
votes
4answers
1k views

How to calculate the number of pieces in the border of a puzzle?

Is there any way to calculate how many border-pieces a puzzle has, without knowing it's width-height ratio? I guess it's not even possible, but I am trying to be sure about it. Thanks for your help! ...
7
votes
0answers
442 views

Is there a Steiner system S(6,9,45)?

Background: the Belgian Lottery switched its main game this year to a draw of 6 balls out of a pool of 45, plus a bonus number which doesn't matter for the sake of this question. Assuming someone ...
2
votes
1answer
612 views

Algorithm to find all the possible cuts in a graph

Is there any efficient algorithm which can help me to list out all the cuts in an undirected weighted graph. I want to find out what are all the possible cut sets with source or one of the nodes on ...
3
votes
1answer
105 views

An ordering different from the Gray order (digits change by 1 at each step)

Given $A=\lbrace x_n,\ldots x_1\rbrace$. How would I construct an ordering on the subsets of $A$ such that the immediate successor of a subset is obtained by either adding or deleting one element, and ...
1
vote
2answers
312 views

Combinatorial way of sum of digits

I just started my combinatorics course and I am having trouble with a few exercises. How many numbers are there in the range $[3000, 8000]$ that the sum of their digits is 20? I tried ...
10
votes
1answer
209 views

Chess board problem

Is it possible to write the numbers 1, 2, ..., 25 on the square of a 5 by 5 chess board (one number per square) such that any two neighbouring numbers differ by at most 4? (Two numbers are neighbours ...
4
votes
1answer
50 views

Combinatorics question about addition

I noticed the following happening and I wonder if it can be proved: Assume $x_1, \ldots, x_n$ are positive integers and $h$ is their least common multiple. Now assume $$a_1x_1 + \cdots a_nx_n > ...
5
votes
3answers
263 views

How to show that all points are inside of unit circle?

There are $n$ points on the plane. Any $3$ of them are inside of a unit circle. How to show that all points are inside of unit circle? It is needed to prove that if there is a unit circle for each ...
2
votes
0answers
193 views

Number of distributions of $r$ distinct objects into $n$ different boxes

Find an exponential generating function for the number of distributions of $r$ distinct objects into $n$ different boxes w/ exactly $m$ nonempty boxes I'm not sure about the solution, but this is ...
1
vote
0answers
77 views

Proliferating Platonic Dice

An unbiased single 4-sided die is thrown and its value, T, is noted. T unbiased 6-sided dice are thrown and their scores are added together. The sum, C, is noted. C unbiased 8-sided dice are thrown ...
1
vote
3answers
126 views

Generating function with quadratic coefficients.

$h_k=2k^2+2k+1$. I need the generating function $$G(x)=h_0+h_1x+\dots+h_kx^k+\dots$$ I do not have to simplify this, yet I'd really like to know how Wolfram computed this sum as ...
1
vote
3answers
86 views

Simplify the Expression $\sum _{ k=0 }^{ n }{ \binom{n}{k}}i^{k}3^{k-n} $

I should simplify the following expression (for a complex number): $$\sum _{ k=0 }^{ n }{ \binom{n}{k}}i^{k}3^{k-n} $$ The solution is $(i+\frac{1}{3})^n$,but i don't quite get the steps. If would be ...
2
votes
2answers
64 views

Finding almost unique sets

Is there an efficient algorithm to find a group of sets, where all the sets each have the same number of elements and differ from each other by exactly one element, such that the number of unique ...
2
votes
0answers
193 views

Combinatorics: Selecting non-adjacent subsets or objects arranged in a circle

Lets say you have a circular table that seats $n$ people and $b\lt n -1$ identitcal boys. If you were to divide the boys into $k$ teams of size $\geq 1$, how many ways are there to seat the boys so ...
2
votes
0answers
41 views

Characterization of $\lambda,\mu\vdash n$ for which $\displaystyle{n\choose\mu}\mid{n\choose\lambda}$

In view of this question, I was wondering about general characterizations of $\mu,\lambda\vdash n$ for which $${n\choose\mu}\,\left|\,{n\choose\lambda}\right.,$$ (see multinomial coefficient and ...
3
votes
1answer
408 views

Intersecting set systems and Erdos-Ko-Rado Theorem

Suppose you have an $n$-element set, where $n$ is finite, and you want to make an intersecting family of $r$-subsets of this set. Each subset has to intersecting each other subset. We may assume $r$ ...
3
votes
2answers
308 views

Number of necklaces

If we have $3$ white, $4$ red and $5$ green pearls, how many distinct necklaces can be formed? I am also interested whether there is a general formula for necklaces that have $a_i,i=1,2,\dotsc,m$ ...
1
vote
2answers
59 views

In how many ways can $4$ subjects be chosen by $2$ students…

I came across the following problem : In how many ways can $4$ subjects be chosen by $2$ students so that each student should take at least one subject? I do not know how to tackle it.Can ...
3
votes
1answer
91 views

computing a limit of a ratio of derangements

Fix $m$. Consider $\lbrace 1,\ldots ,n\rbrace$. Let $a_1\dots a_n$ be a permutation of this set. How many permutations are there such that $a_i\not=i$ for all $i$ and each $i$ travels at most $m$ ...
1
vote
1answer
161 views

Balls, Bags, Partitions, and Permutations

We have $n$ distinct colored balls and $m$ similar bags( with the condition $n \geq m$ ). In how many ways can we place these $n$ balls into given $m$ bags? My Attempt: For the moment, if we assume ...
2
votes
3answers
92 views

Find different ways. Combinatorics problem.

In how many ways 10 identical blue marbles and 5 identical green marbles be arranged in a row so that no 2 green marbles be together? I know this is star and bars problem but, I am not getting to the ...
1
vote
3answers
82 views

How many ways are there to fill $k$ slots with numbers ranging from $1$ to $n$, if the numbers are in nondecreasing order?

How many ways are there to fill $k$ slots with numbers ranging from $1$ to $n$, if the numbers are in nondecreasing order? I heard the answer was ${n + k - 1 \choose k}$ but I can't work out how to ...
1
vote
3answers
182 views

finding the number of subsets and functions of $S_n$

Let $S_n = \{1,2,\ldots,n\}$ (a) for any positive integer $n$, find the number of subsets of $S_n$ which contain 1. I think this would be $2^{n-1}$ it seems to work when I test a few examples, ...
2
votes
3answers
153 views

A question to be solved via the Pidgeonhole Principle [SOLVED]

Question: Let $n_1, n_2, \cdots, n_t$ be positive integers. Show that if $n_1 + n_2 + \cdots + n_t - t + 1$ objects are placed into $t$ boxes, then for some $i$, $i = 1, 2, \cdots, t, $the $i$th box ...
0
votes
1answer
31 views

$a$ people each throw one $b$-sided die. How many outcomes exist where person 1 rolls higher than everyone else?

Let there be $a$ people (at least two) playing a game where each person rolls a $b$-sided die. I want to know how many outcomes exist where the first player rolls higher than anything anyone else ...
1
vote
1answer
80 views

Is there efficient way of finding last number in following sequence

"Imagine the sequence lying on a circle. Take every second number in the sequence. Continue the process until you finish" Is there efficient way of finding last number in following sequence : we ...
11
votes
3answers
260 views

Problem about subsets of $\{1, 2,\dots,n\}$

Let $A=\{1, 2,\dots,n\}$ What is the maximum possible number of subsets of $A$ with the property that any two of them have exactly one element in common ? I strongly suspect the answer is $n$, but ...
0
votes
2answers
188 views

Countable or uncountable

(1) $C$ is the set of all circles $C(z,r)$ with $z\in\mathbb{Q}\times\mathbb{Q}$ and $r\in\mathbb{Q}^+$. What is the cardinality of $C$? (2) Let $S$ be the set of all sequences ...
0
votes
2answers
344 views

Finding the maximal complete subgraph which contains no monochromatic triangles of a complete graph

Given a 2-coloring of $\ E(K_n)$ such that a red edge belongs to no more than one unique Red triangle, show that $\exists \ K_k \subset K_n$ which contains no Red triangle, with $\ ...
0
votes
1answer
58 views

How to get calculate ratio and compare between two

I am making report, I need help finding who performed best. I have 3 workers, and they are assigned number of work/task to do. but but tasked assigned to each of them are not same numbers. How can ...
5
votes
1answer
358 views

Counting Balanced Brackets with a twist

I have $n$ "1"s written as a sum: $1+1+1+\dots+1$, and proceed to add some brackets to the sum. Call the modified sum "good" if the brackets are balanced and not redundant*. [Since in fact placing any ...
1
vote
2answers
556 views

finding 2-element subsets of $S_n$ which contain 2?

For any positive integer $n$ let: $$S_n = \{1,2,\ldots,n\}$$ (a) for any integer $n \ge 2$, find the number of 2-element subsets of $S_n$ which contain 2. (b) for any integer $n \ge 2$, find the ...
1
vote
3answers
64 views

Examples of Partially Ordered Sets

I was if anyone could come up with some good examples of partially ordered sets with exactly $3$ maximal elements. For example: all proper subsets of $[3]$, the maximal elements are ...
1
vote
1answer
108 views

Determining Stirling number

In the first part of the question I was asked to find the exponential generating function for $s_{n,r}$, the number of ways to distribute $r$ distinct objects into $n$ (a fixed constant) distinct ...
9
votes
1answer
264 views

A question about “binary numbers in arbitrary bases”

Here's a problem that I had come up with some time ago: Let a "binary number in base $n$" refer to a natural number whose representation in base $n$ consists of only $0$'s and $1$'s. Prove that ...
0
votes
1answer
237 views

Prove a sum involving multinomial coefficients

I need to prove that if n and m are positive integers, then $$ \sum_{k_1+...+k_m}\binom{n}{k_1, ..., k_m}(-1)^{k_2+k_4+...+k_{2l}}$$ is equal to 0 if m =2l, and is equal to 1 if m = 2l + 1.
1
vote
0answers
575 views

Lazy caterer's sequence, cutting pizza into most pieces with n straight cuts. Graph theory proof.

is there a way to solve this problem using graph theory? I used Euler's formula to find that when you use the method in which every new line intersects the old line in different places gives you ...