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)

1
vote
1answer
6 views

The number of quadrilaterals formed from collinear and non-collinear points.

There are $25$ points on a plane of which $7$ are collinear . How many quadrilaterals can be formed from these points ? I did this $^{25}C_{4}-^{7}C_{4}=12615$ quadrilaterals. But the book is ...
1
vote
2answers
33 views

How many $3$ integer subsets have no consecutive integers, where integers are less than $20$?

I have to determine how many integers between $1$ and $20$ are possible if no two consecutive integers are in a set. I've thought it has something to do with a combination of an element $(a,a+2,a+4)$ ...
2
votes
3answers
79 views

Sum of increasing integer numbers

Please help me to calculate this sum: $$ \sum\limits_{1\leq i_1 < i_2 <\ldots i_k \leq n} (i_1+i_2+\ldots+i_k). $$ Here $n$ and $k$ are positive integer numbers, and all the numbers $i_1, i_2, ...
2
votes
2answers
36 views

Confusing probability problems based on product rule and combinations

I am going thru probability exercise. Faced first problem: Book Q1. Ten tickets are numbered 1,2,3,...,10. Six tickets are selected at random one at a time with replacement. What is the ...
2
votes
2answers
77 views

Simplifying Sum

How would one show that $$ \sum_{i=0}^n\binom{n}{i}(-1)^i\frac{1}{m+i+1}=\frac{n!m!}{(n+m+1)!} ? $$ Any hint would be appreciated. Note: I tried to recognize some known formula, but since I don't ...
4
votes
3answers
50 views

Algebraic and combinatorial proof of an identity

For any two integers $2 \le k \le n-2$, there is the identity $$\dbinom{n}{2} = \dbinom{k}{2} + k(n-k) + \dbinom{n-k}{2}.$$ a) Give an algebraic proof of this identity, writing the binomial ...
3
votes
3answers
278 views

Prove $\sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}$

Let $n$ be a nonnegative integer, and $k$ a positive integer. Could someone explain to me why the identity $$ \sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k} $$ holds?
3
votes
1answer
45 views

Picking K counters out of K buckets containing NK counters, N of each different colour, up to N in each

This is a generalisation of a question that recently came up while solving a TopCoder problem. Suppose we have N blue counters, N red counters, N white counters, and so forth, K colours in total. We ...
4
votes
1answer
98 views

Consecutive numbers in rows of Pascal's triangle …

The fourteenth row of Pascal's triangle has an interesting property. $$\begin{align} \binom{14}{4}+\binom{14}{5} &= 1001+2002 \\ =\binom{14}{6} &= 3003 \end{align}$$ This begs the ...
1
vote
1answer
42 views

The ant is moving through the coordinate system, Started at $(0,0)$ to $(4,4)$. What is the probability that the ant will find food at $(3,2)$?

The path to the $(3,2)$ is $3+2 \choose 3$ or $3+2 \choose 2$. Total path is $4+4 \choose 4$ And the probability is : $ \frac{3+2 \choose 3}{4+4 \choose 4}$ = $ \frac{5 \choose 3}{8 \choose 4}$ = ...
0
votes
1answer
19 views

Solution of recurrence relation for roots having multiplicity $ \ge 1 $

If there is a recurrence relation of the form $ a_n = c_1 a_{n-1} + c_2 a_{n-2}+ ... + c_k a_{n-k} $, then if b is a non zero complex root of the recurrence relation with multiplicity t, $t \ge 1 $, ...
2
votes
1answer
27 views

Birhdays: find the probabilities for the various configurations of the birthdays of 22 people

Let S,D,T,Q stand for simple,double,triple and quadruple, respectively: So, for example: the probabilities of 22 simple birthdays(22 person have birthdays in different days) are $ P(22S) = ...
10
votes
3answers
643 views

Distinguishable painted prisms with six colors (repetition allowed)

Fraleigh(7th) Ex17.9: A rectangular prism 2 ft long with 1-ft square ends is to have each of its six faces painted with one of six possible colors. How many distinguishable painted prisms are ...
8
votes
3answers
116 views

Probability of rolling a dice 8 times before all numbers are shown.

What is the probability of having to roll a (six sided) dice at least 8 times before you get to see all of the numbers at least once? I don't really have a clue how to work this out. Edit: If we are ...
0
votes
2answers
56 views

Combinatorics: How many 6 digit numbers have AT LEAST one '9' among them?

The Question is pretty simple and straight forward when we try to find the count of numbers without 9 and Subtracting that with Total arrangement of numbers [9*10^5] - [8*9^5]. But how do you ...
3
votes
1answer
149 views

How many ways to arrange 12 identical apples and five distinct oranges in a row so no two oranges are side by side?

My first intuition to solve this problem was to use the separator technique with the apples acting as separators. $$_1_1_1_1_1_1_1_1_1_1_1_1_$$ Since there are now 13 blank spaces for the oranges to ...
3
votes
1answer
74 views

