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
61 views

the sum of all four digit multiples of 6

The sum of all four digit multiples of $6$ is equal to: A. $8~274~489$ B. $8~247~498$ C. $8~241~996$ Can you help me with this question? I've tried $$S_n= \frac{n(a_1+a_n)}{2}$$ with $...
1
vote
4answers
90 views

Expected number of rolls

A fair m-sided dice is rolled and summed until the sum is at least N. What is the expected number of rolls? In other words what is the number of rolls if we roll a m-sided dice and the sum of rolls ...
25
votes
6answers
39k views

Combination of smartphones' pattern password

Have you ever seen this interface? Nowadays, it is used for locking smartphones. If you haven't, here is a short video on it. The rules for creating a pattern is as follows. We must use ...
3
votes
1answer
37 views

Uniqueness of graph neighbourhood sizes

I was thinking about graphs the other day, and had the following questions which I suppose fall under the topic of graph reconstruction. I am not very familiar with the literature, so in case this ...
0
votes
1answer
41 views

How to find the General expression of $\sum_{k=0}^ {\lfloor n/3\rfloor} {n \choose 3k}$ [duplicate]

Well as the title says I'm having problems trying to derive a general expression for this sum which involves cubic roots of unity $$\sum_{k=0}^ {\lfloor \frac n 3\rfloor} {n \choose 3k}$$ Need help ...
1
vote
1answer
37 views

Probability of picking balls with same color with replacement and without replacement

