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
2answers
17 views

How many different ways can a pitcher throw $3$ pitches when warming up with $12$ pitches

A pitcher has three pitches, a fastball, a curveball, and a knuckleball. When warming up he wants to throw $3$ fastballs, $5$ curveballs, and $4$ knuckleballs. How many different ways can he throw ...
0
votes
0answers
18 views

number of times a sum can be made with three numbers

we are given 4 numbers A, B, C and K with the condition A,B,C >=K. We need to find the sum ...
1
vote
0answers
29 views

Can this sum over the q-Pochhammer symbol be simplified?

While considering the problem of the expected value of a dice fixing strategy on a two-sided die that comes up as $1$ with a probability of $\alpha$ and $0$ otherwise. I was studying the strategy ...
1
vote
2answers
57 views

number of cylces in a graph

Consider a connected graph with e edges and v vertices, let x = e - v for a given x what are the maximum and minimum number of cycles a graph can have? Examples: x = 0 the maximum number of cycles ...
2
votes
1answer
20 views

How to schedule n jobs on two machines so that their order of execution remains same on both machines?

There are n jobs that have to be scheduled. Each job requires operations on two machines. For reasons of control, the order in which the jobs are processed on the two machines is the same so what is ...
0
votes
1answer
52 views

Count the number of non-isomorphic 6-regular graphs on 9 vertices.

I know there will be 9 vertices of degree 6, which means there are 54 edges. But then how will I figure out the number of non-isomorphic graphs?
2
votes
0answers
19 views

Bijective mapping between face polytopes of permutohedra and partitions of integers

The OEIS entries A019538, A049019, and A133314, relate a refinement of the face polynomials of the permutohedra (A049019) to partition polynomials (A133314) defined by multiplicative inversion of an ...
0
votes
2answers
34 views

Number of possible team combinations

The baseball team is made up of 7 girls and 8 boys. There are 9 people on the field at the same time in a baseball game. If at least four of the people on the field must be girls, how many different ...
1
vote
0answers
34 views

Number of ways to form N as the sum of array elements?

I have given an Array A containing M elements and i also given two numbers N and K . Now i have to find the number of ways to represent N as the sum of different elements of A but exactly K elements ...
0
votes
1answer
25 views

Combinatorics of vectors in plus minus 1

How many vectors of length n are there with entries in {-1,+1} such that the sum of all entries from 1 to k is positive for all k between 1 and n.
1
vote
0answers
36 views

Combinatorics: Counting Set Partitions with Moebius Function

Let $\pi_n$ be the poset of all set partitions of $\{1,...,n\}$ ordered by refinement, $\sigma = \{B_1,...,B_k\}$ be a set partition with blocks $B_i$, and $max(B_i)$ be the maximum value in the block ...
0
votes
0answers
19 views

Expected value of removing every ball once [duplicate]

I thought of this question and I somehow I can't figure out an answer Let there be a box with $n$ balls (which have numbers from $1$ to $n$ to that you can distinguish them). When we randomly pick a ...
2
votes
1answer
32 views

Probability of a random chair being empty and having a seat to the right which is not empty is $\frac{m(n-m)}{n(n-1)}$

Let there be a round table with $n$ chairs. $m$ people choose their chair (max 1 person per chair) and let $m < n$. I am pretty sure that the probability of a random chair being empty and having a ...
2
votes
0answers
30 views

Properties of transfer matrices and their traces

I'm having difficulties understanding some arguments in my statistical mechanics lecture and would like to make them more rigorous by proving some properties. For the Ising model on a lattice we ...
1
vote
1answer
40 views

How does $\frac{1}{2}(n-s+1)(n-s)$ equal $\binom{n-s+1}{2}$?

Maybe a basic question, but I'm strolling through graph theory at the moment after a few years out of tertiary mathematics. There is a theorem that if a graph $G$ has $s$ connected components, then $$ ...
0
votes
1answer
28 views

How to choose $n$ balls from the bags?

Given $4$ bags A, B, C and D. Bag A contains 'a' number of balls. Bag B contains 'b' number of balls. Bag C contains 'c' number of balls. Bag D contains 'd' number of balls. I have another bag E ...
1
vote
1answer
32 views

Problem with understanding why 2 solutions of a combinatorics task don't give the same result

The task is: In how many ways can we pick 6 people from a group of 4 girls and 6 boys so that there are at least 2 girls? The first solution, which we did in school, is to divide into 3 different ...
1
vote
0answers
27 views

Acute triangle in regular polygon

