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

Defining a combinatorial problem for a given equation

I was given the following task: define a combinatorial problem to the following equation, and say how each side of the equation solves the given problem. The equation is: $$ n\binom{n}{r} ...
-1
votes
0answers
8 views

How to prove that there exists a binary string set $|A|=\Omega(2^n)$ such that its elements have hamming distance nonless than $\frac{n}{3}$?

Suppose $A\subset \{0,1\}^n$ and for any $x,y\in A$, the hamming distance between $x$ and $y$ is nonless than $\frac{n}{3}$. Prove that $\max\limits_A|A|=\Omega(2^n)$.(there exists a constant $C>0$ ...
2
votes
3answers
22 views

Largest subset with no arithmetic progression

I am trying to find some weak bounds on the largest subset of a set, such that the subset has the property that it contains no three elements in arithmetic progression. The elements of the original ...
1
vote
2answers
23 views

Need help with figuring out what this definition of permutations actually means.

Here is a direct screenshot of the book: First of all, what does type mean? Does the author mean that the set with $r$ elements can be partitioned into $n$ subsets? Secondly, an $r$ permutation of ...
1
vote
3answers
31 views

Multiplication partitioning into k distinct elements

Let's say I have a list with the prime factors of a number $n$ and their corresponding exponents. Is there a formula to calculate how many multiplications with $k$ distinct factors of $n$ are ...
0
votes
1answer
34 views

Composition of n into k parts, one part is odd and the rest are even

My task is to determine the number of compositions of $n$ into $k$ parts, such that exactly one part is odd and the rest are positive and even. I am trying to determine the set itself that I am ...
1
vote
1answer
16 views

Prove number of edges in an edge-disjoint spanning tree

I have the following problem. It isn't homework--it's additional work I want to do to further grasp the material in my Combinatorics class. Show that if a graph $G$ contains $k$ edge-disjoint ...
-1
votes
0answers
28 views

Choosing M cards from N decks

Alice and Bob are playing cards. They have N decks of cards. Each deck of cards contain 52 cards: ...
-1
votes
0answers
48 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}$$
6
votes
1answer
75 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
27 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
1answer
57 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 $
5
votes
5answers
67 views

solutions such that a combination number is odd

Let $m$ be a positive integer. Given $m$, I want to find the largest $n$, $1\leq n\leq m$, such that $$m+n\choose n $$ is odd. Is there any standard theorems or results? Any references? Thanks!
2
votes
1answer
23 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 ...
3
votes
2answers
40 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 ...
2
votes
1answer
16 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
30 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 ...
0
votes
1answer
15 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
27 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
19 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
21 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
19 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 ...
-3
votes
0answers
27 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 ...
2
votes
2answers
35 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 ...
0
votes
2answers
27 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
50 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
1answer
25 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 ...
4
votes
2answers
42 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
33 views

Probability of getting A to K on single scan of shuffled deck

Let us say we have a regular 52-card well-shuffled deck. We scan through the deck (first to last) till we find an Ace. Then we continue (from that Ace) till we find a 2. Then we scan (from the 2) ...
1
vote
0answers
55 views

Minimizing over partitions $f(\lambda) = \sum \limits_{i = 1}^N |\lambda_i|^4/(\sum \limits_{i = 1}^N |\lambda_i|^2)^2$

I'm trying to characterize the behavior of the the quantity: $$A = \frac{\sum \limits_{i = 1}^N x_i^4}{(\sum \limits_{i = 1}^N x_i^2)^2},$$ subject to the constraints that $$ \sum \limits_{i = 1}^N ...
2
votes
1answer
35 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 ...
3
votes
3answers
50 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 ...
0
votes
0answers
12 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
5 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} $
2
votes
1answer
102 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}$$
0
votes
0answers
26 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 ...
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 ...
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
471 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 ...
2
votes
1answer
34 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
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$, ...
1
vote
1answer
44 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 ...
1
vote
1answer
24 views

2 Distributions Questions

How many ordered quadruples $(a,b,c,d)$ satisfy $a+b+c+d=18,$ where $a,b,c,d$ are positive integers? How many ordered quadruples $(a,b,c,d)$ satisfy $$a+b+c+d=18,$$ where $a,b,c,d$ are nonnegative ...
1
vote
3answers
51 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 ...
0
votes
2answers
29 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 ...
2
votes
2answers
59 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 ...