# Tagged Questions

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.

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 ...
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 ...
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 ? ...
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 ...
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 ...
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 ...
31 views

### Example of Cycle Notation and Elementary Transpositions.

How does one achieve the yellow box from the the second line of this problem?
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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)$ ...
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 ...
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 ...
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 ...
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$. ...
47 views

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 ...
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 ...
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). ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...