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
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.
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
35 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 ...
1
vote
1answer
22 views

Combinations and arrangement

Twelve people are to travel by 3 cars, each of which holds four. Find the number of ways in which the party may be divided if two people refuse to travel in the same car. My attempt, I know the ...
2
votes
0answers
46 views

Fill a rectangle with squares

How many ways are there to fill a $m\times n$ rectangles with squares that have integer side lengths. Both $m$ and $n$ are integers.
2
votes
0answers
33 views

Find the probability that between 5 random digits appear two differents.

I have the following exercise; Find the probability that in five random digits appear; a) two differents. My approach was the following. I consider for example the vector $(1,1,1,1,0)$ and noted ...
1
vote
2answers
30 views

Marbles Combinations problem

Martin’s bag of marbles contains two red, three blue and five green marbles. If he reaches in to pick some without looking, how many different selections might he make? I do not know how to ...
3
votes
1answer
34 views

Fixed Point with Permutation

I have this homework question I'm kind of stumped on... "A permutation of the numbers $(1,2,3,\ldots,n)$ is a rearrangement of the numbers in which each number appears exactly once. For example, ...
0
votes
5answers
76 views

If I have 10 different pairs of socks and have washed 10 socks, what are the chances that none will match?

I have 10 pairs of different types of socks. I randomly (let's just assume it was true randomness) washed 10 individual socks. It turns out none of them match! What are the chances of this? I've ...
12
votes
0answers
82 views

Prove a matrix of binomial coefficients over $\mathbb{F}_p$ satisfies $A^3 = I$.

(This problem is problem $1.16$ in Stanley's Enumerative Combinatorics Vol. 1). Let $p$ be a prime, and let $A$ be the matrix $A = \left[\binom{j+k}{k} \right]_{j,k = 0}^{p-1}$, taken over the ...
4
votes
2answers
68 views

Number of graphs such that two sides remain connected after some edges are removed

This problem was actually from a programming problem, but it has more of a math flavor, so I am asking on Math stack exchange! Problem: Initially, you are given a graph as in the first image, ...