A regular 2015-gon is partitioned into triangles by a set of non-intersecting diagonals. Prove that among those triangles only one is acute-angled.
0
votes
0answers
21 views

Sum of k-products with some restrictions

We have an array of $n$ DISTINCT numbers $A=\{a_0, a_1, ... ,a_n\}$; $n<60$. We need to find the sum of $k$-products of above numbers with some restrictions. Ex: Sum of 2-product = $\sum_{i=1}^n ...
3
votes
2answers
47 views

Another Hockey Stick Identity

I know this question has been asked before and has been answered here and here. I have a slightly different formulation of the Hockey Stick Identity and would like some help with a combinatorial ...
3
votes
1answer
40 views

Probability of numbers being in A.P.

There are $ 2N + 1 $ cards numbered $1$ to $2N + 1$ . $3$ cards are picked in random without replacement. Find the probability that the numbers in the card are in arithmetic Progression. ...
2
votes
2answers
25 views

Number of non-identity elements of order $7$ in a group

If $x \neq e \in$ group $G$ s.t. $x^7 = e$, then $(x^i)^7 = e$ for all $i \in 1\le i\le $6 implying the number of $x \neq e \in G$ with $x^7 = e$ is $6n$ for any positive integer $n$ ...
0
votes
0answers
18 views

Chessfield problem with chips and neighbourhood restrictions

I have the following problem. You have a chessfield (size: n*n) and you can put an optional number of chips on the field. On every field only one chip is allowed and the chips can have diagonal ...
2
votes
0answers
38 views

Coin Combinatorics: Minimum amount of coins for given value

I was just doing a bit of thinking on coin combinatorics today when I began thinking of this question: You have a set of coins, greater than £2, but you cannot pay someone £2 without needing change. ...
2
votes
3answers
59 views

How many equivalence relation can be defined on a set of $5$?

The question is how many equivalence relation can be defined on a set of $5$? I think this is asking how many different ways can we partition a set of $5$, right? So the answer is $1$ way: ...
3
votes
3answers
43 views

$24$ students arrive in random order to collect shirt, $3$sizes available

$24$ students arrive in random order. $12$ are size $S$ and $12$ are size $M$. There are $24$ T-shirts provided: $10$ are size $S,$ $10$ are size $M,$ and $4$ are size $L.$ A student takes their ...
2
votes
2answers
30 views

$X$ be a non-empty subset of irrational numbers such that sum of any two elements of $X$ is rational ; then is there any upper bound for $|X|$?

