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

Sum of product with primes

Let $b=e_1e_2,\ldots,e_n$ and $b'=e'_1e'_2,\ldots,e'_n$ be two distinct bit strings of equal length $n$ with same number of occurrences of zeros and ones. The bit string $b$ and $b'$ also must have ...
0
votes
2answers
41 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
25 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, $$ $$ ...
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 ...
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
48 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.
1
vote
1answer
28 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 ...
8
votes
2answers
182 views

$\binom{2p-1}{p-1}\equiv 1\pmod{\! p^2}$ implies $\binom{ap}{bp}\equiv\binom{a}{b}\pmod{\! p^2}$; where $p>3$ is a prime?

From $\binom{2p-1}{p-1}\equiv 1\pmod{\! p^2}$ how does one get $\binom{ap}{bp}\equiv\binom{a}{b}\pmod{\! p^2},\,\forall a,b \in \mathbb N,\, a>b$; where $p>3$ is a prime ?
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 ...
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 ...
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
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 ...
1
vote
1answer
36 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?
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 ...
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
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). ...
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
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
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 ...
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
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 ...
3
votes
0answers
61 views

'Randomness' of inverses of $(\mathbb{Z}/p \mathbb{Z})^\times$

Suppose you are given the group $(\mathbb{Z} / p \mathbb{Z})^{\times}$, where $p$ is prime. Let $A_p$ denote the sequence whose $j$th element is the inverse of $[j]$. For instance, if $p = 7$, the ...
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 ...
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 ...
-1
votes
3answers
44 views

Given 26 balls - 8 yellow, 7 red and 11 white - how many ways are there to select 12 of them?

I'm interested in knowing and understanding the solution to the following problem: given 26 balls - 8 yellow, 7 red and 11 white - how many ways are there to select 12 of them (all balls of the same ...
2
votes
3answers
25 views

Show that one cannot make a 8×8 square using 15 T-tetrominoes and 1 square tetromino

Show that one cannot make a 8×8 square using 15 T-tetrominoes and 1 square tetromino. Its a coloring problem. Unable to solve. please help.
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
votes
2answers
22 views

I need your help for this simple statistics problem.

I need help for the following problem: In a summer reading program for youth, there is a six week period where the seven Harry Potter books are available. (1)If only three books can be read during ...
1
vote
1answer
24 views

Prove there's a simple path of length $k$ in a simple graph $G$ where all the vertices have degree of at least $k$

Prove there's a simple path of length $k$ in a simple graph $G$ where all the vertices have degree of at least $k$. My attempt: Induction, for $k=1$ it's obvious. Suppose for $k-1$ and we'll ...
1
vote
0answers
28 views

How is Wythoff's Theorem proved?

Specifically, how does one prove the following? Suppose $(a,b)$ is not of the form $(A_n,B_n)$, where $A_n=\lfloor n \phi \rfloor$ and $B_n= \lfloor n \phi^2 \rfloor$. Then there is a move in ...
0
votes
0answers
25 views

How many closed knight's tour are possible in a $8\times 8$ chessboard? [duplicate]

How many closed knight's tour are possible in a $8\times 8$ chessboard? I hae no such idea. Please give me the proof of it.
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 ...
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
0answers
21 views

How do I prove that Ramsey Number r(3,6)=18?

How do I prove that Ramsey Number r(3,6)=18 ? I've tried doing so directly by showing there are 9 red vertices and 7 blue ones, and then divided to cases, but is there an easier, more direct way than ...
1
vote
2answers
21 views

Permutation with constrained repetititons

The question is as follows: How many ways can 12 identical white and 12 identical black pawns be placed on the black squares of an 8 x 8 chessboard My answer was $\frac{32!}{12!*12!}$ But the ...
0
votes
0answers
11 views

The image of a a vector in the edge space when multiplied by it's incidence matrix.

Consider a graph $G=(V,E)$ and it's incidence matrix $M$. Let $\textbf{x}$ be the characteristic vector for a standard basis vector in $\mathcal{E}$ (a vector corresponding to the one element edges ...
0
votes
1answer
43 views

$\frac{(-1)^n}{2\cdot 4\cdot \cdot\cdot2n}=\frac{(-1)^n}{2^n\cdot n!}$

$$\frac{(-1)^n}{2\cdot 4\cdot \cdot\cdot2n}=\frac{(-1)^n}{2^n\cdot n!}$$ $$\frac{(-1)^n}{3\cdot 5\cdot \cdot \cdot(2n+1)}=\frac{{(-2)^n} \cdot n! }{(2n+1)!}$$ can anyone tell me if these are true or ...
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 ...
2
votes
2answers
128 views

Why is ${n\choose k}$ is always a product of the primes of $n$ for all $n>k$? [closed]

Let $n, k$ be two positive integers such that $n>k$. Why is ${n\choose k}$ always divisible by a prime dividing $n$ (or even a product of such primes)? Please help me understand why. I cannot seem ...
-3
votes
0answers
15 views

Partially ordered sets - Exercise [duplicate]

I got this question and I'd be happy if someone could help figure it out.. http://i.imgur.com/jmt1wtM.png Thanks!
0
votes
1answer
85 views

Tournament Graphs

Given a partially ordered set (i.e. poset) $P$, let $PC(P)$ be the smallest number of chains that cover all the elements of $P$ . Let $PC'(P)$ be the smallest number of pairwise disjoint chains that ...
1
vote
0answers
15 views

Rook Polynomials with Symmetrical Overlap (Count Permutations Restricted by Distance)

Consider the cardinality $P(n,d)$ of permutations where elements can move up to distance $d$; for example, the permutation $\binom{012}{102}$ with $d = 1$ would be valid but $\binom{012}{201}$ would ...
6
votes
0answers
69 views

A bound on the nth prime.

Is there any combinatorial argument to show that the nth prime $p_n = \mathcal{O}(n^k)$ for fixed $k$ ? There is a problem in the book by Apostol to find upper bounds on $p_n$, the Prime Number ...
1
vote
1answer
93 views

Prove or disprove: for every P we have PC(P) = PC'(P)

Given a partially ordered set (i.e. poset) $P$, let $PC(P)$ be the smallest number of chains that cover all the elements of $P$ . Let $PC'(P)$ be the smallest number of pairwise disjoint chains that ...
-2
votes
0answers
34 views

Combinarics, number of chains of specific subsets [duplicate]

Let n be even integer and m odd integer. a sequence of m sets S1,..,Sm in [n] ([n]={1,...,n}) is called super chain if: 1.S1 contained in S2 contained in S3 ... contained in Sm 2.for every i s.t. ...
1
vote
0answers
130 views

Assume n is an even integer. For an odd integer m, a sequence of m sets S1,…,Sm ⊆ [n] is a graceful chain of length m if…

Assume $n$ is an even integer. For an odd integer $m$, a sequence of $m$ sets $S_1, \dots, S_m \subseteq [n]$ is a graceful chain of length $m$ if: $S_1 \subset S_2 \subset \dots \subset S_m$ For ...