This is one of our probability exercise: We have an urn with m green balls and n yellow balls. Two balls are drawn at random. What is the probability that the two balls have the same color? (...
1
vote
1answer
85 views

Counting the number of partitions

Let $P$ be a set of $7$ different prime numbers and $C$ a set of $28$ different composite numbers each of which is a product of two (not necessarily different) numbers from $P$. The set $C$ is divided ...
1
vote
1answer
58 views

Proving a polynomial with binomial coefficients has non-real roots

I have the following family of polynomials: $$p_n(x) = \sum_{k=0}^n {n \choose k} \frac{n+2}{n+2-k} x^k$$ I conjecture that it has non-real roots for all $n \geq 2$. This holds for all the small ...
4
votes
3answers
77 views

Probability question - how many cycles before all items are chosen

I have a container of 100 yellow items. I choose 2 at random and paint each of them blue. I return the items to the container. If I repeat this process, on average how many cycles will I make ...
2
votes
1answer
434 views

Let $A$ be the set of all $4$ digit numbers $a_1a_2a_3a_4$ such that $a_1 < a_2 < a_3 < a_4$, then what is $n(A)$ equal to?

How can you solve this problem relatively quickly using combinatorics? I found it really interesting. Let $A$ be the set of all $4$ digit numbers $a_1a_2a_3a_4$ such that $a_1 < a_2 < a_3 < ...
1
vote
1answer
37 views

Finding the combination where p of the items are identical.

Suppose we have $n$ objects in which $p$ items are identical. Of course, $n-p$ elements are distinct. Then what is the combination of $n$ objects taken $r$ at a time? That is, what is $C(n,r)$, but ...
1
vote
0answers
58 views

What is the Star of David theorem?

I came across a MathWorld entry for the Star of David Theorem, but it doesn't provide much context. I have never heard of this before, can somebody explain its significance and any applications it ...
4
votes
1answer
64 views

Splitting Line Segments and Finding Expected Value

Consider a line segment which has a length of $2n-3$. It is split into $n$ segments at random. It is guaranteed that $n\ge 3$ and $n\in \mathbb{Z}$. These smaller lines are then used as the sides of a ...
0
votes
0answers
29 views

Counting balls in face centred cubic close packing

Possibly too easy for stack exchange, but... Consider a cubic close packing, or face centred cubic, arrangement of balls or radius $1$ in dimension $3$. Suppose that the origin is the centre of one ...
2
votes
2answers
110 views

Count the permutations which are products of exactly two disjoint cycles.

Let $a_n$ be the number of those permutation $\sigma $ on $\{1,2,...,n\}$ such that $\sigma $ is a product of exactly two disjoint cycles. Then find $a_4$ and $a_5$. Calculating $a_4$: Possible ...
-1
votes
3answers
111 views

Number of permutations which are products of exactly two disjoint cycles. [duplicate]

Let $l_{n}$ denote the number of those permutations $f$ on the set $A=\{1,2,....,n\}$ such that $f$ is the product of exactly two disjoint cycles. Show that $l_{5}=50.$ I tried a lot but reached ...
0
votes
0answers
23 views

Tight lower bound on falling factorial

I have the term $$p=\left(\frac{1}{n-b}\right)^a\cdot[n]_a, 0<b<a,\ b \in \mathbb{R} \text{ fixed}$$ and want to find a tight lower bound such that I will then be able to solve for n. For ...
1
vote
1answer
59 views

PRIMES 2016 entrance problem

PROBLEM G4 In a couples therapy session, n couples are to be seated at a round table (in 2n chairs), but no person is allowed to sit next to his/her spouse. How many seat assignments are there? ...
0
votes
1answer
40 views

How many $N$ digits binary numbers can be formed where $01$ exactly $k$ times is repeated.

How many $N$ digits binary numbers can be formed where $01$ exactly $k$ times is repeated. Note: first digit can't be zero.
0
votes
0answers
24 views

suppose that $ r_{n} =(3, 3, 3, …, 3)$ ramsey number show $r_{n} \leq n(r_{n-1} - 1) +2$ [duplicate]

$r_{n}$ is ramsey number for $k_{1}, k_{2},..., k_{n}$ which it means the smallest size of a set which if we color all pairwise the element with n color we certainly could find a set of element with $...
0
votes
0answers
29 views

How to fast compute the coefficient of $x^{2^{n-1}}$ in polynomial $[\frac{1}{2}[(1+x)^{2^{r-1}}+(1-x)^{2^{r-1}}]]^{2^{n-r+1}}$?

How to fast compute the coefficient of $x^{2^{n-1}}$ in polynomial $$\left(\frac{1}{2}[(1+x)^{2^{r-1}}+(1-x)^{2^{r-1}}]\right)^{2^{n-r+1}}$$ or compute the coefficient of any term $x^k$ for $k\geq 0$? ...
0
votes
3answers
47 views

Number of ways to select men and women to a committee?

A committee to contain $5$ members and have at least one woman. There are $7$ women and $9$ men. I think that we can fix one woman as one of the $5$ members, and randomly select the rest from a ...
1
vote
2answers
62 views

10 people, 2 groups with equally summed ages

In a room there are 10 people, none of them is younger than 1 or older than 100 years. Prove that among them, one can always find two groups of people (possibly intersecting, but different) the ...
3
votes
2answers
129 views

A combinatorial identity $\sum_{i=0}^k \binom ni \binom{-n}{k-i} =0$

Can anyone prove the following identity for me? $\sum_{i=0}^k \begin{pmatrix} n\\ i \end{pmatrix} \begin{pmatrix} -n\\ k-i \end{pmatrix}=0$ for any positive integers $n,k$. I'm pretty sure this is ...
10
votes
2answers
154 views

5x5 Bingo Puzzle [Logical thinking problem]

5 people participate in a custom game. They are given blank cards, in which they have to fill numbers from 1-25 in a 5x5 table. Each card must contain all the numbers from 1-25 without repetition. The ...
0
votes
0answers
33 views

How is the Möbius function in boolean sets?

Although the text is a little long, the text is very simple so that're familiar with the matter. I did not understand two passages in the text. Could you help me show that: $I'= I \cup M$ and only ...
1
vote
2answers
82 views

Standard playing card deck without jokers: Deal 13 cards. What is the probability at least 1 suit is not present?

Similar questions: What is the probability that 13 cards drawn from a standard deck has at least one card from each suit? Deal 4 cards from a deck. What is the probability that we get one card from ...
1
vote
1answer
34 views

Number of n-permutations with repetition

Let $a_n(k)$ be number of n-permutations with repetition on set $\{1,\dots,k\}$ in which $k$ occurs odd numbers of times. I have to find formula of $a_n(k)$ for $k > 1$. Let $b_n(k)$ be number of n-...
3
votes
3answers
36 views

Using 4-cent and 11-cent stamps for postage (induction)

I was wondering how many base cases are needed and when to stop (in general). For example, I have 4-cent and 11-cent stamps and I need to determine the amount of postage I can make, the cases I have ...
1
vote
2answers
51 views

Binomial Coefficient Identity Involving Summation

Prove that $$\sum_{j=0}^n (-1)^j \binom{n+j-1}{j}\binom{N+n}{n-j} = \binom{N}{n} $$ I tried to prove this via binomial expansions of $(1-x)^N (1+x)^{-m}$, and equating the coefficients of $x$, ...
0
votes
2answers
44 views

How many relatively prime 4-tuples are there?

Given a set of $n$ distinct integers $S = \{a_1,a_2,...., a_n\}$, count how many ways $4$ integers from the set $S$ can be chosen such that their GCD is equal to $1$.
6
votes
2answers
214 views

Permutations of {1 .. n} where {1 .. k} are not adjacent

The Problem: So I was thinking up some simple combinatorics problems, and this one stumped me. Let N be the set of numbers $\{1 .. n\}$, or any set of cardinality $n$ Let K be the set of ...
1
vote
2answers
53 views

Number of solutions in non-negative integers question (Stars and bars)

Q How many solutions are there in non-negative integers $a, b , c, d$ to the equation: $$ a + b + c + d = 79 $$ with the restrictions that $a \geq 10$, $b \leq 40$ and $20 \leq c \leq 30?$ If ...
2
votes
1answer
46 views

In how many ways can these people be arranged for a photograph?

Jessie and Casey are getting married. In how many ways can a photographer at their wedding arrange 6 people in a row from a group of 10 people, where the spouses are among these 10 people, if both ...
1
vote
2answers
76 views

Simplify $\sum_{i=0}^{m}(-1)^{i}\binom{n}{i}\binom{2n}{2m-2i}$

I have to simplify $\sum_{i=0}^{m}(-1)^{i}\binom{n}{i}\binom{2n}{2m-2i}$. That because when $n$ and $m$ get large (eg. $n = 2^{64}$, $m = 2^{60}$), the computation complexity is too high. Could ...
1
vote
2answers
188 views

Different ways of picking a committee of $12$ women and $10$ men

$12$ women and $10$ men are on the faculty. How many ways are there to pick a committee of $7$ if (a) Claire and Bob will not serve together, (b) at least one woman must be chosen I'm not sure ...
0
votes
1answer
23 views

combinatorics: give an upper bound for the cardinality of a set of 100-ary sequences

Let $S$ be a $1990$-element set and let $P$ be a set of $100$-ary sequences $(a_1, a_2, ..., a_{100})$, where $a_i$'s are distinct elements of $S$. An ordered pair $(x,y)$ of elements of $S$ is said ...
0
votes
0answers
45 views

Strategy of ball math game

Found math game: http://www.emathhelp.net/math-games-and-logic-puzzles/rgbw/ What is a strategy for it? I can make 15 white balls max. Any thoughts?
0
votes
2answers
77 views

Number of words with length 8 with certain restrictions

How to find number of words with length 8 such in which every letter A, B, C, D occurs exactly 2 times and exactly one pair of same letters occurs on neighbouring positions? Maybe inclusion–exclusion ...
0
votes
0answers
37 views

Simplify $\sum_{\sum_{i=1}^{2^{n-r}}m_i\ =\ 2^{n-1}\ and\ m_i\ is\ even}\prod_{j=1}^{2^{n-r}}\binom{2^{r}}{m_j},$ where $n$ and $r$ are given.

I need to simplify the following formula: $$\sum_{\sum_{i=1}^{2^{n-r}}m_i\ =\ 2^{n-1}\ and\ m_i\ is\ even}\prod_{j=1}^{2^{n-r}}\binom{2^{r}}{m_j},$$ where $n$ and $r$ are given. I know that: when ...
1
vote
1answer
20 views

Ford-Fulkerson for irrational capacities

We know that the Ford-Fulkerson algorithm works for integer capactities but it may loop forever for irrational ones. Is there an algorithm that only alters Ford-Fulkerson slightly but works for ...
2
votes
0answers
39 views

Trying to understand the properties of a combinatorial game

Consider the following game for $n \geqslant 3$, which I will demonstrate with $n=4$: draw an $n$-gon and place the value 0 at each of the vertices, except one vertex which we circle and place the ...
2
votes
0answers
39 views

Looking for a clever simplification of $\sum_{j=2}^{T_L}(j-1-O_L)(2j-n-1)+\sum_{i=T^U}^{n-1}(O^U-n+i)(2i-n-1)$

I have the expression (which I got by adding up all the distances between $n$ natural numbers bounded by $a_n$ and $a_1$): $$\sum_{j=2}^{T_L}(j-1-O_L)(2j-n-1)+\sum_{i=T^U}^{n-1}(O^U-n+i)(2i-n-1)$$ ...
1
vote
1answer
39 views

Number of unique combinations

I have a collection of possibly repeated items that I need to map onto another set with possibly repeated items. I need to know an efficient algo to iterate through the unique mapping combinations. ...
2
votes
3answers
181 views

In how many ways can you select one of the two but not both?

For this question: A committee of three boys and three girls is to be selected from a class of 14 boys and 17 girls. In how many ways can the committe be selected if: a.) Ana has to be on the ...
0
votes
1answer
458 views