Let $X$ be a non-empty subset of irrational numbers such that sum of any two elements of $X$ is rational ; then is there any possible upper bound for the cardinality of $X$ ? Can $X$ be infinite ?( I ...
0
votes
0answers
16 views

Different ways to leave linearly dependent vectors of a set of vectors

Let a set $S=\left\{ {{\mathbf{v}}_{i}}:i\in \mathbb{Z}_{n}^{+} \right\}$, where $\mathbb{Z}_{n}^{+}=\left\{ 1,2,...,n \right\}$ and ${{\mathbf{v}}_{i}}\in {{\mathbb{R}}^{m}}$ for each $i\in ...
0
votes
0answers
48 views

Formula for combinations-

While I was thinking I found this formula: $\binom{n-k}{r-k} + \binom{n-k}{r-k +1} + \binom{n-k}{r-k +2} + ....+ \binom{n-k}{r-k +r}$ Where ...
6
votes
2answers
66 views

number of integer solutions to $2x_1 + x_2 + x_3 = n$

I'm working on a problem for which I need to efficiently compute the number of integer solutions to equations of the form $x_1 + \cdots + x_k = n$ with some subset of $\{x_1, \dots, x_n\}$ equivalent. ...
1
vote
2answers
33 views

Confused about when to use permutations or combinations

How many baseball teams can be formed from 15 players if 3 only pitch and the others play any of the remaining 8 positions? I'm thinking that this is permutations, but my teacher says it is ...
2
votes
1answer
45 views

Stars and Bars with an odd constraint.

Stars and bars is a classic combinatorics question, but I've run into a variant I've never seen before. I have $n$ stars. Rather than group them into piles using $k - 1$ bars, I want to group them ...
3
votes
1answer
108 views

Why is a Pair of Tens better than a Pair of Aces in Texas Hold 'Em?

A couple years ago I developed a program to calculate the optimum betting amount for a round of Texas Hold 'em by using the Kelly criterion. In the process of computing the probability of winning for ...
4
votes
4answers
127 views

Find a generating function for the number of strings

The string $AAABBAAABB$ is a string of ten letters, each of which is $A$ or $B$, that does include the consecutive letters $ABBA$. Determine, with justification, the total number of strings of ten ...
0
votes
1answer
29 views

Coloring points on a circle

On a circle there are $n$, $n \ge 3$ points. In how many ways can we color them in $m$, $m \ge 2$, colors, so that neighbour points have different colors? We shouldn't use all $m$ colors. ...
13
votes
6answers
207 views

How to prove that $\sum_{i=0}^n 2^i\binom{2n-i}{n} = 4^n$.

So I've been struggling with this sum for some time and I just can't figure it out. I tried proving by induction that if the sum above is a $S_n$ then $S_{n+1} = 4S_n$, but I didn't really succeed so ...
1
vote
2answers
80 views

Scheduling gym class

My cousin came to me with this problem yesterday: She has 8 students in her gym class. In tomorrows class she has planned 4 different activities to rotate them through, each of which requires ...
2
votes
2answers
79 views

Number of polynomials which are divisible by $x+1$

Let $a,b,c,d$ be four integers (not necessarily distinct) in the set ${1,2,3,4,5}$ . The number of polynomials $f(x)=x^4+ax^3+bx^2+cx+d$ which are divisible by $x+1$ are: $(A)$ Between 55 and 65 ...
0
votes
2answers
37 views

What does this definition of permutation mean?

A simple question. They give the definition of permutation as "a one to one mapping of the set onto the set of positive integers $\{1, 2,3,4, \ldots n\}$." What does this definition exactly ...
1
vote
1answer
27 views

Permutations acting on coordinates of codewords

Let $\mathcal{C}$ be a binary code of length $n$. The automorphism group of $\mathcal{C}$ is defined to be the set of permutations in $S_n$ that take $\mathcal{C}$ to itself. The text by MacWilliams ...
1
vote
1answer
32 views

Permutation and Combination to find pairs

In how many different ways students can be paired such that no pair consists of 2 boys. Given :- Total students = 10, Girls = 7, boys = 3. What my approach is 3 boys can be paired with 7 girls like ...
2
votes
3answers
51 views

Intuitive explanation of $(1-x)^{-a-1}=\sum_{j=0}^{\infty}{{a+j} \choose j}x^j$

Could anyone please explain me the reasoning behind this formula? $(1-x)^{-a-1}=\sum_{j=0}^{\infty}{{a+j} \choose j}x^j$ Thanks so much!
0
votes
1answer
26 views

How to find the number of faces of a rhombicosadodecahedron?

I need to use the Euler's formula. I know there are $62$ faces...first, how do I find the number of vertices it has. From there, I can get the amount of edges, which will then in turn get me the ...
2
votes
0answers
42 views

Write as a product of integers [closed]

My question is that in how many ways can $10,000!$ be written as the product of $30$ distinct positive integers. My question is similar to this question: In how many ways can $1000000$ be expressed as ...
0
votes
1answer
42 views

Proving binomial identities [duplicate]

Can someone help me prove these two binomial identities using either walks in Pascal's triangle or a committee-selection model? $(1)$ $\qquad$ $\displaystyle\sum_{k=0}^m {m\choose k}{n\choose ...
0
votes
2answers
46 views

Finding expected number coin flips to get 2 consecutive heads [duplicate]

First, I know what the right answer is, and I know how to solve it. What I'm trying to figure out is why I can't get the following process to work. The probability that we get 2 consecutive heads ...
4
votes
2answers
39 views

Must the number of people…

Must the number of people at the party who do not know an odd number of people be even? Describe a graph model and then answers the question. I'm confused because I do not understand the ...
0
votes
5answers
63 views

How many ways to choose $ i,j,k,l$ from $1,\ldots, n$ such that $i<j$ and $k<l$

I am trying to work my way through the proof of Lemma 2 in Broder, A., & Karlin, A. R. (1990). Multilevel Adaptive Hashing. SODA 90 in order to generalise it as explained in a related question. I ...
0
votes
1answer
24 views

Is there an estimate for how much k-element subsets are needed to have any t-element subset in at least one of them?

Let's call $S(t, k, n)$ a minimal number of $k$-element subsets (blocks) of an $n$-element set $S$ with the property that each $t$-element subset of $S$ is contained in at least one block. Are there ...
1
vote
1answer
19 views

Finding a binary column vector that makes all rows distinct

Say I have a collection $\mathcal{M}$ of distinct binary matrices $M_i$, $i = 1, \dots, \binom{k+1}{k-1}$ of size $2^{k-1} \times (k-1)$ where in each $M_i$, all rows are distinct (note: $M_i$ is not ...