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
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 ...
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 ...
3
votes
1answer
76 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
29 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
32 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
10 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
28 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
17 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
45 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
37 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
32 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? [on hold]

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 ...
8
votes
2answers
50 views

Given $n$ points, the difference of $2$ of them is $1/n$ close to an integer

From today's ENS Ulm Math D exam Let $x_1,\ldots,x_n$ be real numbers Prove there exists $i\neq j $ and $h\in \mathbb Z$ such that $|x_i-x_j-h|\leq \frac{1}{n}$ I tried contradiction and ...
0
votes
1answer
26 views

How to show mutually orthogonal latin squares

I have a question concerning mutually orthogonal latin squares (MOLS). Let $ \mathbb F $ be a field of $n\in\mathbb N$ elements. For all $q\in\mathbb F \backslash \{0\}$, define $n\times n $ tables ...
0
votes
2answers
31 views

Why do we divide to remove elements considered equivalent?

Suppose we have a set of $N$ elements, each of which is considered distintic from all others. If we ask ourselves the number of ways to order those $N$ elements the reasoning is based on this: for the ...
2
votes
2answers
45 views

Combinatorial polynomial identity.

Can someone help me make sense of the following expression: $$f(x) = \sum_{k=0}^n (-1)^k {n \choose k} (x - k)^m$$ Where $m$ is an integer. I ran into a special case of it while solving a ...
2
votes
0answers
14 views

Optimal Matching Distance

I'm stuck on problem II.5.9 from Bhatia's Matrix Analysis. The problem is as follows: Let $\{\lambda_1,\dots,\lambda_n\},\{\mu_1,\dots,\mu_n\}$ by two $n$-tuples of complex numbers. Let $$ ...
2
votes
0answers
21 views

Max cut problem

I've just looked at the standard proof using the probabilistic method stating that the max cut problem has a lower bound of $|E|/2$ for any graph $G=(V,E)$. More specifically if $X$ is the random ...
2
votes
1answer
65 views

What is this type of function called? How can I translate it to a different origin?

A factory produces 1 widget per week. A builder builds 1 factory each week. A construction firm trains 1 new builder each week. Partially-produced things do not produce anything. Starting with 1 firm, ...
2
votes
1answer
32 views

Generating function for recurrence in two variables

Given characteristic polynomial for the recurrence in two variables (say $F(x,y)$) $$ (y^2-1)^x $$ and initial values can generating function for $F(x,y)$ be derived? I know how to do it for a ...
-1
votes
1answer
15 views

Problem related to permutations [closed]

I need help with the following question. Can someone please explain as to how such questions should be approached?Thanks ! The number of ways in which six letters can be placed in six directed ...
1
vote
0answers
62 views

Magic square with not distinct numbers

There's a 4x4 magic square: 4 0 1 0 3 0 2 0 0 3 0 2 0 4 0 1 Where 0s are different numbers, 1=1, 2=2, 3=3, 4=4. Only the rows and the columns have the same sum, ...
4
votes
2answers
56 views

Binomial Theorem of Differentiation? [duplicate]

I noticed that $$\frac{d^{n}}{dx^{n}} f(x)g(x)=\sum_{i=0}^n {n \choose i} f^{(i)}(x)g^{(i)}(x)$$ and it's had me scratching for a little bit. It's easy to see how the cross terms add up but can anyone ...
3
votes
1answer
35 views

A result of Erdos: the multiplicative persistence of $n$ is at most $c\ln(\ln n)$

Multiply all the digits of a number $n$ by each other, repeating with the product until a single digit is obtained. The number of steps required is known as the multiplicative persistence of $n$. ...
0
votes
1answer
53 views

Dilworth's theorem

Show that the truth of Dilworth's theorem for two-level posets can be deduced from Hall's theorem. I am not sure how to prove this. A poset $P$ is a two-level poset if it is the union of two ...
33
votes
7answers
5k views

How many scientists can survive?

Yesterday the aliens took 100 scientists from Earth as prisoners. They want to test how smart the humans are. The aliens made 101 headbands, numbered from 1 to 101. On the contest day, they throw ...