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)

2
votes
1answer
24 views

Difference table for a sequence.

Let the sequence $h_0,h_1, ... h_n$ be defined by $h_n = 2n^2- n+3~(n \geq 0)$. Determine the difference table, and find a formula for summation of $h_0$ through $h_n$ I encountered this ...
-1
votes
0answers
57 views

How to simplify $\sum_{r=1}^{y} \binom{x-1}{r}\binom{y-1}{r}$? [on hold]

To find sum of the product of two combination terms $$\sum_{r=1}^{y-1} \binom{x-1}{r}\binom{y-1}{r}$$
2
votes
1answer
59 views

How many five-digit number $ABCDE$ exist

How many five-digit numbers $ABCDE$ exist if, a) $A>B>C>D>E$ or b) $A≥B≥C≥D≥E $
0
votes
2answers
30 views

How many ways are there to distribute 6 distinguishable objects into 4 indistinguishable boxes so that each of the boxes contain at least 1 object?

How many ways are there to distribute 6 distinguishable objects into 4 indistinguishable boxes so that each of the boxes contain at least 1 object? Can anyone tell me how should I approach this ...
6
votes
1answer
78 views

How many topologies exist on a finite set?

In my topology class we are asked to list all topologies on a $3$ element set. I have found $29$ and this should be the correct result. Now I wonder whether there is some formula that determines this ...
0
votes
1answer
41 views

to simplify the following combinatorial terms [on hold]

To simplify the following summation involving product of combinations $$\sum_{r=1}^{y}\left(\begin{array}{c} x-1 \\ r \end{array}\right) \left(\begin{array}{c} y-1 \\ r-1 ...
2
votes
2answers
327 views

Two Probability Questions

Studying for a final: 1) Suppose we have four indistinguishable red balls, 6 indistinguishable blue balls, and 2 indistinguishable green balls. How many different color patterns can be obtained by ...
3
votes
2answers
42 views

Counting $3$ digit even integers between $1$ and $1000$ with distinct digits

$5$ choices for the last digit, $9$ choices for the second digit and $7$ choices for the first digit: $5 * 9 * 7$ integers with the given property. Or $5$ choices for the last digit, $8$ choices for ...
-3
votes
0answers
30 views

in how many ways i can put three things in two bags [on hold]

