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
0answers
28 views

Number of Unique Permutations of 3 digits (-1,0,1) given a length that match a sum

Say you have a vertical game board of n length (length being number of spaces). And you have a three sided die that has the options: go forward one, go back one, and stay. If you go below or above ...
27
votes
11answers
6k views

How many positive integers $< 1{,}000{,}000$ contain the digit $2$?

How many positive integers less than $1{,}000{,}000$ have the digit $2$ in them? I could determine it by summing it in terms of the number of decimal places, i.e. between $999{,}999$ and ...
4
votes
1answer
642 views

Social Golfer Problem - Quintets

I wrote an article on the Social Golfer Problem, which has questions like: Each day, 16 people play Munchkin in foursomes simultaneously. How many days can they play with no two people playing with ...
0
votes
1answer
23 views

Rectangular stained glass window with different colors

Suppose you have six squares of stained glass, all of different colors, and you would like to make a rectangular stained glass window in the shape of a 2 × 3 grid. How many different ways can you do ...
3
votes
4answers
325 views

An identity involving Stirling numbers of the second kind and binomial coefficients

Need to prove: $$\sum\limits_{k=0}^{n} \binom nk k^r x^k = \sum\limits_{j=0}^{r} \binom nj j! (1+x)^{n-j} x^j S(r,j)$$ where $S (n, k)$ denotes a Stirling number of second kind, the number of ...
1
vote
1answer
51 views

Probability of same birthday

I think I solved this problem but I would like to know if I am right or wrong, I am not quite sure. We assume that the year has 365 days and the birthdays are uniformly distributed. We want to find ...
0
votes
0answers
8 views

Are there any minimum-degree-5 triangulations of the sphere for which every four-coloring consists of six Kempe chains, one for each color-pair?

I'm interested only in triangulations that have no separating triangles (i.e. triangles for which there are vertices both inside and outside the triangle). The 5-regular icosahedron is one. Are ...
3
votes
2answers
477 views

What is the expected number of suits in a hand of 4 cards?

To find the expected number of suits the formula is $E(Num Suits) = 1*P(1 Suit) + 2*P(2 Suit) + 3*P(3 Suit) + 4*P(4 Suit)$ For the probability of getting 4 suits I got ${13 \choose 1}^4 {4 \choose ...
3
votes
1answer
8k views

Programming: find the total possible combinations of three variables?

I have three variables in a programming function, and a 4th variable depends on these. I have to test the dependent variable against all combinations of the three variables: Var A: 2 possible ...
2
votes
1answer
35 views

How to compute coefficients of the Vandermonde polynomial?

I am trying to find the coefficients of the monomials in the expansion of $$\prod_{1\le i < j \le n}^n (x_j - x_i)$$ also known as the Vandermonde determinant. For example, for $n=3$ we have ...
1
vote
3answers
52 views

Expected number of cards drawn before drawing a $4$ or $5$

I'm working on the following problem: Compute the number of expected cards drawn from a standard 52 card deck (without replacement) until a $4$ or $5$ is drawn. I tried to model it using a ...
2
votes
1answer
51 views

Jacobi Identities

Can anyone guide me how can I prove these two identities? a)$$\prod_{n=1}^{\infty}\frac{1-q^{2n}}{1-q^{2n-1}}=\sum^{\infty}_{n=1}q^{n(n+1)/2}$$ b) ...
1
vote
1answer
33 views

How many permutations of [8] have neither 1 nor 2 as fixed points?

I am attempting to understand the probleme des recontres and the principle of inclusion and exclusion. My solution for the question would be: Use ${n \choose k}$ $D_{n-k}$ where D represents the ...
1
vote
1answer
22 views

Combinatorics problem on the size of A+B

Let $A$, $B$ be finite subsets of $\mathbb{Z}$ with $|A|=n$, $|B|=m$. Denote $A+B=\{a+b:a \in A, b \in B\}$. It's fairly easy to show that $|A+B| \geq n+m-1$. My question is: If $|A+B|=n+m-1$, ...
1
vote
1answer
24 views

2 Distributions Questions

How many ordered quadruples $(a,b,c,d)$ satisfy $a+b+c+d=18,$ where $a,b,c,d$ are positive integers? How many ordered quadruples $(a,b,c,d)$ satisfy $$a+b+c+d=18,$$ where $a,b,c,d$ are nonnegative ...
2
votes
4answers
43 views

Find a binomial coefficient, combinatorics

I don't really understand what we are asked to do when we are told to find a binomial coefficient equal to the sum of some combinations, I suppose that in a combinatorial way we must show that the ...
2
votes
1answer
56 views

How do I express, algebraically, this comparison of two sets of sets?

