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)

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 ...
5
votes
2answers
73 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) ...
2
votes
0answers
74 views
+100

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
36 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
51 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
13 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
125 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
474 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
46 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
60 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 ...
3
votes
1answer
81 views
+200

Optimal scheduling dilemma (A textbook math problem IRL)?

I am trying to solve a scheduling problem for a boys camp. I have 12 teams(A through L), 6 sports for them to play, and 6 periods for them to play in(P1 through P6). ...
1
vote
1answer
31 views

Number of labeled graphs satisfying a degree sequence

Say we have two sequences of integers $d^\text{in}$ and $d^\text{out}$ representing the in- and out-degree sequences of a directed graph. How many (possibly isomorphic) graphs are there that satisfy ...
0
votes
1answer
17 views

Prove an identity with integer partitions

I have already proven this identity: $\prod_i (1+st^i) = 1 + \sum_r \frac{s^rt^{r(r+1)/2}}{(1-t)(1-t^2)\cdots(1-t^r)}$ I expanded the product, grouped the s terms, and then made an argument about ...
1
vote
2answers
40 views

In how many ways

In how many ways can $n$ people split in three groups and then people in each group arrange in row. I need help to solve this. I tried to solve this in following way ...
1
vote
0answers
41 views

Graph Combinatorics: How many such Graphs are there?

How many $4$-regular graphs exist on $8$ vertices? I found that such a graph can't be disconnectd since if so, then graph can be written as disjoint union of atleast two graphs. $4$ regularity ...
2
votes
2answers
36 views

At least n Spades in $14$ cards

Standard $52$-card deck. $14$ randomly chosen cards. Total number of Combinations: $C_{52}^{14}$. The question is: what is the probability of having at least $n$ Spades with the dealt $14$ cards? ...
2
votes
4answers
42 views

Find a binomial coefficient, combinatorics

I don't really understand what we are asked to do when we are told to find a binomial coefficient equal to the sum of some combinations, I suppose that in a combinatorial way we must show that the ...
0
votes
1answer
18 views

Edge coloring - Ramsey's Theorem

Before covering Ramsey's Theorem, the book gave the following proposition: If the 2-subsets of a 9-set are colored yellow and green, there is either a yellow 3-set or a green 4-set. Then the ...
0
votes
2answers
34 views

Find minimum and maximum wins required in a $8$ team tournament

In a tournament, there are $8$ teams in total and playing against each other $2$ times. We need to find (-)What is the minimum no of wins required to qualify for the next round? (-)What is the ...
0
votes
0answers
11 views

Need a lower bound for a discrete monotonic distribution

I'm staring at the following expression: $$ \displaystyle \frac{\sum_{i=0}^{n}\sigma_i\left(\sigma_i-\sigma_{i-1}\right) w_i}{\sum_{i=0}^{n} \sigma_i^2}$$ I need to come up with a lower bound to ...
0
votes
0answers
30 views

determine whether a combination number is odd or even

Let $k$ be a given positive integer (fixed). I want to determine whether $$ 2n-k\choose n $$ is even or odd, for each positive integer $n$. Is there any general result? My attempt: Case (1). ...
2
votes
1answer
20 views

What did I do wrong with this combinatorics question?

I was given the following problem. "A teacher wants to choose a captain and vice-captain among 12 volleyball players. In how many ways can she do so?" I tried to solve it by multiplying 12 by 11 ...
1
vote
0answers
18 views

Methods of solving nonlinear systems of equations derived from combinatorial problem

I'm trying to find a way to generalize the expression of polynomials of degree $n-1$ such that $$ k_1+k_2x+k_3x^2+k_4x^3+\dots+k_nx^{n-1}=\frac ...
1
vote
3answers
31 views

How many different possible expressions can I have?

I have three numbers $a,b$ and $c$ How many different additions can I have ? $a + a + a = 3a$ $a + a + b = 2a + b$ However, $a + b + a =2a + b$ which is the same addition as above so I neglect it. ...
2
votes
1answer
26 views

Counting unique states in 3d tic tac toe with 6 moves

I am doing some probability review and came across in interesting question I can't quite figure out how to do. The question is asking for a 3x3x3 tic tac toe board with three players a,b,c with taking ...
0
votes
1answer
32 views

Is the number of different patterns possible permutations or combinations?

I was given the below question. "Linus is taking a true or false test and seems to be guessing every answer. If there are $20$ questions how many different "patterns" are possible?" I solved this ...
2
votes
1answer
47 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) ...
0
votes
0answers
38 views

How many strings $s^\infty$ with $s$ a string of length $\le k$ on alphabet $\{1,2,…,m\}$?

As a function of $k$ and $m$, say $f(k,m)$, how many strings are of the form $sss... = s^\infty$, where $s$ is a string of finite length $\le k$ on the finite alphabet $\{1,2,...,m\}$? E.g., ...
1
vote
2answers
33 views

How many words with letters from the word ABRACADABRA if they must end in a consonant and $d$ must be after $r$.

How many words with letters from the word ABRACADABRA if they must end in a consonant and $d$ must be after $r$. What I did: I have $A:5$ $B:2$ $R:2$ $C:1$ $D:1$ If the words must end in a ...
0
votes
0answers
21 views

Combinatorial identity binomial coefficients [duplicate]

How to prove that $$ \binom{m}{p} = \sum_{j=0}^q \binom{q}{j}\binom{m-q}{p-j}\;?$$
0
votes
1answer
25 views

Counting spanning trees in labelled graphs

I have some troubles with counting spanning trees, it seems completely abstract to me. First one is cycle with n vertices - it's just n, because we can move each number n times like so: ...
2
votes
1answer
55 views

How do I express, algebraically, this comparison of two sets of sets?

Say I have two sets ($A$ and $B$) containing three sets of the same integers. For example: $A_1 = \left\{{1,2}\right\}$, $A_2 = \left\{{3}\right\}$, $A_3 = \left\{{4,5,6}\right\}$ $B_1 = ...
0
votes
1answer
30 views

How many poker hands have exactly two pairs?

I found an interesting solution to the combinatorial question of "How many poker hands have exactly two pairs?" and I cannot figure out (or find) the reasoning of the solution. The answer I found in ...
2
votes
1answer
33 views

Set of pairs of options that could be wrong/right

One has a list of n options out of which 2 are incorrect, and guesses can be made by picking a pair of options. After picking a pair as a guess, it is either valid, in which case both of the pair's ...
0
votes
1answer
18 views

Mobius Funcions of the posets

For a poset, where $n = 2$ we have that two comparable points $1<2$ so $R = \{(1,1),(1,2),(2,2)\}). \ $ For two incomparable points $R=\{(1,1),(2,2)\} \ $. Now, for $n=4$ we have $1<3, ...
0
votes
0answers
17 views

Determining Counts of Discrete Objects Using Linear Algebra

I'm teaching myself linear algebra and was able to solve the following question using trial and error, but--how would one setup and solve a question like this using Linear Algebra? I have 32 bills ...
0
votes
0answers
17 views

How to fill number of positions with given operators? [closed]

We have 4 position between 5 numbers ....and 3 operators (+,*,/) to fill this position... for example 1_2_10_15_25 we can have 1+2*10*15/25 or 1+2+10+15+25 (Repetition of any operator is allowed) ...
1
vote
0answers
25 views

question regarding edge space

Given a graph $G=(V,E)$ and it's edges space $\mathcal{E}(G)$ in the book by Diestel it defines given two edges sets $F,F'$ and their coefficients $\lambda_{1},...,\lambda_{m}$ and ...