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
1answer
43 views

How many $3$-of-a-kinds are possible if one ace is missing?

So I know how to do the simpler 'How many $3$-of-a-kinds are possible' question - it has been asked on here multiple times too. But what if say an Ace is missing. How would you go about starting the ...
1
vote
1answer
40 views

Proving that between each pair of vertices there is a path length $2$ at most

Let $G=(V,E)$ be a graph with $n$ vertices such that $\forall v,w\in V$ that doesn't have a common edge we have: $\text{deg}(v)+\text{deg}(w)\ge n-1$. Prove that for each pair of vertices ...
1
vote
0answers
60 views

Why is combinatorics not a part of the Tripos? [migrated]

I do not officially study mathematics, so I always rely on what's on the internet. Specifically, I follow the schedules of the Tripos – the math program at Cambridge, supposedly one of the most ...
7
votes
2answers
483 views

In how many ways can 1500 be resolved into two factors?

In how many ways can 1500 be resolved into two factors? Is there a formula for that or a smart way because if I do that by listing all the divisors of 1500 it will take a lot of time.
2
votes
0answers
91 views

The amazing lift.

I would like to ask for a program to efficiently calculate how a lift should fetch the people who need it. Most of us use lifts (or elevators) but maybe it could be programmed to be faster! Or can it? ...
0
votes
1answer
14 views

Question about use of pigeonhole principle to show that there are at least 3 common neighbors to two vertices

Let $G$ be a simple graph such that $|V|\ge 5$, also $x,y$ are vertices that aren't adjacent. Prove that if $d(x),d(y)\ge \frac {n+1}2$, then $x,y$ has at least $3$ common neighbors. My attempt: ...
4
votes
1answer
45 views

Bijection $f$ of $\mathbb{N}$ such that $n$ divides $\sum_{k=1}^{n} f(k)$

Is it possible to construct a bijection $f: \mathbb{N} \mapsto \mathbb{N}$ such that $n$ divides $\sum_{k=1}^{n} f(k)$ for every $n \in \mathbb{N}$? At first, I've tried to construct such ...
5
votes
3answers
328 views

proof of formula and calculation sum

Show that following formula is true: $$ \sum_{i=0}^{[n/2]}(-1)^i (n-2i)^n{n \choose i}=2^{n-1}n! $$ Using formula calculate $$ \sum_{i=0}^n(2i-n)^p{p \choose i} $$
19
votes
4answers
568 views

A three variable binomial coefficient identity

I found the following problem while working through Richard Stanley's Bijective Proof Problems (Page 5, Problem 16). It asks for a combinatorial proof of the following: $$ \sum_{i+j+k=n} ...
0
votes
0answers
50 views

on subset of items in ordered list would like to calculate cardinality of set of orderings grouped by kendall tau distance

Let's say I have an ordered list of length $n$ which I will denote $12\ldots n$. There are $n!$ ways to rearrange the items in this list. Take a subset of the items in the list $B\subset ...
6
votes
1answer
75 views

Combinatorial Interpretation of these two identities

Currently, I am trying to prove the following two identities, which arose as a result of my other question in the Math StackExchange recently: \begin{equation} ...
0
votes
1answer
19 views

Generating function for $2n$ distinct balls to $n$ bins such that each bin will hold exactly two balls

Find the number of ways for having $2n$ distinct balls in $n$ distinct bins such that each bin will hold exactly two balls using a generating function The generating function (exponential) would ...
0
votes
2answers
480 views

number of ways to divide an array into m sets of equal sum

I recently came across this question: Find the number of ways to divide and array into m subarrays of equal sum? Ex: given a[]= {1, 1, 2, 3, 4, 5}, m= 2 ...
1
vote
2answers
368 views

ln how manyways can we distribute $7$ apples and $6$ oranges among $4$ children so that each child gets at least one apple.

In how many ways can we distribute $7$ apples and $6$ oranges among $4$ children so that each child gets at least one apple? I think this can be solved by using permutations because the word ...
2
votes
3answers
76 views

Number of n-words such that a and b are not neighbors.

Question:How many n-words from the alphabet {a,b,c,d} are such that a and b are never neighbors? 1.There are $4^n$ ways to arrange the four letters. 2.There are $(n-1)$$2^{n-1}$ ways of ...
0
votes
2answers
40 views

Find coefficient of $X^{12}$

I need to find coefficient of $X^{12}$ in $({1-2X})^{19}$. What is the formula to solve it?I only know about $$\frac{1}{a-X}=\frac{1}{a}\sum_{r=0}^\infty \frac{X^r}{a^r}$$ ...
0
votes
1answer
15 views

Recurrence relation for ways to color a circle with two colors such that there can't be two adjacent reds

Find the recurrence relation for how many ways there are to color a carousel with a circumference of length $n$ with two colors, red and blue such that no two reds will be adjacent This is like ...
2
votes
0answers
24 views