About permutation with repeated identical elements.

First up, I do know the general solution but somehow am unable to use it to solve this kind of problem. I am simply lost. The problem is like this: ...
1
vote
3answers
45 views

Simplify $\sum_{i,j}\left[{n}\atop{i+j}\right]\binom{i+j}{i}$

I have to simplify $\sum_{i,j}\left[{n}\atop{i+j}\right]\binom{i+j}{i}$. I looks like we have $n$ children and we have to answer how many times we can arrange them into circles and color some of ...
1
vote
4answers
121 views

What is the probability that a person wearing a blue t-shirt will sit next to one wearing red?

9 people sit in a row linearly. 2 dressed in Red, 3 blue and 4 in yellow. What is the probability that a person in blue will sit next to a person in red? Why? RRBBBYYYY this sequence from what I ...
4
votes
1answer
104 views

number of labeled trees with n vertices

How many labeled trees with $n$ vertices exist such that their degree is $1$ or $3$? I succeeded to get a range but not a particular answer. EDIT the range I found: $$\frac{n-2}{2^n}\lt\text{ ...
0
votes
1answer
25 views

Proof of Baranyai's theorem

Could you give me a full proof of Baranyai's theorem. I looked at a lot of sites but they seem to only give partial proofs. I read that Schrivjer proved it using the max-flow-min-cut theorem but I can'...