Say I have two sets ($A$ and $B$) containing three sets of the same integers. For example: $A_1 = \left\{{1,2}\right\}$, $A_2 = \left\{{3}\right\}$, $A_3 = \left\{{4,5,6}\right\}$ $B_1 = ...
0
votes
1answer
19 views

Prove an identity with integer partitions

I have already proven this identity: $\prod_i (1+st^i) = 1 + \sum_r \frac{s^rt^{r(r+1)/2}}{(1-t)(1-t^2)\cdots(1-t^r)}$ I expanded the product, grouped the s terms, and then made an argument about ...
1
vote
2answers
40 views

In how many ways

In how many ways can $n$ people split in three groups and then people in each group arrange in row. I need help to solve this. I tried to solve this in following way ...
0
votes
0answers
42 views

How many strings $s^\infty$ with $s$ a string of length $\le k$ on alphabet $\{1,2,…,m\}$?

As a function of $k$ and $m$, say $f(k,m)$, how many strings are of the form $sss... = s^\infty$, where $s$ is a string of finite length $\le k$ on the finite alphabet $\{1,2,...,m\}$? E.g., ...
0
votes
4answers
125 views

Number of ways you can form pairs with a group of people when certain people cannot be paired with each other.

Let's say you have a group of eight people and you want to form them into pairs for group projects. There are $\frac{8!}{4!.2!}$ ways to do it. ($8!$ is the total number of ways $8$ people can be ...
1
vote
2answers
80 views

Number of $r$-sided polygons in $P$ with no common edges

We have a $n$-sided convex polygon $P$. How many $r$-sided polygons $(r<n)$, with its vertices among those of $P$, can be formed such that it has no sides (edges) in common with $P$? I tried ...
0
votes
0answers
46 views

Graph Combinatorics: How many such Graphs are there?

How many $4$-regular graphs exist on $8$ vertices? I found that such a graph can't be disconnectd since if so, then graph can be written as disjoint union of atleast two graphs. $4$ regularity ...
4
votes
1answer
62 views

Number of subgraphs in the ladder graph

