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

Order-Preserving Bijection $f:A\to A^*$?

Let $A$ be a well-quasi-ordered infnite set. Does there exist an order-preserving bijection $f:A\to A^*$, where $A^*$ is the free monoid over $A$ under the subword ordering? Would this subword ...
0
votes
2answers
22 views

Probability; bridge hand question

$13$ cards are chosen at random with no replacement from a deck of $52$ cards. find the probability there are $5$ spades chosen, $4$ hearts, $3$ diamonds and $1$ club. I got ...
1
vote
1answer
12 views

Splitting $N$ Groups of Objects into $M$ bins

For simplicity, I'll give the example as splitting 3 bins of balls into 4 bins. Bin 1 contains $N_1$ blue balls, bin 2 $N_2$ red balls, and bin 3 $N_3$ green balls How many combinations of ways ...
3
votes
1answer
30 views

Combinatorics: How do you find the coefficient in the given expression?

The question asks me to find the coefficient of the term $x^6y^4$ in the expression $(xy^2+x^2+3y)^7$. This was pretty simple. This is how I did it: $$(xy^2+x^2+3y)^7 = \sum_{a+b+c = n} (xy^2)^a + ...
0
votes
1answer
12 views

Show that if a bipartite graph $G = (V, E)$ with bipartition $V = A \cup B$ is $k$-regular, then $|A| = |B|$.

A graph is $k$-regular if every vertex has degree $k$. Show that if a bipartite graph $G = (V, E)$ with bipartition $V = A \cup B$ is k-regular, then $|A| = |B|$. I dont understand it. Please explain ...
0
votes
3answers
27 views

How many different varieties of pizza can be made if you have the following choices:

How many different varieties of pizza can be made if you have the following choice: small medium, large; thin, hand tossed, pan; and $12$ toppings (cheese is an automatic), from which you may select ...
1
vote
3answers
23 views

Prove that the sequence of combinations contains an odd number of odd numbers

Let $n$ be an odd integer more than one. Prove that the sequence $$\binom{n}{1}, \binom{n}{2}, \ldots,\binom{n}{\frac{n-1}{2}}$$ contains an odd number of odd numbers. I tried writing out the ...
3
votes
2answers
97 views

Seeking non-inductive, combinatorial proof of the identity $1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n + 1)(2n + 1)}{6}$

How do you prove $$1^2 + 2^2 + 3^2 + \cdots + n^2 = \dfrac{n(n + 1)(2n + 1)}{6}$$ without induction? I'm looking for a combinatorial proof of this.
0
votes
0answers
17 views

Integer partitions with distinct parts

Let $~~p(n)~~$ denote the number of all partitions of positive integer $~~n~~$ with distinct parts. I would like to find some effective algorithm for calculating $~~p(n)~~$. It seems that dynamic ...
-1
votes
1answer
16 views

Prove that for every $n \in \Bbb N$, the hypercube graph $Q_n$ is bipartite [duplicate]

Prove that for every $n \in \Bbb N$, the hypercube graph $Q_n$ is bipartite I don't understand this problem. And I'm not very good with proofs. Please help because I want to understand fully ...
0
votes
0answers
13 views

Fraction of permutations satisfying a poset

Let $[n]:=\{1, ..., n\}$. Let $P$ be a poset on $[n]$. What is the fraction of permutations that satisfy $P$ when we view a permutation as inducing a linear ordering on the numbers? For instance, if ...
1
vote
1answer
44 views

How to calculate number combinations of formulas for a number of propositions

I can see, using a paper, that the number of different combinations of forumals (in the sense extensively discussed in the comments) that one proposition can have is $4$, and even that the number for ...
5
votes
2answers
45 views

What is the number of ordered triplets $(x, y, z)$ such that the LCM of $x, y$ and $z$ is …

What is the number of ordered triplets $(x, y, z)$ such that the LCM of $x, y$ and $z$ is $2^33^3$ where $x, y,z\in \Bbb N$? What I tried : At least one of $x, y$ and $z$ should have factor ...
0
votes
2answers
40 views

threshold for random 2-sat

I'm looking at notes on the threshold for random 2-sat which is given as $r_{2}^{*}=1$. In the first part of proving the threshold they claim that a 2-sat formula is satisfiable if and only if the ...
0
votes
1answer
19 views

Recurrence solving

Suppose recurrence is $a_{n+2}=a_{n+1}+6a_{n}$ Tried to solve it with solving $Fnc(n)=An^5+Bn^4+Cn^3+Dn^2+En+F$ Which gives $A = (-33/4), B = (365/4), C = (-1385/4), D = (2155/4), E = (-551/2), F = ...
0
votes
1answer
43 views

Prove a square free word

A square free word is a word that does not contain any subword twice in a row. An infinite word is defined: $$ w_i=\{ \textrm{the maximal natural j that } 2^j \textrm{ devides } i\} $$ the first ...
-1
votes
5answers
65 views

