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
65 views

Extended rule of sum/product

Prove that both, the sum and the product principle, can be extended to more than two sets, i.e. show that: Given finite sets $A_1, A_2, ..., A_n$ which are pairwise disjoint, then ...
0
votes
1answer
30 views

Finding probability that the number is 30

Okay I found this one on a test and I am still struggling to solve this so here it goes: A bag contains $50$ tickets numbered $1,2,3,4......50$ of which five are drawn at random and arranged in ...
0
votes
1answer
15 views

Probability of dealer having a same-value card as me in Black Jack

In a game of Black Jack, before any additional cards are given out (so everyone has exactly two cards), what are the chances that the dealer has, say, a King, given that one of my cards is a King ? ...
4
votes
5answers
44k views

The maximum number of nodes in a binary tree of depth $k$ is $2^{k}-1$, $k \geq1$.

I am confused with this statement The maximum number of nodes in a binary tree of depth $k$ is $2^k-1$, $k \geq1$. How come this is true. Lets say I have the following tree ...
2
votes
2answers
68 views

Number of ways to arrange $a,b,c,d$ such that $a$ is not followed immediately by $b$

Can someone explain this solution? The question is: How many ways are there to arrange the letters $a,b,c,d$ such that $a$ is not followed immediately by $b$? The solution is: $4! − 3! = 18$ I ...
1
vote
1answer
130 views

Number of anagrams of 'AABBCCDD' that have no repeated letters.

I am seeking to find the number of anagrams of 'AABBCCDD' (that is strings with 2 A's, 2 B's, 2 C's and 2 D's). That have no repeated letters. So far my thoughts have been to find the total number of ...
1
vote
2answers
31 views
1
vote
3answers
183 views

Pigeonhole principle: Asking the minimum number of students

The question What's the minimum number of students, each of whom comes from one of the 50 states must be enrolled in a university to guarantee that there are at least 100 who come from the same ...
0
votes
0answers
21 views

Enumerate possibilities when choosing exactly one from 5 of 6 subsets

The problem Given an arbitrary number n of sets of possibly different sizes, generate an m-column matrix where the rows describe all possible combinations of elements with one taken from each set. ...
0
votes
2answers
59 views

Deduce formula for $\sum_{j=0}^m {m \choose j}(-1)^j j^{m+1}$

I am working on the following problem: For each $m$ we have found the values of $$\sum_{j=0}^m {m \choose j}(-1)^j p(j)$$ for polynomials of degree at most m. Use a combinatorial story to ...
2
votes
1answer
40 views

Counting and conditional probability

We put $r$ balls in $m$ boxes. What's the probability that box $1$ will have exactly $k$ balls? My guess is $\dfrac{r \choose k}{m^r}$ probability because there are $m^r$ ways of putting the balls ...
0
votes
1answer
44 views

How to create a matrix in Hammersley's proof for Erdős-Szekeres Theorem?

Hammersley gave the following algorithm that proves the theorem. Let a sequence $a_1,a_2,...,a_{n^2+1}$. (a) let $a_1$ start the first column and for $i\ge 1$ (b) if $a_i$ is greater than or equal ...
0
votes
1answer
30 views

How many series in length $n$ above $\{3, 5, 7\}$ there are with “$35$” in?

How many series in length $n$ above $\{3, 5, 7\}$ there are with "$35$" in? I though that we should find a place for "$35$", so there are $n-1$ of these. And then we place "35" there and we just ...
1
vote
0answers
38 views

Simplicial polytope Dehn-Sommerville Equations

Let's suppose we have a polytope P with $dim(P)=d$ and the h vector $ h(P,x)=\sum\limits_{i = 0}^{n} h_ix^{d-i}$ i have to prove that if $h_{k}=h_{d-k}$(simplicial polytope) then $xh(P,x)=h(P,1/x)$ ...
0
votes
1answer
53 views

Recurrence relation of number of sequences with $0,1$ and $2$

$d_n$ represents number of sequences of length $n$ made by $0, 1$ and $2$ that don't contain two consecutive 1 or 2. for example $d_2 = 7$ because valid sequences are $\{00,01,02,10,12,20,21\}$. first ...
2
votes
2answers
118 views

Find the maximum possible value of $\frac{A}{\gcd(A,B)} \text{ where } A={100\choose k} \text{ and } B={100\choose k+3}$ such that $30\leq k\leq70$:

For an integer $30\leq k\leq70$, let $M$ be the maximum possible value of $$\frac{A}{\gcd(A,B)} \text{ where } A={100\choose k} \text{ and } B={100\choose k+3}$$ Find $M \mod 100$. Okay, so ...
3
votes
0answers
58 views

An upper bound for the number of answers of this equation

Let $n$ be a natural number and $p$ a prime number less than or equal to $n$. $$\begin{align} n^2 + 2n &\equiv a \pmod p\\ n^2 + 1 &\equiv b \pmod p \end{align}$$ If $a \lt b$, $p$ is ...
3
votes
4answers
48 views

