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)

1
vote
0answers
35 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
48 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
41 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
39 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
50 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
128 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
208 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
82 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
33 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
25 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 ...
0
votes
2answers
54 views

Division n items into k boxes prove that it is NP-Complete

I don't know how to solve this problem. Can anyone help me with it please? I need to prove that this is a NP-complete problem. We are given $n$ items with sizes $s_1, s_2, ... ,s_n$, where $0 < ...
-1
votes
1answer
16 views

Self-avoiding walks from one diagonal to the other on $mxn$ lattice is ${m+n \choose m,n} $

According to wikipedia "self-avoiding walks from one end of a diagonal to the other, with only moves in the positive direction, there are exactly $$ \binom{n+m}{n,m} $$paths for an $m × n$ ...
0
votes
5answers
83 views

How many triplets $(x,y,z)$ can we make with $x,y,z\in\{1,\ldots,25\}$, where $x\leq y\leq z$? [closed]

The numbers $x$, $y$ and $z$ are chosen from the set of $\{1,2,3,\ldots,25\}$ such that $z\geq y\geq x$. In how many different ways can we from such triplets?
1
vote
0answers
47 views

How to use sub-pattern frequencies to calculate the authenticity the main pattern

I'm trying to determine the probability that something is real by comparing the frequency of the sub-permutations it contains. Here is an example: You want to guess whether or not a random symbol is ...
3
votes
3answers
62 views

Five people have applied for three different positions in a store. In how many ways can the positions be filled?

Five people have applied for three different positions in a store. If each person is qualified for each position, in how many ways can the positions be filled? Can someone tell me if I have to ...
1
vote
0answers
29 views

Smallest set of n-digit, base-m numerals containing every digit assignment to any 2 places?

I am interested in whether this is a familiar problem (I know it's a problem of familiar types, such as a set cover problem). To put the problem in the subject line another way, for a set $M$ with ...
0
votes
0answers
20 views

Monovariant problem

The problem is stated as follows: $200$ people are in a circle and have a real number assigned to them, such that the absolute difference of $2$ neighboring values is between $1$ and $3$ and the sum ...
0
votes
1answer
28 views

Three rounds, three bets: how to guarantee a loss of all three rounds

Suppose you are buying tickets for three round of some game. Your ticket must have three bets on it before the first round starts. Your three options for each round are for a win, a loss and a draw. ...