Give a proof of ${n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + … + {n \choose n}^2 = {2n \choose n}$ [duplicate]

I must prove this: ${n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + ... + {n \choose n}^2 = {2n \choose n}$ But, I have no idea how to prove it or how it necessarily works. Could someone help ...
0
votes
0answers
26 views

Probability of choosing the same color has the smallest probability on balanced set?

A bag contains $N$ balls of $K$ different colors. Suppose that there is, at least, $s>0$ number of each color. We would like to do the following procedure: Choose $s$ balls randomly (with ...
1
vote
2answers
53 views

Give a Combinatorial proof to show $\sum_{i=1}^{n}{iC(n,i)}=n2^{n-1}$

I am completely lost on how to achieve this. I have no idea where to start, nor do I know what to use to find to prove this problem. Can someone help me with this?
3
votes
2answers
39 views

If you roll a die two times, what is the probability the sum of the upturned faces equals $7$?

If you roll a die two times, what is the probability the sum of the upturned faces equals $7$? I can answer this question if I consider the order of the rolled numbers relevant. However, when I ...
3
votes
1answer
43 views

How many DFA's exist with two states over the input alphabet $\{0,1\}$?

How many DFA's exist with two states over the input alphabet $\{0,1\}$? My attempt : Input set is given. So, we have 3 parts of DFA which we can change: Start state Transition Function Final ...
0
votes
1answer
50 views

What is the coefficient of ${x}^{101}{y}^{99}$ in the expression of $(2x-3y)^{200}$

I know that I have to use the binomial theorem. So, in following the formula of ${(1+x)}^{n} = {n \choose 0}+{n \choose 1}{x}+{n \choose 2}{x}^{2}...+{n \choose k}{x}^{k}+...+{n \choose n}{x}^{n}$, I ...
1
vote
2answers
50 views

How many outcomes are there when you roll 4 dice?

My initial reaction is to say that the answer is $6^4$, since 4 dice can have 6 outcomes. In my train of thought, the first dice can have 6 outcomes, same as the second, third and fourth, thus ...
3
votes
1answer
41 views

Combinatorial proof of number of disjoint subsets

Fix positive integers $n$ and $k$. Find the number of $k$-tuples $(S_1, S_2,\dots, S_k)$ of subsets $S_i$ of $\{1, 2, \dots , n\}$ with the $S_i$’s pairwise disjoint. I am looking for a way to ...
1
vote
1answer
18 views

Combinatorics Name Generating

So I'm supposed to figure out how many names an alphabet consisting of A,L,I,S and T can generate. Each name must consist of $2$ vowels and $5$ consonants, begin and end with a consonant, two vowels ...
2
votes
0answers
22 views

Allocate Chamber Musicians to Fewest Possible Concerts

First of all, I am not a mathematician. I'm mainly asking the question to see if what I want to do is even possible via math -- and whether I then could computerize this math. So you may throw this ...
1
vote
1answer
24 views
0
votes
2answers
45 views

Reverse Lexicographic Order

Find the 233rd subset of [12] with five elements in reverse lexicographic order. I am a little confused with the difference between normal and reverse lexicographic order. I think I understand that ...
0
votes
0answers
15 views

Simple probability/combinatorics computation

I can do that for specific values of $n$ and $L$, but I just can't generalize it. Let $F:Dom \rightarrow Cod$ be a surjective function, $n,L \in \mathbb{N} $, $n$ even and $L \ge2.$ Let ...
5
votes
2answers
122 views

How many numbers of $10$ digits that have at least $5$ different digits are there?

In principle I resolved it as if the first number could be zero, to the end eliminate those that start with zero. The numbers that can use $4$ certain figures (for example, $1$, $2$, $3$ and $4$) are ...
2
votes
1answer
47 views

Measure of card shuffling randomness

I've read online that you need to shuffle a deck of cards at least 7 times (depending on the game being played) for the deck to be 'random enough', i.e. that it is nearly impossible to predict the ...
1
vote
2answers
22 views

Product of the edges is distinct

We have a complete graph with $n\geq 3$ vertices. Show that we can label the edges with $1,2$, or $3$ so that the product of the edges is distinct at every vertex. For $n=3$ this is obvious. For ...
0
votes
0answers
17 views

combinatorial optimization - choosing portfolios

Here is my problem.. I have 100,000 individuals choosing portfolios of size 6 among 2,000 potential. Each individual must submit a ranked list of orders. A portfolio $j$ yields utility $u_{ij}$ for ...
0
votes
0answers
16 views

Hypercontractivity Lemma

In the proof of the Hypercontractivity Lemma here http://www.cs.cmu.edu/~odonnell/boolean-analysis/lecture13.pdf (3.4) what does it mean to split $p$ into $r + x_n*s$, why can we do this?
0
votes
0answers
25 views

The minimum of two big-O functions

Suppose we have the following lower and upper bounds for an invariant $\chi(G_N)$, where $G_N$ is a graph on $N$ vertices, $N=f(k,n,m) $ and $N,k,n,m\in \mathbb{N}$: $$ ...
0
votes
2answers
27 views

(Probability)Bars and stars problem with two constraints

What is the probability that you roll 4 die and get a sum less than or equal to 5? So far, I have come up with this: $x_1 + x_2 + x_3 + x_4 \leqslant5 $ Constraints: $x_1, x_2, x_3, x_4 ...
3
votes
2answers
29 views

Alice, Beatrice and a tournament

In a tournament of $2^n$ players, Alice and Beatrice ask what's the probability that they'll not compete if they've the same level of play? Let : $A_i$ : Alice plays the $i$-th tournament ; $B_i$ : ...
2
votes
2answers
51 views

Prove that the intersection of all the sets is nonempty.

Given $2^{n-1}$ subsets of a set with $n$ elements with the property that any three have nonempty intersection, prove that the intersection of all the sets is nonempty. I find this question a bit ...
1
vote
1answer
35 views

What is this matrix notation and how is it solved?

I've never taken a stats class, or linear algebra or much of anything that involves matrices. In one of my books they give me this as part of an example and it states, $$\binom{6}{4} = 15 \text{ ...
3
votes
1answer
45 views

Tricky pigeonhole principle question

Say someone is given at least one marble every day for 7 weeks. However, there are never more than 11 marbles given to the person in one week. Prove that there is some period of consecutive days in ...
0
votes
1answer
33 views

In how many ways can you order in line the letters of the words $AAAABBBBBCCDE$ such that

In how many ways can you order in line the letters of the words $AAAABBBBBCCDE$ such that none of the substrings: "$DE$" or "$ED$" appear in the beginning or in the end? I was thinking - take all the ...
0
votes
1answer
15 views

Formula for choosing $x$ elements from a set containing $n$ elements, with repetition allowed

I've been searching around for a formula for the number of cmbinations for choosing $x$ elements from a set containing $n$ elements. For instance, for the set $(1,2,3)$ we have $10$ different ways of ...
0
votes
2answers
18 views

$A = \{{1, … , n\}}$ - How many $(B,C) \in P(A) \times P(A)$ are there such that $B \cap \overline{C} = \emptyset$?

$A = \{{1, ... , n\}}$ How many $(B,C) \in P(A) \times P(A)$ are there such that $B \cap \overline{C} = \emptyset$ ? I got to the conclusion that it must be $\sum\limits_{k=0}^{n}2^k$ because for ...
0
votes
1answer
26 views

Number of n-tuples, whose elements <=than q, sum up to k

Given $X^q_n=\{1,...,q\}^n$, with $q<n$, whose elements are the n-tuples $x = (x_1, ..., x_n)$, I would like to find an explicit formula for $$|V_k^n|$$ where $$V_k^n = \{ x \in X^q_n ...
2
votes
0answers
19 views

Proving number of partitions of $n$ to $3$ parts at most.

I have an exercise, to prove that the number of partitions of $n$ to at most $3$ integers is $\frac{(n+3)^2}{12}$ rounded. I tried to prove by induction but I don't know how.
2
votes
3answers
28 views

In how many ways can you order in line the letters of the word $AAABBCDEFG$

In how many ways can you order in line the letters of the word $AAABBCDEFG$ , such that $A$ or $E$ will be the first letter? I'm thinking there are $2$ options for the first letter ($E$ or $A$) and ...
3
votes
2answers
29 views

How many pairs are in $(B,C) \in P(A) \times P(A)$ such that $B \subseteq C$

I'm trying to solve this problem: Let $A = \{1,2,3,\ldots,n \}$ How many pairs are in $(B,C) \in P(A) \times P(A)$ such that $B \subseteq C$ I want to solve this using combinatorics, Basically what ...
0
votes
0answers
7 views

Count options for sitting people om a bench [duplicate]

I have this combinatoric question which I can't figure out. In how many ways can we sit 12 men and 12 women on a bench where no 2 women sit next to each other. The answer is : $ 13! \cdot 12! $ but my ...
2
votes
0answers
18 views

Factorization of permutations into two factors with fixed number of cycles, plus a placement condition

I have asked this question in MathOverflow, but it received no answers, so I am posting it here. In my recent work I have been led to consider the following type of permutation factorizations. Let ...
0
votes
3answers
47 views

How many non-negative integer solutions are there for the equation $x+y+z = 11$ when $x \geq 1$, $y \geq 2$, and $z \geq 3$?

So, if $x+y+z=11$, and $x \ge 1, y \ge 2$, and $z \ge 3$, how many non negative integer solutions can it have? So far, I did the math this way: $C(10 + (3-1),10) = C(12,10)$ for $x$ being at least ...