Find simple proofs of the two $q$-series identities

When I read an article, I found the following two $q$-series identities very interesting $$ \sum_{k=-\infty}^{+\infty}(-1)^k{2n\brack n+2k}q^{2k^2}=(-q;q^2)_n, $$ $$ ...
2
votes
2answers
34 views

Proof of Number of: *permutations of ‘n’ things, taken ‘r’ at a time, when ‘m’ specified things always come together*

I read below at many sources Number of permutations of ‘n’ things, taken ‘r’ at a time, when ‘m’ specified things always come together =$ m!  * (n-m+1) !$ However no one gave the proof. I ...
0
votes
1answer
61 views

Ways to have exactly $n$ nominees out of $2n$ voters

There are $2n$ voters, each write his name on a paper as the voter and the name of his nominee. How many ways there are such that there are exactly $n$ different nominees and each of the nominees ...
0
votes
5answers
88 views

$\sum_{i=0}^n {2n \choose 2i} = 2^{2n-1}$

$$ \sum_{i=0}^n {2n \choose 2i} = 2^{2n-1} $$ I know what this sum is supposed to equal. I also have a hint that I am supposed to use ${n \choose r} = {n-1 \choose r-1} + {n-1 \choose r}$ I was ...
8
votes
1answer
141 views

Meeting of people.

In a group of k people, some are acquainted with each other and some are not. There are two rooms for dinner. Every person chooses to stay in that room, in which he has an even number of ...
0
votes
1answer
47 views

Combinatorial proof for $\sum_{k = 0}^n \binom {r+k} k = \binom {r + n + 1} n$ [duplicate]

I'm trying to figure out a combinatorial proof for: $$\displaystyle \sum_{k \mathop = 0}^n \binom {r+k} k = \binom {r + n + 1} n$$ I've tried the committee counting thing, but that didn't work.
2
votes
0answers
30 views

An art gallery problem

An art gallery has the shape of a simple $n$-gon. Find the minimum number of watchmen needed to survey the building, no matter how complicated its shape be. I failed to solve the problem. Please help ...
1
vote
0answers
17 views

Hamming weight intersection probability

Given $s,t\in(0,1)$, $c>1$, $n\in\Bbb N$, pick ${n^t}$ random vectors $\{v_i\}_{i=1}^{{n^t}}$ such that each $v_i\in\{x\in\{0,1\}^{2^n}:|x|_{hamming}={2^{n-n^s}}\}$. Denote $v_j\cap v_j$ to be ...
1
vote
1answer
24 views

How does this solution involve counting surjective functions?

I recently had the following question, which I answered incorrectly, in a combinatorics exam: How many ways are there to put 8 balls in 9 holes $H_1, ..., H_9$ if the balls are all different and only ...
0
votes
1answer
33 views

what is the number of pairs of partitions of fixed length with a fixed number of like elements

