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)

3
votes
4answers
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$
0
votes
0answers
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 ...
2
votes
2answers
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....
3
votes
3answers
140 views

Coefficient of $x^{41}$ in $(x^5 + x^6 + x^7 + x^8 + x^9)^5$

What is the coefficient of coefficient of $x^{41}$ in $(x^5 + x^6 + x^7 + x^8 + x^9)^5$? Using summation of G.P., this is equivalent to finding the coefficient of $x^{41}$ in $$\left(x^5 \left(\...
7
votes
1answer
38 views

The size of sets of positive integers not having distinct subsets with equal size and sum

Let us call a set $S$ of positive integers "good" if there does not exist a pair of distinct subsets $A,B\subseteq S$ who have equal size and an equal sum. Equivalently, a set $S$ is good if the ...
2
votes
2answers
71 views

Show that $\sum_{k=0}^n \frac{(2n)!}{{k!^2(n-k)!}^2}= \binom{2n}{n}^2$

Show that $$\sum_{k=0}^n \frac{(2n)!}{k!^2(n-k)!^2} = \binom{2n}{n}^2.$$ I tried canceling $2n!$ from both sides then moving $k!$ to right but still not sure how to proceed.
9
votes
2answers
276 views

Counting: how many ways of climbing a stair?

You are climbing a staircase. At each step, you can either make $1$ step climb, or make $2$ steps climb. Say a staircase of height of $3$. You can climb in $3$ ways $(1-1-1,\ 1-2,\ 2-1)$. Say a ...
1
vote
4answers
51 views

Probability: 5 cards drawn at random from a well-shuffled pack of 52 cards [closed]

A poker hand consists of 5 cards drawn at random from a well-shuffled pack of 52 cards. Then, the probability that a poker hand consists of a pair and a triple of equal face values (for example, 2 ...
3
votes
1answer
32 views

Why am I under-counting when calculating the probability of a full house?

I was trying to answer this question. Find the probability of getting a full house from a $52$ card deck. That is, find the probability of picking a pair of cards with the same rank (face value), ...
0
votes
1answer
466 views

About permutation with repeated identical elements.

First up, I do know the general solution but somehow am unable to use it to solve this kind of problem. I am simply lost. The problem is like this: ...
0
votes
1answer
22 views

Can any simple graph be “super edge labeled”?

Let $X=(V(X),E(X))$ be a simple graph with $|V(X)|=n$ and $|E(X)|=m$. Let $$f:V(X) \bigcup E(X)\rightarrow \{1,2,3,\ldots ,n+m\}$$ be a bijection, such that for all $x,y \in V(X)$ and $\{x,y\} \in E(X)...
2
votes
5answers
354 views

Packing $8$ identical DVDs into $5$ indistinguishable boxes

I am trying to solve this question: How many ways are there to pack eight identical DVDs into five indistinguishable boxes so that each box contains at least one DVD? I am very lost at trying to ...
3
votes
0answers
65 views

Counting number of bases in a set of vectors with spanning constraint

I am interested in a good bound for the following problem: Suppose $S = \{ v_1, \dots, v_n \}$ is a set of vectors where $v_i \in \mathbb{R}^r$ for $i = 1, \dots, n$. Suppose further that any ...
3
votes
1answer
67 views

Problem 48 in A First Course in Probability

I have an issue with problem 48 Chapter 2, page 51 in Sheldon Ross' A First Course in Probability (9th edition). The problem is as follows, Given 20 people, what is the probability that among the 12 ...
8
votes
2answers
5k views

Inductive Proof for Vandermonde's Identity?

I am reading up on Vandermonde's Identity, and so far I have found proofs for the identity using combinatorics, sets, and other methods. However, I am trying to find a proof that utilizes mathematical ...
1
vote
2answers
45 views

Probability problem with a die

I've been practicing probability problems lately and I came to this problem A number is formed in the following way. You throw a six-sided die until you get a 6 or until you have thrown it three ...
2
votes
1answer
33 views

How to find that a number is a sum of multiple of different numbers?

Suppose a product comes in packs of 3, and 5, and a customer demands 8 quantities of that ...
2
votes
1answer
24 views

Transposal generators like {1, 1, 2, 3, 3, 2}

The sequence {1, 1, 2, 3, 3, 2} generates all the transposals of {1,2,3}. Just cyclically pick positions $n, n+2, n+4$. Is there a sequence like this for 1-4, 1-5, and so on?
4
votes
2answers
64 views

How many distinct ways are there to $2$-color the $8$ vertices of a cube?

How many distinct ways are there to $2$-color the $8$ vertices of a cube, with colorings only considered distinct up to rotation?
9
votes
1answer
106 views

Prove that $\dfrac{b^{n-1}a(a+b)(a+2b)\cdots(a+(n-1)b)}{n!}$ is an integer

Let $a$ and $b$ be integers and $n$ a positive integer. Prove that $$\dfrac{b^{n-1}a(a+b)(a+2b)\cdots(a+(n-1)b)}{n!}$$ is an integer. Define $v_p(x)$ such that if $v_p(x) = n$, then $p^n \mid x$ but ...
0
votes
3answers
55 views

N is a four digit number. If the leftmost digit is removed, the resulting three digit number is 1/9th of N. How many such N are possible? [closed]

N is a four digit number. If the leftmost digit is removed, the resulting three digit number is 1/9th of N. How many such N are possible with solution?
1
vote
1answer
40 views

How many ways are there to pick k cards in a game of Skat?

In a game of Skat there are 4 suits (spades, hearts, diamonds, clubs) and 8 values (7, 8, 9, 10, jack, queen, king, ace) yielding 32 cards altogether. I'm trying to figure out in how many ways $k \geq ...
0
votes
2answers
28 views

Probabilities in infinite Bernoulli type of series

While I was trying to solve the 1st problem from here I run into the following problem: find the probability of the events such as $1122213$ or $2122111116$ in infinite series of dice rolls which end ...
1
vote
1answer
540 views

How to calculate the cardinality of the intersection of three sets?

I have a universe (or total number of people polled who are distributed amongst these sets) of $151$ persons. These sets correspond to which TV shows they watch (i.e., each set represents one TV show)...
0
votes
1answer
27 views

Unique integer solutions to $\sum\limits_{i=1}^n a_i = A$ when $l \leq a \leq u$ and $a,A,l,u \in \mathbb{N}$

I'm trying to find a analytical way for finding the total amount of unique solutions to equation: $$\sum\limits_{i=1}^n a_i = A, \text{when } l \leq a \leq u,$$ where $a,A,l,u \in \mathbb{N}$. For ...
1
vote
4answers
54 views

Circular permutation probability

A circular table has $9$ chairs that $4$ people can sit down randomly. What is the probability for no two people sitting next to each other? My current idea is to calculate the other probability, ...
0
votes
1answer
35 views

Permutation: Number of ways 4 cars could park

I came across this question in my Algebra textbook: Find the number of ways 4 cars could park right next to each other if the parking slots were: a) in a straight row b) in a circular ...
0
votes
2answers
32 views

How many ways can numbers be split into different groups

If I had the numbers [2,2,2,2,3,3] and I wanted to find the number of ways to split them into two groups, then how would I do it. I know that if I had all different numbers eg.[1,2,3,4,5,6] then I ...
0
votes
2answers
70 views

Four people are rolling a die once. What is the probability of $2$ people getting the same number?

I am doing as following- $1^{st}$ people get a number from any $6$ number in $6$ ways, $2^{nd}$ people get a different number from rest of $5$ in $5$ ways, $3^{rd}$ people get another different ...
4
votes
2answers
85 views

How many integers $\leq N$ are divisible by $2,3$ but not divisible by their powers?

How many integers in the range $\leq N$ are divisible by both $2$ and $3$ but are not divisible by whole powers $>1$ of $2$ and $3$ i.e. not divisible by $2^2,3^2, 2^3,3^3, \ldots ?$ I hope by ...
2
votes
1answer
53 views

How many different 4 letter words can be selected from the word ADVANCED?

My attempt : $A-2 , D -2 , V - 1, N -1 , C -1 , E -1 $ $XXXX$ words $=0 $ $XXXY$ words $=0 $ $XXYY$ words $= \binom{2}{2}\times \frac{4!}{2!2!} = 6$ $XXYZ$ words $= \binom{2}{1}\times \binom{5}{...
2
votes
0answers
40 views

Finding only the number of unlabeled graphs on $n$ vertices

I know that it is possible to find the number of unlabelled graphs on $n$ vertices using Polya's theorem, but you get a horrible sum. This also tells you much more: it gives you the number of ...
1
vote
1answer
56 views

Combinatorial question relating to zero sets of ideals

Let $R$ be a ring and $I$ an ideal of $R[x_1,\ldots,x_n]$. Then define the Zariski closed set $$V=\{x\in R^n:f(x)=0\text{ for all }f\in I\}.$$ I'm interested in the quantity $$p(f)=\frac{|\{x\in V:f(x)...
2
votes
2answers
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
2answers
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?
2
votes
0answers
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 \...
1
vote
0answers
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. ...
1
vote
4answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
26 views

Counting solutions by estimating Fourier coefficients

In W. T. Gower's essay The Two Cultures of Mathematics, he mentions the following as an example of a 'general principle' in combinatorics: "If one is counting solutions, inside a given set, to a ...
2
votes
0answers
34 views

Minimum least common multiplier for variable combinations

I looking to find the minimum possible value of the LCM of a variable set of integers. My hypotheses are the following: I have a set $N$ of $n$ integers, all different. My integers are bounded by $...
0
votes
0answers
31 views

Applications of tensor product of graphs (modelling of Internet Graphs)

I was going through the book Handbook of Product Graphs, by Richard Hammack, Wilfried Imrich, Sandi Klavžar. Somewhere in book, they mentioned the following lines : One of the applications of tensor ...
0
votes
1answer
27 views

In how many ways can 10 different things be distributed to 4 persons if 2 are to receive 2 things and the others are to receive 3 things?

I have no idea how to answer this question, I did a lot of research on trying to figure it out but every answer is so different. I would prefer something along the lines of using combinations and ...
-1
votes
2answers
52 views

find the number of permutations of the letters of the word ANTENNA taken 4 at a time? [closed]

I understand how to get the permutation of the word itself, but what does the "taken 4 at a time" mean?
-3
votes
1answer
22 views

How many possible combinations can be made of two characters from $62$ characters?

I want to make combinations to create an encryption system. Can you please tell me how to calculate how many possible combinations can be made of two characters from $62$ characters. Characters are A-...
6
votes
1answer
465 views

Finding the maximum number of subspaces of a vector space over finite field that satisfy these relations

I have a question and I am stuck. I was wondering if anyone has a thought, before I start a brute-force search. For $q$ a prime number and $n =6$, let $\mathbb {F}_{q}^{n}$ be an $n$-dimensional ...