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

Inclusion Exclusion with 4 sets: How many integers between 1 and 100 are divisible by 2 or 3 or 5 or 7?

How many numbers between 1 and 100 are divisible by 2 or 3 or 5 or 7? The solution I had gives a different answer from what was provided, so I was wandering if anyone could tell me what mistake I ...
0
votes
0answers
12 views

Intersection of balls in Hamming space

Let $B(x_1, r)$ and $B(x_2,r)$ be balls in $\{0,1\}^n$ (in Hamming distance). Denote by $d$ Hamming distance between $x_1$ and $x_2$. What is $|B(x_1, r) \cap B(x_2, r)|$ (asymptotically)? Upd: I ...
0
votes
0answers
21 views

A combinatorics question about selection strategies

I am given a set of balls--red and blue. In each set, there are three kinds of balls--small, medium and large. In each set there are 10 balls of each color: 10 Red balls (2 small + 3 medium + 5 ...
0
votes
2answers
22 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} ...
-3
votes
0answers
19 views

Largest subset with certain Hamming distance. [on hold]

The problem is about finding a largest subset such that each pair of its element is "far enough". Suppose $A\subset \{0,1\}^n$ and for any $x,y\in A$, the hamming distance between $x$ and $y$ is ...
3
votes
3answers
26 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
25 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
32 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
39 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
51 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
76 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
29 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
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 $
5
votes
5answers
71 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 ...
1
vote
1answer
75 views

A math contest question related to Ramsey numbers

In a group of 17 nations, any two nations are either mutual friends, mutual enemies, or neutral to each other. Show that there is a subgroup of 3 or more nations such that any two nations in the ...
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 ...
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
31 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
28 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
20 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
28 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
28 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
51 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 ...
4
votes
1answer
47 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
56 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
109 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
472 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
45 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 ...