Given a labeling of the set of partitions of $n$ with $k\leq n$ parts (numbering choose$(n,k)$), and comparing all pairs of partitions from this set (numbering choose$(n,k)^2$ since we allow a ...
1
vote
0answers
63 views

Coding probability?

Given $s,t\in(0,1)$, $c>1$, $n\in\Bbb N$, pick $2^{n^t}$ random vectors $\{v_i\}_{i=1}^{2^{n^t}}$ such that each $v_i\in\{x\in\{0,1\}^{2^n}:|x|_{hamming}={2^{n-n^s}}\}$. If $v_i^\perp$ is ...
1
vote
1answer
27 views

Good Reason for Partitions Indexing Symmetric Functions?

I'm mostly unfamiliar with the study of symmetric functions. However, it's my understanding that: We are interested in, as a basic object, the vector spaces $\Lambda_n$ of symmetric polynomials in ...
0
votes
1answer
28 views

Combinations of two character alphanumeric - how many [closed]

For some reason I cannot find this answer on Google, and I am not good enough in this particular area to figure it out on my own. Using the alphabet, letters $A$-$Z$, and the numbers $0$-$9$, how ...
0
votes
1answer
39 views

Cutting the Plane

Into how many parts at most is a plane cut by $n$ lines? Into how many parts is space divided by $n$ planes in general position? My approach: $$p(n+1)=p(n)+n+1$$ $$s(n+1)=s(n)+p(n)$$ This solution ...
0
votes
3answers
6k views

How to use simple examples to explain $^nC_r$ and $^nP_r$.

What I mean is not how to use $^nC_r$, $^nP_r$. I want examples to explain why $^nC_r$ = $\frac{n!}{r!(n-r)!}$ and $^nP_r$ = $\frac{n!}{(n-r)!}$
6
votes
5answers
221 views

Is this combinatorial identity a special case of Saalschutz's theroem?

When I solved a question, the following combinatorial identity was used $$ \sum_{k=0}^{n}(-1)^k{n\choose k}{n+k\choose k}{k\choose j}=(-1)^n{n\choose j}{n+j\choose j}. $$ But to prove this identity is ...
0
votes
2answers
39 views

Expressing the expected value in a simpler form

We randomly set numbers $(1, 2,\ldots, n)$ in the sequence $(a_1,\dots,a_n)$. Let $N$ be the largest number such that for $2 \le k \le N$ we have $a_k>a_{k-1}$. Find $\mathbb{E}N.$ Lets start ...
4
votes
1answer
68 views

Combinatorial interpretation of identity

I recently came across the identity $$\sum_{k=0}^m\dbinom{m}{k}\cdot \frac{(-1)^k}{n+k+1}=\dfrac{n!\cdot m!}{(n+m+1)!},$$ while working on evaluating $$\int_0^1 x^n(1-x)^m\, dx.$$ I ended up ...
1
vote
2answers
43 views

The number of cases $(0, 0)$ moves by either $(1,1)$ or $(1,-1)$, in $2n$ steps, without touching $x$-axis again.

I was solving combinatorics problems when I ran into this shady statement: The number of cases $(0, 0)$ moves by either $(1, 1)$ or $(1, -1)$, in $2n$ steps, without touching $x$-axis again is ...
0
votes
1answer
42 views

Show $ \left\lfloor\frac{2n}{p} \right\rfloor - 2 \left\lfloor \frac{n}{p} \right\rfloor \in \{ 0, 1 \}$

I conjecture that $$ \left\lfloor\frac{2n}{p} \right\rfloor - 2 \left\lfloor \frac{n}{p} \right\rfloor \in \{ 0, 1 \}. $$ I know that it is always nonnegative, and equals $1$ for $n < p \le 2n$, ...
3
votes
0answers
16 views

Expectation of longest monotonic segment of a permutation

Consider for any $p \in P(n)$, the permutation group of order $n$, the function $L(p)$ defined as the length of the longest monotonic segment in $p$. By this I mean that $$L(p) \geq k ...
0
votes
1answer
333 views

Probability of picking exactly one correct from a pool of 6 incorrect and 4 correct

So as the question says. You have 6 incorrect objects and 4 correct ones. What are the odds that, when picking 3 of them at random, you end up with exactly one of them being correct. This seems to be ...
1
vote
0answers
41 views

Finding a closed form expression for $\sum_{k=\frac {n+2} 2} ^n \binom n k$

Find a closed expression for $\displaystyle\sum_{k=\frac {n+2} 2} ^n \binom n k$, $n$ is even. My attempt: $(1+1)^n = \displaystyle\sum_{k=0} ^ n \binom n k= \sum_{k=0} ^{\frac {n-2} 2}\binom n ...
8
votes
2answers
181 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 ...
0
votes
1answer
298 views

Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
4
votes
2answers
66 views

Graphs with 12 edges over the vertices $\{1,2,…,12\}$ have two vertices with a degree of 5

How many graphs with 12 edges over the vertices $\{1,2,...,12\}$ have two vertices with a degree of 5? The two vertices aren't neighbours: $\binom {10} 2 \binom 85 ^2 \binom {\binom 82} 2$. ...
1
vote
1answer
84 views

Arrange the number

Consider this sequence {1, 2, 3 ... N}, as an initial sequence of first N natural numbers. You can rearrange this sequence in many ways. There will be a total of N! arrangements. You have to calculate ...
0
votes
1answer
50 views

Another olympiad question related to External principle (regarding geometry problem)

Into how many parts at most is a plane cut by $n$ lines? (b) Into how many parts is space divided by $n$ planes in general position First i was thinking about the approach (not able to find it). ...
1
vote
1answer
34 views

Ways to buy marbles (Arrangement)

A boy wishes to buy exactly six marbles. There are four different colours of marbles available. In how many ways can he buy the six marbles?
0
votes
2answers
38 views

Explanation for solution of a combinatorial problem

The given problem is: An ordinary deck of cards is dealt to four people: Joe, Bob, Jim, and Larry. If Larry has exactly one ace, what is the probability that Jim has all the remaining aces? My ...
1
vote
1answer
47 views

Why do the probabilities not match?

I came up with this problem myself: There is a deck of 52 playing cards. A hand contains 5 of them. You pull a hand from deck. What is the probability of no Queens in it? You pull a hand from deck. ...
0
votes
0answers
120 views

Arrow’s Theorem

Suppose $k ≥ 3$ Recall that Arrow’s Theorem shows that any function $F:(S_k)^n\to S_k$ (the input is composed of n permutation of $[k]$ and the outcome is a single permutation of $[k]$ that satisfies ...
0
votes
2answers
17 views

How many unique combinations you can have when pairing 17 designs into a 7 set?

Following situation: You have 17 designs for a packing box and you want to create a set where you put 7 of them into box. The sort is not important, but the set has to be unique and no double designs ...