How many ways can $p+q$ people sit around $2$ circular tables - of sizes $p,q$?

How many ways can $p+q$ people sit around $2$ circular tables - first table of size $p$ and the second of size $q$? My attempt was: First choose one guy for the first table - $p+q\choose1$. ...
4
votes
0answers
47 views

Counting the number of ways to cover $4 \times n$ board with $1 \times 3$ or $3 \times 1$ dominoes

I'm trying to solve the problem described in the title by writing down some recurrent relation for the number of ways $T(n)$. It is not very simple, one can not just say that it is $T(n) = 3 \times ...
1
vote
0answers
51 views

Ball Colouring problem clarification

Before you downvote this for being a duplicate, kindly take cognisance of the face that I don't have enough reputation to comment on the germane answer.I'll attempt to pose my enquiry as a question In ...
1
vote
1answer
58 views

Combinatorial proof of $1=\sum_{i=0}^n{(-1)^i \binom{n}{i} 2^{n-i}}$

I'm searching for a combinatorial proof of the following equality: $$1=\sum_{i=0}^n{(-1)^i \binom{n}{i} 2^{n-i}}$$ It's trivial to show using Newton's binomial theorem: $(-1+2)^n=1$, but I'm ...
2
votes
0answers
56 views

Color the set of integers with four colors

Show that one can color the set of integers with four colors: blue, red, yellow and purple, such that for any four numbers with the same colors $a, b, c, d$ (not necessarily distinct, not all four of ...
0
votes
1answer
26 views

Prove using a combinatorial argument the following statement

$$\binom{n+m}{2} = \binom{m}{2} + \binom{n}{2} + \binom{n}{1}\binom{m}{1}$$ I already proved this algebraically by using the formula for choose, but I don't know what exactly the question means by ...
0
votes
3answers
5k views

How many 3 digit even numbers are there(No Repetition)?

First find numbers ending with 0 So, 1's place-1 10's place-9 100's place-7 (2 digits are already consumed and 0 can't be used) So ...
0
votes
1answer
98 views

Erdős-Szekeres theorem generalized example showing exactness

I am struggling to understand the following example taken from Seidenberg's paper (1959). "A well-known example of a sequence of $mn$ terms like the following: ...
2
votes
1answer
36 views

Let $\vec{a}=\hat{i}+\hat{j}+\hat{k}$ and $\vec{r}=x\hat{i}+y\hat{j}+z\hat{k}$ be a variable vector

Let $\vec{a}=\hat{i}+\hat{j}+\hat{k}$ and $\vec{r}=x\hat{i}+y\hat{j}+z\hat{k}$ be a variable vector such that $\vec{r}.\hat{i},\vec{r}.\hat{j}$ and $\vec{r}.\hat{k}$ be positive integers.If ...
1
vote
0answers
39 views

Finding a Hamiltonian cycle for $Q_4$

A hyper cube $Q_n$ is a graph that have the length-n binary sequences as its vertices. Two vertices are adjacent if they differ in one entry. I found a Hamilton cycle for $Q_3$ as follows $$000 \to ...
1
vote
1answer
32 views

Expression for recurrence relation $a_n$ using exponential generating functions

$a_0 = 2$, $a_n = na_{n - 1} - n!$ for $n \geq 1$. Let $$f(x) = \sum_{n \geq 0}a_n\frac{x^n}{n!}.$$ Multiplying each term in the relation by $\frac{x^n}{n!}$ and summing over values for which the ...
0
votes
0answers
106 views

Out of $513$ nine-digit numbers, there must be two with matching zero positions

Need help figuring this one out, came up in class and I have no idea how to write a proof for this. Prove: Given a collection of 513 Social Security numbers, there must be two that match zeros.
1
vote
1answer
60 views

Prove that a graph is a maximal planar graph if and only if $e = 3v − 6$

Definition: A planar graph with no multi-edges $G$ is called a maximal planar graph if the graph formed by addition of any edge (not already in the $G$) is not planar or the graph is $K_3 $ or $K_4$ ...
1
vote
1answer
283 views

The number of pendant vertices in a tree

