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

90 views

### Find the coefficient of $x^{12}$ in $(1-x^2)^{-5}$

Find the coefficient of $x^{12}$ in $(1-x^2)^{-5}$ What can be said for $x^{17}$ Tried $\frac{1}{(1-x^2)^{5}}$=$\sum_{n=0}^\infty \binom{n+5-1}{n}x^n$ not sure that i can do that with $x^2$
18 views

### enumerating polyominos

Polyominoes are made by gluing together finitely many squares along their edges. They always have connected interiors, but are allowed to have holes. Enumerating polyominoes is a huge subject, and ...
68 views

### every tree $T$ has at most one perfect matching, alternative proof

I have two questions: I need to know if the following approach (by induction) is correct. The ones I saw use induction on the components of $T$ with a leaf removed, I did something a little different....
140 views

67 views

### What is the rank of COCHIN

Is there any shortcut method for finding the rank of the word COCHIN? I mean is there any shortcut method for finding the rank of a word having repeated letters. For example there is a shortcut method ...
51 views

### Is there symbol to denote a combination and permutation?

For example, let's say I wanted to denote any arbitrary, $2$ number combination of the letters, A, B and C. So you can have AB, AC, and BC. Say you wanted a way to represent any given combination, is ...
67 views

### Number of ways two matrices can be multiplied?

Given the dimensions of two matrices what are the different ways they can be multiplied? Example $A[2][2]$ and $B[2][2]$ then answer is $2$. Let the dimensions of first matrix be $n \times m$ and ...
455 views

### Recursive random draw

Let $R(n)$ be a random draw of integers between $0$ and $n − 1$ (inclusive). I repeatedly apply $R$, starting at $10^{100}$. What’s the expected number of repeated applications until I get zero?
51 views

### lower bound for sum of distinct n-th roots of unity

Given a positive integer $n$, define $\zeta = e^{2\pi i/n}$ and define $s: \mathbb Z^n \to \mathbb C$$s(\vec x) = \sum_{k=0}^{n-1} x_k \zeta^k$$ Let us consider the set$S = \{ |s(\vec x)| : \vec x \...
39 views

### Maximal chains in posets under homomorphisms

Suppose that $P$ and $Q$ are two posets and $f:P\to Q$ is a homomorphism (a.k.a., $f(x)\le f(y)$ whenever $x\le y$). Given a chain $C\subset P$, the image $f(C)$ automatically is a chain as well. ...
84 views

### Closed form of recurrence relation $F(n) = 2 + F(n-1) + F(n-2)$

I was figuring out an answer to the question, How many Boolean arrays of length $n$ could be formed if there are to be no two falses in a row? I could see that it boils down to a Fibonacci ...
24 views

### Plaid in generic position. Counting faces.

I write $\pi_n$ to denote a group of $n$ parallel lines. Consider a family of $(\pi_1,\pi_2,\ldots,\pi_s)$ parallel groups each with $(n_1,n_2,\ldots,n_s)$ parallel lines. Arrange the family of ...
39 views

### Optimization Algorithm for Combining Nodes on a Graph

Graph before and after clustering nodes $R_1$ and $R_2$ In the picture linked above, I have a graph with nodes $R_1$ through $R_5$ and vertices linking them. All the vertices are weighted 10 in this ...
403 views

### Probability when a professor distributes a quiz and homework assignment to a class of n students.

Need help with this problem. Suppose our lazy professor collects a quiz and a homework assignment from a class of n students one day, then distributes both the quizzes and the homework assignments ...