I have two oranges,one apple and one banana. i want to put two of them at a time in two bags having one(one froot at max in one bag) each. There are two oranges and they are indistinguisable(they are ...
1
vote
0answers
41 views

Intersecting Family of subsets of size k

Suppose that $k$ divides $n$. Then an intersecting family $F$ of $k$-subsets of an $n$-set $X$ has size at most $n-1\choose k-1$. The prove goes as follows: Let $B$ be the set of all partitions ...
1
vote
2answers
46 views

Finding minimum value of a trigonometric expression [duplicate]

If $A+B+C=\pi$ then what is the minimal value of $$\tan^{2}A/2+\tan^{2}B/2+\tan^{2}C/2$$
2
votes
2answers
61 views

If sum of seven distinct natural numbers is 100 How to prove that there exist at least one group of three numbers whose sum is 50

There are $7$ distinct natural numbers whose sum is $100$. From these 7 numbers 3 numbers can be selected in $C(7,3)=210$ ways How to prove that at least one of these groups will have sum at least ...
4
votes
2answers
43 views

If there must be at least one person in each table, in how many ways can 6 people be seated in 3 tables?

If there must be at least one person in each table, in how many ways can 6 people be seated in 3 tables? I know there are three possible ways to split the set of people P into three distinct ...
2
votes
1answer
19 views

How do I read this equation related to Combinations with repetitions in natural language?

Here's an Article from TopCoder about Combinatorics, that starts by introducing some basic concepts such as: Combinations and permutations. That part I understood just fine, but then the article ...
1
vote
1answer
34 views

Is there any upper bound of this sum?

$a_1,a_2,\ldots,a_n,k$ are all integers. Is there any upper bound of the following sum $$\sum_{a_1+a_2+\cdots+a_n=k\textrm{ and } a_1,a_2,\ldots,a_n\ge 0} \frac{1}{a_1!a_2!\cdots a_n!},$$ which is a ...
6
votes
3answers
6k views

How many options are there for 15 student to divide into 3 equal sized groups?

How many options are there for 15 student to divide into 3 equal sized groups? Now i know the soultion is $\;\dfrac {15!}{5!5!5!3!}\;$ but i can't understand why. Can anyone please enlighten me?
2
votes
1answer
37 views

calculating characteristic polynomial in $\mathbb{R}^n$

Given some hyperplane arrangement $\mathcal{A}$, we call any subset $\mathcal{B}\subseteq \mathcal{A}$ $\textit{central}$ if $$\displaystyle \bigcap_{H\in \mathcal{B}}H\neq \emptyset.$$ There is a ...
0
votes
1answer
17 views

Restricted Derangement - Envelope Letter Problem

There are 5 envelopes numbered from 1 to 5 and 5 letters numbered 1 to 5.Letter numbered 1 is always placed in envelope number 2.In how many ways the all the letters can be put in wrong envelopes? ...
0
votes
1answer
31 views

Formula for numerating the elements of the set

Is there a formula for numerating the elements of the set $$ D = \{ (i_1, i_2, \ldots, i_k): 1 \leq i_1 <i_2 < \ldots <i_k \leq n \} $$ (here $ n, k $ are positive integers, $ n> k $; $ ...
-3
votes
0answers
21 views

Bit String Probability [on hold]

Given a bit string of length 8 begins with a 0, find the probability that it contains exactly three 0's. How many bit strings of length 8 contain an evan number of 0's? How can permutations and ...
1
vote
1answer
31 views

Is this the correct number of permutations?

How many permutations of the English alphabet do NOT have all five vowels appearing consecutively? What I have: Since there are $26$ letters in the alphabet and each letter can be used only once, ...
2
votes
0answers
23 views

Prove this Binomial Identity by Induction

Prove the following binomial identity by induction $\sum_{i=1}^n \binom {i+k-1} {k} =\binom {n+k} {k+1}$ What I have: We will show that the equality is true for $n=1$: $$\binom {i+k-1} ...
0
votes
1answer
21 views

Bitstring Probability

I am not understanding how to apply n choose r and permutations to the following problem. Given a bit string of length 8 that has exactly three 0's, what is the probability that the bit string will ...
0
votes
2answers
35 views

How many 5 digit numbers can be formed out of {1,2,3…,9} where a digit can repeat at most twice?

The question is: How many different numbers of 5 digits can be generated out of {1,2,3,4,5,6,7,8,9} such that no digit can appear more than twice ? That is a number like 11213 is not allowed. but ...
3
votes
3answers
57 views

How many subsets of A={1,2,3,…,10} have the property that the sum of their elements is $\geq 28$?

I've already known that the desired answer is 512. But, how can I get this answer? Can anybody show me how to get this answer with only using permutation or combination? I can only think that the ...
2
votes
2answers
36 views

How many distinct numbers can I get mod 8

so I have the following $(0,1\ \text{or}\ 4)+(0,1\ \text{or}\ 4)+(0,1\ \text{or}\ 4)$ I want to see how many distinct numbers can I get mod $8$ by adding from this list 3 times for example I got so ...
3
votes
3answers
55 views

Is this a good proof of the binomial identity?

Prove that the binomial identity ${n\choose k} = {n-1\choose k-1} + {n-1\choose k}$ is true using the following expression: $(1+x)^n = (1+x)(1+x)^{n−1}$ and the binomial theorem. What I have: We ...
-4
votes
2answers
40 views

No. of surjections [on hold]

Find the number of surjections from a $3$-element set to a $2$-element set. Find a formula for the number of surjections from $ℙ_{k+1}→ℙ_k.$ Find a formula for the number of surjections from ...
2
votes
1answer
27 views

Combinations with maximum allowed Repetition

There are how many ways to select $r$ things from $n$ categories with maximum $k$ repetitions are allowed from each category? I think its only solvable if and only if $nk\ge r$ and I also believe ...
3
votes
1answer
97 views

Product of Stirling Numbers of the first kind

I have been messing around with coefficients of various polynomials and was wondering if there was a way to reduce the following stuff. Let polynomial, ...
0
votes
0answers
15 views

Show that every tournament on n vertices, contains a transitive tournament on floor(log2 n) vertices

Show that every tournament on n vertices, contains a transitive tournament on floor(log2 n) vertices. Also, show that there exists a tournament on n vertices that does not contain a transitive ...
0
votes
0answers
6 views

To write product of 2 combinations as one combination term

Is it possible to write this product of combinarions as one comination term $\binom{N-x-1}{r} * \binom{x-1}{r} $
10
votes
2answers
148 views

Number of $K_{10}$ always increases

Let $G=(V,E)$ be a graph with $n\geq 10 $ vertices. Suppose that when we add any extra edge to $G$, the number of complete graph $K_{10}$ in $G$ increases. Show that $|E|\geq 8n-36$. [Source: The ...
2
votes
1answer
151 views

How can I prove this combinatorial identity?

Let $n,m$ be non-negative integers. How can one prove the following identity? $$\sum_{j=0}^n j\binom{2n}{n+j}\binom{m+j-1}{2m-1}=m\cdot4^{n-m}\cdot\binom{n}{m}$$
1
vote
1answer
45 views

Determining coefficients in generating functions?

The question is to determine the coefficient of x^8 in G(x) = (10x-1)/((1-4x)(1-x)). I'm not sure what to do here, I don't know how to expand this. I figured the decomposition for this equation to ...
0
votes
0answers
28 views

Number of Unique Permutations of 3 digits (-1,0,1) given a length that match a sum

Say you have a vertical game board of n length (length being number of spaces). And you have a three sided die that has the options: go forward one, go back one, and stay. If you go below or above ...
27
votes
11answers
6k views

How many positive integers $< 1{,}000{,}000$ contain the digit $2$?

How many positive integers less than $1{,}000{,}000$ have the digit $2$ in them? I could determine it by summing it in terms of the number of decimal places, i.e. between $999{,}999$ and ...
4
votes
1answer
642 views

Social Golfer Problem - Quintets

I wrote an article on the Social Golfer Problem, which has questions like: Each day, 16 people play Munchkin in foursomes simultaneously. How many days can they play with no two people playing with ...
0
votes
1answer
23 views

Rectangular stained glass window with different colors

Suppose you have six squares of stained glass, all of different colors, and you would like to make a rectangular stained glass window in the shape of a 2 × 3 grid. How many different ways can you do ...
3
votes
4answers
324 views

An identity involving Stirling numbers of the second kind and binomial coefficients

Need to prove: $$\sum\limits_{k=0}^{n} \binom nk k^r x^k = \sum\limits_{j=0}^{r} \binom nj j! (1+x)^{n-j} x^j S(r,j)$$ where $S (n, k)$ denotes a Stirling number of second kind, the number of ...
1
vote
1answer
51 views

Probability of same birthday

I think I solved this problem but I would like to know if I am right or wrong, I am not quite sure. We assume that the year has 365 days and the birthdays are uniformly distributed. We want to find ...
0
votes
0answers
8 views

Are there any minimum-degree-5 triangulations of the sphere for which every four-coloring consists of six Kempe chains, one for each color-pair?

I'm interested only in triangulations that have no separating triangles (i.e. triangles for which there are vertices both inside and outside the triangle). The 5-regular icosahedron is one. Are ...
3
votes
2answers
476 views

What is the expected number of suits in a hand of 4 cards?

To find the expected number of suits the formula is $E(Num Suits) = 1*P(1 Suit) + 2*P(2 Suit) + 3*P(3 Suit) + 4*P(4 Suit)$ For the probability of getting 4 suits I got ${13 \choose 1}^4 {4 \choose ...
3
votes
1answer
8k views

Programming: find the total possible combinations of three variables?

I have three variables in a programming function, and a 4th variable depends on these. I have to test the dependent variable against all combinations of the three variables: Var A: 2 possible ...
2
votes
1answer
35 views

How to compute coefficients of the Vandermonde polynomial?

I am trying to find the coefficients of the monomials in the expansion of $$\prod_{1\le i < j \le n}^n (x_j - x_i)$$ also known as the Vandermonde determinant. For example, for $n=3$ we have ...
1
vote
3answers
52 views

Expected number of cards drawn before drawing a $4$ or $5$

I'm working on the following problem: Compute the number of expected cards drawn from a standard 52 card deck (without replacement) until a $4$ or $5$ is drawn. I tried to model it using a ...
2
votes
1answer
50 views

Jacobi Identities

Can anyone guide me how can I prove these two identities? a)$$\prod_{n=1}^{\infty}\frac{1-q^{2n}}{1-q^{2n-1}}=\sum^{\infty}_{n=1}q^{n(n+1)/2}$$ b) ...
1
vote
1answer
33 views

How many permutations of [8] have neither 1 nor 2 as fixed points?

I am attempting to understand the probleme des recontres and the principle of inclusion and exclusion. My solution for the question would be: Use ${n \choose k}$ $D_{n-k}$ where D represents the ...
1
vote
1answer
22 views

Combinatorics problem on the size of A+B

Let $A$, $B$ be finite subsets of $\mathbb{Z}$ with $|A|=n$, $|B|=m$. Denote $A+B=\{a+b:a \in A, b \in B\}$. It's fairly easy to show that $|A+B| \geq n+m-1$. My question is: If $|A+B|=n+m-1$, ...