Let $T$ be a tree with vertices $\{v_1, v_2, . . . , v_n \}$ for $n \geq 2$. Prove that the number of pendant vertices in $T$ is equal to $$\large{2 + \sum_{v_i,deg(v_i) \geq 3}\big( deg(v_i) - 2 ...
1
vote
1answer
27 views

Using Euler's theorem to calculate the number of edges in a graph

I want to use Euler’s theorem for planar graphs to proof that for a tree $T = (V, E)$ that $|V | = |E| + 1$. Now It's very obvious that a tree is a planar graph since it is connected and there is no ...
1
vote
1answer
39 views

Struggling a bit with Combinatorics Order in which to do this question?

n P 4 = 84 n C 2 Now I'm not even sure if the 84 is multiplying by the N choose 2? I don't understand. Ive done all the practice questions my teacher gave me and this came up on the homework and Ive ...
0
votes
1answer
28 views

Counting permutations in $S_n$ with $k_i$ cycles of length $i$ using Polya's theorem

I had this assignment on counting the number of permutations in $S_n$ with $k_i$ cycles of length $i$. It is pretty easy to find that the answer is $\frac{n!}{1^{k_1}2^{k_2}\cdot\cdot\cdot ...
0
votes
2answers
40 views

Find the coefficient of $x^n$ in $\sqrt{1 - 8x}$.

We know from the extended binomial theorem that the OGF corresponding to the concise expression is $\sum_{k \geqslant 0}{1/2 \choose k}(-8x)^k$. And we need to find the coefficient $x^n$, which is ...
1
vote
1answer
30 views

Dimension of the basis $\{x \otimes y + y \otimes x\}$

I'm trying to prove that the annihilator of $I = \left<x \otimes y - y \otimes x \right>$ is $\left<x \otimes y + y \otimes x \right>$. To do this I am trying to compare dimensions. So if ...
1
vote
0answers
26 views

Initially, I would just like to be pointed in the right direction on this problem involving combinations (I think).

Let's say I want to select individuals to create a musical ensemble consisting of 1 each violin, harp, oboe, and kazoo. I have 4 groups of experienced candidates (with varying quantities of members). ...
0
votes
0answers
20 views

What many associative ways are possible an expression of n variables? [duplicate]

Let's say we have an expression AxBxC and x is associative. Then we can solve it as (AxB)xC or Ax(BxC) i.e 2 ways, similarly for 3 variables, I found 5 ways. How can we find a general formula for n ...
0
votes
2answers
60 views

Why is the constant term in any chromatic polynomial is always zero?

The chromatic polynomial $P(G,\lambda)$ is simply the number of different way in which we can colour a graph $G$ with at-most $\lambda$ different colours. Such that every pair of adjacent vertices ...
3
votes
2answers
159 views

9th grade AMTI question $-$ $65$ bugs on a $9 \times 9$ board

65 bugs are placed at different squares of 9X9 square board. A bug in each moves to a horizontal or vertical adjacent square. No bug makes two horizontal or two vertical moves in succession. Show that ...
1
vote
2answers
156 views

The size of a set of closed intervals with integer endpoints, which are either disjoint or nested

Let $n>1$ be an integer. Let $M$ be a set of closed intervals. Suppose that the endpoints $u$ and $v$ of each interval $[u,v] \in M$ are natural numbers satisfying $1\le u < v \le n$ and ...
0
votes
0answers
9 views

lower bound Tutte polynomial for planar graphs

The Tutte Polynomial $T(G, x, y)$ s a #P-Hard problem except for the hyperbola (x-1)(y-1)=1 and some other specific points. For the case of planar graphs, Dell $\textit{et. al.}$ mention (in the ...
0
votes
1answer
27 views

definition clarification of some special type of graphs

I was going through some families of graph and got introduced to circulant graphs. Got the following link of circulant graphs, but I am unable to get it. What do they mean by the list. Kindly help me ...
0
votes
0answers
41 views

How to divide n distinctive objects into k groups so that each group must have at least one object?

I am just wondering how do we compute the number of ways to divide n distinctive objects into k groups so that each group must have at least one object? For example, I want to divide 11 different ...
0
votes
1answer
63 views

Permuting letters within three-letter substrings of strings over $\{\mathsf{x},\mathsf{y},\mathsf{z}\}$ to yield a target “cyclic string”

Given a string made up of only letters $\mathsf{x}$, $\mathsf{y}$ and $\mathsf{z}$, we need to determine whether it can be changed into a string such that each three-letter substring of the string is ...
2
votes
0answers
34 views

$|x^2-xy-y^2|=1$ implies that $x=\pm F_{n+1},\; y=\pm F_n$

So I've proved that $ A= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \implies A^n= \begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1} \end{pmatrix} $ for Fibonacci numbers $F_i$. I'm ...
0
votes
1answer
27 views

Find the probability of picking a bolt

Okay so I found this one in a textbook I tried solving it but I don't know whether I am not able to understand the question or doing a really silly mistake here it goes:A box contains $100$ bolts and ...
5
votes
1answer
114 views

Matching with probabilistic edges

Consider two sets $A,B$, each with $n$ vertices. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $0.01$, independently of the remaining edges. Is it true that ...
1
vote
1answer
40 views

Combinatorics question involving derangements of elements

If $n$ people put their names in a bag, mix it up, and redraw at random, what is the probability that exactly $i$ people get their names back? I have an expression we learned in class about the number ...
0
votes
1answer
35 views

Summing up the first k elements in a row of pascal's triangle.

I trying to come up with a formula for the number of functions there are that map n boolean variables to a boolean output supposing that the functions are a series of disjunctions of conjunctions with ...