Assume you have the usual (in both directions infinite) ladder graph. I can try to provide a picture if needed. Further assume the vertices are labelled and I have one distinct vertex (call it the ...
2
votes
2answers
40 views

At least n Spades in $14$ cards

Standard $52$-card deck. $14$ randomly chosen cards. Total number of Combinations: $C_{52}^{14}$. The question is: what is the probability of having at least $n$ Spades with the dealt $14$ cards? ...
0
votes
1answer
18 views

Edge coloring - Ramsey's Theorem

Before covering Ramsey's Theorem, the book gave the following proposition: If the 2-subsets of a 9-set are colored yellow and green, there is either a yellow 3-set or a green 4-set. Then the ...
0
votes
2answers
35 views

Find minimum and maximum wins required in a $8$ team tournament

In a tournament, there are $8$ teams in total and playing against each other $2$ times. We need to find (-)What is the minimum no of wins required to qualify for the next round? (-)What is the ...
0
votes
1answer
32 views

Is the number of different patterns possible permutations or combinations?

I was given the below question. "Linus is taking a true or false test and seems to be guessing every answer. If there are $20$ questions how many different "patterns" are possible?" I solved this ...
0
votes
0answers
11 views

Need a lower bound for a discrete monotonic distribution

I'm staring at the following expression: $$ \displaystyle \frac{\sum_{i=0}^{n}\sigma_i\left(\sigma_i-\sigma_{i-1}\right) w_i}{\sum_{i=0}^{n} \sigma_i^2}$$ I need to come up with a lower bound to ...
0
votes
0answers
31 views

determine whether a combination number is odd or even

Let $k$ be a given positive integer (fixed). I want to determine whether $$ 2n-k\choose n $$ is even or odd, for each positive integer $n$. Is there any general result? My attempt: Case (1). ...
2
votes
1answer
20 views

What did I do wrong with this combinatorics question?

I was given the following problem. "A teacher wants to choose a captain and vice-captain among 12 volleyball players. In how many ways can she do so?" I tried to solve it by multiplying 12 by 11 ...
2
votes
1answer
26 views

Counting unique states in 3d tic tac toe with 6 moves

I am doing some probability review and came across in interesting question I can't quite figure out how to do. The question is asking for a 3x3x3 tic tac toe board with three players a,b,c with taking ...
6
votes
3answers
274 views

How many permutations

How many permutations $\pi \in S_{2n} $ for which $\exists a\in [2n] $ such that set $\lbrace a,\pi (a),\pi ^2(a),\pi^3(a),... \rbrace $ has exactly $n$ elements. I need help to solve this.
2
votes
4answers
434 views

How many ways are there for $2$ teams to win a best of $7$ series?

Case $1$: $4$ games: Team A wins first $4$ games, team B wins none = $\binom{4}{4}\binom{4}{0}$ Case $2$: $5$ games: Team A wins $4$ games, team B wins one = $\binom{5}{4}\binom{5}{1}-1$...minus $1$ ...
1
vote
0answers
20 views

Methods of solving nonlinear systems of equations derived from combinatorial problem

I'm trying to find a way to generalize the expression of polynomials of degree $n-1$ such that $$ k_1+k_2x+k_3x^2+k_4x^3+\dots+k_nx^{n-1}=\frac ...
1
vote
3answers
32 views

How many different possible expressions can I have?

I have three numbers $a,b$ and $c$ How many different additions can I have ? $a + a + a = 3a$ $a + a + b = 2a + b$ However, $a + b + a =2a + b$ which is the same addition as above so I neglect it. ...
1
vote
2answers
33 views

How many words with letters from the word ABRACADABRA if they must end in a consonant and $d$ must be after $r$.

How many words with letters from the word ABRACADABRA if they must end in a consonant and $d$ must be after $r$. What I did: I have $A:5$ $B:2$ $R:2$ $C:1$ $D:1$ If the words must end in a ...
3
votes
1answer
59 views

Working with finitely presented groups in GAP

This is more of a question specifically about how GAP handles calculations with finitely presented groups rather than about group theory. I have several finite group presentations that I would like ...
2
votes
2answers
45 views

Combinatorial polynomial identity.

Can someone help me make sense of the following expression: $$f(x) = \sum_{k=0}^n (-1)^k {n \choose k} (x - k)^m$$ Where $m$ is an integer. I ran into a special case of it while solving a ...
0
votes
0answers
22 views

Combinatorial identity binomial coefficients [duplicate]

How to prove that $$ \binom{m}{p} = \sum_{j=0}^q \binom{q}{j}\binom{m-q}{p-j}\;?$$
0
votes
1answer
29 views

Counting spanning trees in labelled graphs

I have some troubles with counting spanning trees, it seems completely abstract to me. First one is cycle with n vertices - it's just n, because we can move each number n times like so: ...
4
votes
1answer
77 views

What is this sequence of all permutations with gaps permissible [duplicate]

Let there be a sequence $a_1, a_2, a_3,...,a_n$ that represent some actions that you know are required to solve a problem. However, you do not know what order these actions need to be taken to solve ...
0
votes
1answer
18 views

Mobius Funcions of the posets

For a poset, where $n = 2$ we have that two comparable points $1<2$ so $R = \{(1,1),(1,2),(2,2)\}). \ $ For two incomparable points $R=\{(1,1),(2,2)\} \ $. Now, for $n=4$ we have $1<3, ...
1
vote
0answers
62 views

Magic square with not distinct numbers

There's a 4x4 magic square: 4 0 1 0 3 0 2 0 0 3 0 2 0 4 0 1 Where 0s are different numbers, 1=1, 2=2, 3=3, 4=4. Only the rows and the columns have the same sum, ...
0
votes
1answer
31 views

How many poker hands have exactly two pairs?

I found an interesting solution to the combinatorial question of "How many poker hands have exactly two pairs?" and I cannot figure out (or find) the reasoning of the solution. The answer I found in ...
1
vote
2answers
380 views

Find recurrence relation for ternary strings that don't have substrings 00, 01 and last symbol is not 0

I am preparing for my finals for discrete mathematics and I came across this exercise in textbook. Let $s_{n}$ denote all ternary strings of length $n$, such that any string in $s_{n}$ does not ...
2
votes
1answer
34 views

Set of pairs of options that could be wrong/right

One has a list of n options out of which 2 are incorrect, and guesses can be made by picking a pair of options. After picking a pair as a guess, it is either valid, in which case both of the pair's ...
2
votes
2answers
107 views

Why General Leibniz rule and Newton's Binomial are so similar?

The binomial expansion: $$(x+y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$$ The General Leibniz rule (used as a generalization of the product rule for derivatives): $$(fg)^{(n)} = ...
0
votes
0answers
18 views

Determining Counts of Discrete Objects Using Linear Algebra

I'm teaching myself linear algebra and was able to solve the following question using trial and error, but--how would one setup and solve a question like this using Linear Algebra? I have 32 bills ...
3
votes
2answers
66 views

Counting sequences using Catalan Numbers

Count the number of sequences $a_{1},...,a_{2015}$ such that: $a_{i}\in \{-1,1\}$, and $\sum _{i=1} ^ {2015} a_{i}=7$, and $\sum _{i=1} ^{j} a_i >0$ for every $1\leq j\leq 2015$ I assume we have ...