How to count the number of substrings in this combinatorics problem?

Let's say I'm making a string of $A$s and $B$s, where the number of $A$s and $B$s are $a$ and $b$ respectively. A total of $a+b \choose a$ such strings are possible. Now, I wish to know the total ...
3
votes
1answer
66 views

Probability: 12 students choose a major

12 students must choose a major from 6 options (math, biology, physics, chemistry, psychology and architecture). a) what is the probability that exactly 3 students choose physics? b) what is the ...
3
votes
1answer
36 views

Probability of at most two aces

I am dealt 7 cards from a standard pack. I want to find the probability of being dealt at most two aces by using combinations. I believe the calculation looks like this: $$\frac{\binom{4}{2} ...
2
votes
0answers
28 views

Properties of a specific antichain of a lattice formed by the cartesian product of finite ordered sets

Introduction Let $X$ be a poset of all $n$-tuples, $x = (x_1, x_2, ..., x_n)$, where $0 \leq x_i \leq m_i - 1$ for $i = 1, ..., n$ together with the relation $x \prec y$ defined so that for ...
5
votes
1answer
28 views

Integer Tetrahedra

The points $\{(0, 0, 0), (12, 27, 44), (48, 0, 20), (48, 0, -64)\}$ have the property that All vertices are on the integer grid, All edge lengths are integers and different $\{51, 52, 53, ...
3
votes
2answers
40 views

Alternative interpretation of ball and urns problem

Suppose an urn has r red balls and b black balls. They are withdrawn one at a time at random until a total of k, k $\leq$ r, red balls have been withdrawn. Find the probability that a total of n balls ...
3
votes
1answer
26 views

Simplifying a Taylor polynomial that involves Stirling numbers of the second kind

I am currently trying to evaluate a complicated function $f$ at a point $x+a$ using a high order Taylor polynomial about the point $a$. The polynomial has the standard form: $$\sum_{n=1}^k ...
0
votes
3answers
47 views

What is the sum of nine dates in a month? [on hold]

9 dates in a certain month are enclosed by a rectangle as following: 7 8 9 14 15 16 21 22 23 Let $n$ be the number at the top left hand corner of the rectangle. Express the sum of the ...
5
votes
2answers
55 views

Proof that $2^n-(n+1) $ equations are necessary to establish the independence of n events.

Suppose $A_1,A_2,\cdots,A_n$ are $n$ events, we say that they are all independent if for all $\{i_1,\cdots, i_m\}\subset \{1,2,\cdots,n\}$(where $m\ge 2$), we have $$\mathrm{Pr}[A_{i_1}\cap ...
0
votes
1answer
21 views

Say we have a double-decker Lazy Susan with two levels that can be turned independently. If we have n + k dishes in total, how many ways

Say we have a double-decker Lazy Susan with two levels that can be turned independently. If we have n + k dishes in total, how many ways is that solution is correct ???
1
vote
2answers
2k views

Probability of n balls in n cells, one remaining empty

Counting problems have always intrigued me, and I'm working on some out of interest. The other thread on this topic had unsatisfactory answers, because they don't match the answer in my book. My ...
1
vote
1answer
16 views

How can I generate a set of unique groupings of a set (e.g. a set of pairings of students such that everyone works with everyone)?

How can I generate a set of unique groupings of a set (e.g. a set of pairings of students such that everyone works with everyone)? I'm starting with a class of a given size and a group of a giving ...
2
votes
1answer
31 views

Numbers between $200$ and $1200$ that can be formed with the digits $0,1,2,3 $

How many numbers between $200$ and $1200$ can be formed with the digits $0,1,2,3 $ (repetition of digits not allowed ) ? $a.)\ 6\\ b.)\ 8\\ c.)\ 16\\ \color{green}{d.)\ 14}$ I divided it in ...
3
votes
1answer
27 views

Optimizing number of 6-digit strings differing in at least two places

A certain province issues license plates consisting of six digits (from 0 to 9). The province requires that any two license plates differ in at least two places. (For instance, the numbers ...
0
votes
2answers
402 views

calculate all combination of indistinguishable objects

I am thinking a question of picking $k$ objects out of $n$($n>k$). But among the $n=4m$ objects, only $m$ distinguishable objects. For example, a deck of poker cards, total $n=52$ cards, but we ...
5
votes
4answers
116 views

How many ways to write $2010$?

Let $ N$ be the number of ways to write $ 2010$ in the form $ 2010 = a_3 \cdot 10^3 + a_2 \cdot 10^2 + a_1 \cdot 10 + a_0$, where the $ a_i$'s are integers, and $ 0 \le a_i \le 99$. An example of ...
2
votes
1answer
34 views

dots/ beads on a grid

I've got some difficulties with the following problem. We have an infinite grid. We put $4$ beads on the point $(0, 0)$. If we want to move a bead from $(x, y)$ we have to replace it with two ...
6
votes
3answers
263 views

When are products of binomial coefficients equal?

It's known that $\binom{n}{r} = \binom{n}{s}$ if and only if $r = s$ or $r = n - s$. If $n \neq m$, is it true that $\binom{n}{s} \binom{m}{r} = \binom{n}{k} \binom{m}{\ell}$ if and only if ($s = k$ ...
0
votes
0answers
9 views

Question regarding isomorphisms formed by deleting various edges in a plane triangulation…

Consider a plane triangulation $T$ with $m$ edges numbered $1, 2, … , m$. Form the near-triangulation $G_k$ by deleting the edge $e_k$ in $T$. Suppose the $m$ near-triangulations $G_k$ for $k = 1, 2, ...
0
votes
0answers
33 views

Highest efficiency suub collection of sets.

Hy can some one help me to figure out this. X is a set of type1 elements. Y is a set of type2 elements. Given a collection of sets (S) in which each set(Si) is a subset of XunionY. The efficiency ...
13
votes
1answer
116 views

Congruent quadrilaterals in a tri-colored $72$-gon

I recently watched a movie (A Brilliant Young Mind) in which this problem appeared: Let the vertices of a regular $72$-gon be colored red, blue, and green in equal parts. Show that there are $4$ ...
0
votes
1answer
57 views

Permutations on word $MISSISSIPPI$.

In how many ways can the letters of the word $MISSISSIPPI$ be rearranged ? I am confused on whether it is $\dfrac{11!}{4!4!2!}$ or $\dfrac{11!}{4!4!2!}-1$ since it is given rearranged and not ...
0
votes
2answers
27 views

Find number of unordered pairs $(A,B)$

Find number of unordered pairs $(A,B)$ such that $\bullet \space A$ and $B$ are subsets of an $n$ element set $S$ $\bullet \space A \cup B=S$ $\bullet \space A≠B$
5
votes
1answer
53 views

How to prove$\displaystyle \sum_{i=0}^{k}(-1)^i\binom{n}{k-i}\binom{n+i-1}{i}=0$

I saw a combinatorial identity when i study linear-algebra, But the author didn't explain how to get it. $\displaystyle \sum_{i=0}^{k}(-1)^i\binom{n}{k-i}\binom{n+i-1}{i}=0$ I tried $n=10$ or ...
2
votes
1answer
31 views

Permutation of students in a class

In how many ways can 10 BS and 7 MS students be arranged in a line so that no two MS students may sit together? My approach: Total number of ways all 17 students can be arranged in a line is ...
2
votes
1answer
21 views

How many ways to select distinct pairs from k disjoint sets

How many pairs can be generated from k disjoint sets. For example I have following 3 sets(k=3): A = {1,2,3} B = {4,5} C = {6,7} I want to form pairs such there's no element of pair coming from the ...
2
votes
1answer
35 views

Must the number of people at a party who do not know an odd number of other people be even

I have a homework question in my discrete mathematics class as the title shows, I feel the answer is no, but googling this question seem's to contradict my answer. Let me explain: So if they are ...
0
votes
2answers
58 views

An online calculator that can calculate a sum of binomial coefficients

Is there any online calculator that can calculate $$\dfrac{\sum_{k=570}^{770} \binom{6,700}{k}\binom{3,300}{1,000-k}}{\binom{10,000}{1,000}} $$ for me? There are a few binomial coefficient ...
2
votes
1answer
38 views

Permutations and Combinations - conceptual

Suppose we have 10 objects. I want to create a group with those 10 objects. The group should contain a minimum of 2 objects (it can contain anywhere from 2-10 members). How would I find the total ...
4
votes
1answer
29 views

Echalon decomposition in binary shuffle (Hopf) algebras

Consider a binary shuffle algebra $\mathcal{W}$ of two letters $a, b$. As usual the concatination of two words $u = u_1 \dots u_m$, $v = v_1 \dots v_n$ is defined as: $$u \bullet v := u_1 \dots u_m ...
2
votes
2answers
36 views

How many zero-sum $n$-tuples are there?

The question is extremely short and concise. How many $n$-tuples $X \in \{\, -1,0,1 \,\}^n$ have the zero-sum property $\sum_{x \in X} x = 0$ ? At the moment I have nothing to share of my own since ...
13
votes
6answers
1k views

Why $0!$ is equal to $1$? [duplicate]

Many counting formulas involving factorials can make sense for the case $n= 0$ if we define $0!=1 $; e.g., Catalan number and the number of trees with a given number of vetrices. Now here is my ...
-2
votes
0answers
36 views

Counting math problems [on hold]

1) Ann, Bobby, and Cece are randomly placed in a line with 26 people total. What is the probability that Ann is to the left of Bobby, and Bobby is to the left of Cece? Express your answer as a common ...
3
votes
2answers
53 views

How many ways can we form two non-intersecting triangles from an $n$ sided regular polygon

Say I wish to form exactly two non-intersecting triangles using vertices of an $n$ sided polygon. How many ways would there be of doing this? The condition is that the vertices must be distinct. In ...