This tag is for basic 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)

4
votes
3answers
131 views

Help with this combinatorial proof $\sum\limits_{k=1}^nk^2(k-1){n\choose k}^2 = n^2(n-1){2n-3\choose n-2}$ considering $n\ge2$

$\displaystyle\sum\limits_{k=1}^nk^2(k-1){n\choose k}^2 = n^2(n-1) {2n-3\choose n-2}$ considering $n\ge2$ Can somebody help with this combinatorial proof? I'm struggling a lot. Thanks. EDIT: Ok. ...
1
vote
1answer
20 views

Placing between n and n+2 different books into n different boxes

The homework question asks: There are n (for integers $n>1$) different boxes, each of which can hold up to $n+2$ books. Find the probability that: a) No box is empty when $n$ different ...
0
votes
2answers
44 views

What subject in mathematics investigates the type of problems that constitute the LSAT “logic games” (example given)?

For my own curiosity, I read part of an LSAT study guide yesterday. The "logic games" section comprised questions like, An advertising executive must schedule the advertising during a particular ...
0
votes
2answers
46 views

How find this $\max{|A|}$ if $A=\{S_{i}|S_{i}\equiv 1\pmod 2\}$

let $(a_{1},a_{2},\cdots,a_{2014})$ be a permutation of $(1,2,3,\cdots,2014)$,and define $$S_{k}=a_{1}+a_{2}+\cdots+a_{k},k=1,2,3,\cdots,2014$$ Find the $\max{|A|}$, where ...
0
votes
2answers
40 views

Combinatorics-Generating function

5 pirates find 3000 gold coins. In how many ways they can distribute them, if the captain gets at least 500 and not more then 2000 coins. the rest get at least 150 but not more then 1000 coins.(each ...
1
vote
1answer
37 views

Counting triangles in triangular graphs

A triangular graph $T_n$ is the line graph of the complete graph $K_n$ (see for example here). Can you derive a formula for the number of triangles in the triangular graph $T_n$? If not, can you at ...
4
votes
4answers
773 views

Fewest number of moves to win the game 2048?

I'm trying to figure out the fewest number of moves one could make to win the game 2048. In another thread, someone placed the figure at 520, but I'm wondering if anyone knows how to mathematically ...
1
vote
0answers
27 views

Finite sum identity involving Stirling numbers

I was given the following identities (note: $s_{n,k},S_{n,k}$ are the Stirling numbers of first and second kind respectively): (1) $s_{n+1,k+1}=\sum_{i=k}^{n}\binom{i}{k}s_{n,i}$ (2) ...
0
votes
2answers
71 views

How many students like none of the toppings? (Principle of Inclusion - Exclusion)

There are 17 students. 11 students like one pizza topping 7 students like two of the toppings 4 students like 3 of the toppings 2 students like 4 of the toppings 1 students likes all of the toppings ...
0
votes
0answers
31 views

How many ways can this quadrilateral be formed if no two of its vertices are next to each other?

A quadrilateral is formed by joining four vertices of a convex decagon. In how many ways can such a quadrilateral be formed if no two of its vertices are next to each other (that is, no two vertices ...
1
vote
0answers
19 views

Rearanging people so that no one is in the same spot

I am not sure how to approach this problem: "n people are seated in numbered chairs 1 to n. Let the number of ways the people can be reseated so that no one is in the same chair as before be N. Show ...
0
votes
1answer
28 views

Number of configurations in a constrained nested loops and configuration back from serial

Consider 4 counters looping the digits 0, 1, 2 to form the various "configurations", like in : ...
0
votes
1answer
18 views

Number of ways of arranging 7 coloured blocks in patterns

The question goes: Given you have 7 differently coloured blocks (red, orange, yellow, green, blue, indigo, violet), how many different arrangements are there such that the blue and green are not ...
0
votes
1answer
17 views

Bound the Number of Acute-angled Triangles

I encounter the following problem with solution. But I do not quite understand the argument for 5, 10 points and eventually 100 points. Can someone elucidate the details? Problem In a plane there ...
4
votes
1answer
103 views

Probability of cycles of length at most $g$ in a random graph

I am working on a homework problem. The essence of it is as follows: Fix some integer $g$, a probability $p\in [0,1]$, and a linear function $f(n)$, where $n$ is the number of vertices of a random ...
0
votes
0answers
19 views

closed form of a specific crazy summation?

How can I find the closed form of $f_2 + f_4 + ...+ f_{2m}$ where $\sum\limits_{m=1}^\infty f_{2m} = u_{2m-2}- u_{2m} $ where $u_{2m} = \binom{2m}{m} 2^{-(2m)}$ and $u_{2m-2} = \binom{2m-2}{m-1} ...
1
vote
2answers
422 views

Minimizing Gender Regularity in a linear arrangement of boys and girls

Let us consider that there are G girl students and B boy students in a class, we need to arrange them in a single row, but arrangement of students should be in order to minimize the gender ...
0
votes
0answers
21 views

Find Sum of series

Find Sum of series - $$ C^n_k + C^n_{k+t} + C^n_{k+2t} + C^n_{k+3t} + ... C^n_{k+qt} $$ Here $$ k+q\cdot t \le n $$ $$ q\ge 0 $$ $$ k \le n $$
1
vote
0answers
30 views

Simple problem in probability

You have 100 lightbulbs. Every lightbulb is either functioning or not. You test 20 of them, and all of the 20 are functioning. What is the probability that 10 of the 100 lightbulbs do not function? ...
0
votes
1answer
46 views

Summation of product of combinations

my question is, can the following series be solved $$ \sum_{i,j}^{} {a\choose i} {b \choose j} $$ where, (i+j) mod 3 =0 or i+j is multiple of 3 I need a generalized solution, i.e variables i,j,k... ...
1
vote
1answer
39 views

How to prove a set must have a specific number of elements?

Trying to understand sets but having a hard time. Could someone help me through this one? Let A be a set of six positive integers each of which is less than 13. Show that there must be two distinct ...
0
votes
2answers
45 views

Two sequences $a$ and $b$ for which $\Delta a_n = \Delta b _n$

Find two different sequences $a$ and $b$ for which $\Delta a_n = \Delta b_n$ for all of $n$. This is my first time doing recurrence relations, so if anyone could provide some thorough and clear ...
0
votes
1answer
40 views

Differences Exponential and Ordinary Generating Functions

I am trying to understand conceptually the differences between ordinary generating functions (OGF$=1+x+x^2+\ldots$ ) and exponential generating functions (EGF$=1+x+\frac{x^2}{2!}+\ldots$ ) when it ...
1
vote
0answers
33 views

Special case coefficient sum in multinomial equation

I need to find the sum of coefficients of $x^{c}$ in the general equation $(1+x)^{a_1}(1+x^2)^{a_2}...(1+x^m)^{a_m}$, where $c$ is a multiple of $m+1$. For example in $(1+x)^2(1+x^2)$ the ...
3
votes
2answers
84 views

Deriving a (tricky, I think?) recurrence relation

I'm having trouble trying to derive a recurrence relation for a problem I'm looking at. "Let $h_n$ be the number of ways of packing a bag with $n$ fruits (either apples, oranges, bananas, or pears), ...
2
votes
1answer
34 views

counting vector pairs with a given hamming distance

Let $\mathbb{F}_2$ denote the binary field. For integer $t\geq 0$, define $W_t = \{(x,y)\in \mathbb{F}_2^n\times \mathbb{F}_2^n: d_H(x,y)=t\}$, where $d_H(\cdot,\cdot)$ denotes the Hamming distance. ...
1
vote
0answers
42 views

Arranging Peoples In A Row

Why when we need to put 2 people together we calculate them as one unit and not two? They have 2 ways to sit one near the other, but why we reduce just 1 from the overall number of peoples?
0
votes
2answers
72 views

Grasshopper in a tropical forest

There is a Grasshopper in a tropical forest. The grasshopper can jump only vertically and horizontally, and the length of the jump is always equal to x centimeters. A Grassshopper has found herself at ...
1
vote
2answers
35 views

How many ways are there to pick 18 letters from 12 A's and 12 B's?

How many ways are there to pick 12 letters from 12 A's and 12 B's? How many ways are there to pick 18 letters from 12 A's and 12 B's?
1
vote
1answer
68 views

The complexity of counting solutions to $x_1 + \dots + x_m = N$ in non-negative integers under constraints

Consider the equation $$x_1 + \dots + x_m = N$$ where $x_1,\dots,x_m \ge 0$ and under the additional constraints $x_k \le a_k$ for $k=1,2,\dots,m$. I'm interested in knowing whether the number of ...
0
votes
1answer
42 views

How many symmetric and transitive relations are there on ${1,2,3}$?

I'm trying to count the number of relations on ${1,2,3}$ that are symmetric and transitive. I know how to count the symmetric relations but I can't seem to find the method for this one. I've counted ...
7
votes
2answers
34 views

The proof of $|I_X|=\frac{n!}{|\text{Aut}(X)|}$

Suppose $X$ is a graph with a set $V$ of vertices and $|V|=n$. $I_X$ is the isomorphy class of $X$ and $\text{Aut}(X)$ is the automorphism group of $X$. How can I prove the formula $$ ...
4
votes
0answers
76 views

How to prove this indentity $\binom{100}{0}^2-\binom{100}{1}^2+\binom{100}{2}^2-…-\binom{100}{99}^2+\binom{100}{100}^2=\binom{100}{50}$ [duplicate]

I don't know how to prove this identity: $\binom{100}{0}^2-\binom{100}{1}^2+\binom{100}{2}^2-\binom{100}{3}^2+...-\binom{100}{99}^2+\binom{100}{100}^2=\binom{100}{50}$
2
votes
1answer
40 views

How do you handle this kind of probability?

What is the probability of selecting a singular matrix from $\Bbb{R}^{3\times 3}$? I calculated it to be zero based on their being approximately $9$ degrees of freedom to choose entries of $A$ such ...
1
vote
2answers
65 views

Use generating functions to find the number of partitions of $n>1$ that have an odd number of even parts $k=1,…,10$

Here are some examples where we find $f(n)$ - the number of partitions that satisfy our condition: $\boldsymbol{2} = (1+1) \rightarrow \boldsymbol{f(2)=0} $ $\boldsymbol{3} = (1+1+1) = ...
4
votes
1answer
75 views

Proving a combinatorial identity “directly”

This is a homework problem. In the first part of the problem, I managed to use a combinatorial problem to prove the following identity: $\Sigma_{k=0}^{n}(-1)^k {2n-k \choose k} 2^{2n-2k} = 2n+1$ But ...
0
votes
1answer
26 views

Inclusion Exclusion Principle Question

A merchant have 3 kinds of coins in his pocket: r of copper, s of aluminum and t of gold. He randomly take out 3 coins from his pocket. how much combinations there are in which he will pull 3 coins ...
0
votes
2answers
23 views

Minimum of Maximum of Addition of two vectors/arrays

Suppose you have two arrays and you want to compute the maximum of the addition of the two arrays. Now you move the second array one field to the right. Now you can compute the maximum again of the ...
0
votes
2answers
214 views

What is the probability of of drawing at least 1 queen, 2 kings and 3 aces in a 9 card draw of a standard 52 card deck?

The title problem is just one specific example of a more generalized problem that I'm trying to solve. I'm trying to write an efficient algorithm for calculating the probability of at least k ...
1
vote
1answer
28 views

Number [n,k]-linear codes with one fixed vector

I need to find the number of $[n,k]$-linear binary codes with one fixed codeword x (non zero) in it. So I guess, I need to count the number of $k$-dimensional ...
5
votes
3answers
81 views

How many sequences of numbers $\{a_1…a_5\}$ where $a_i \in \{1…25\}$ satisfy $a_{i+1} \leq a_i + 2$

Here's how it looks: 1 1 1 1 1 1 1 1 1 2 1 1 1 1 3 1 1 1 2 1 1 1 1 2 2 1 1 1 2 3 1 1 1 2 4 1 1 1 3 1 ......... 25 25 25 25 24 25 25 25 25 25 Counting sequences ...
1
vote
1answer
49 views

How many random cards picks with replacement are required?

You pick 1 card from a standard deck of 52 cards. Then put it back in, and pick a card again. Then put it back in and pick a card. etc... How many times do you have to repeat in order to have ...
1
vote
2answers
26 views

$K$ events that are $(K-1)$-wise Independent but not Mutually/Fully Independent

I had the following question: Construct a probability space $(\Omega,P)$ and $k$ events, each with probability $\frac12$, that are $(k-1)$-wise, but not fully independent. Make the sample space as ...
0
votes
0answers
57 views

Proportional growing number set $\mathbb{X}\subset\mathbb{N}$

1. Question: Is there such a set of numbers $\mathbb{X}\subset\mathbb{N}$, in which the proportion of product and sum of all natural numbers $n\in \mathbb{N}$ grow proportional? $$\begin{equation*} ...
0
votes
0answers
19 views

finding the least non-zero of a multivariable polynomial

Let $P(x_1,x_2,...,x_m)$ be a homogeneous polynomial of degree n, with integers coefficients. How can you find the least* $a=(a_1,a_2,...,a_m)$, where $a_i$ are positive integers and $P(a)!\neq 0$? ...
1
vote
0answers
14 views

Generalized permutahedron and random polytopes

The Birkhoff polytope $B_n$ is defined as the convex hull of the set of permutation matrices, which gives us the set of doubly stochastic matrices. A concept which is intimately related is that of the ...
1
vote
1answer
26 views

Partitioning N people into N/2 sized groups across N - 1 days

Problem Statement: Given a list of $N$ people. On the 1st day, divide them into $N/2$ groups of two people each. On the 2nd day, divide them into groups of two again... Do this every day, until day ...
0
votes
1answer
57 views

Number of seating arrangements in 5 cars

An exercise from Introductory Combinatorics by Richard A.Brualdi: A roller coaster has five cars, each containing four seats, two in front and two in back. There are 20 people ready for a ride. ...
1
vote
0answers
56 views

Number of paths in a grid

A common puzzle problem is to count the number of paths that start from the bottom-left-hand corner of a grid and end at the top-right hand corner, with the restriction that you can only move upwards ...
5
votes
1answer
212 views

Is there a name for this problem I can search for approaches on

I have a collection of a collection of numbers that I need to find the smallest number of groups to put them into whereas the distinct set of numbers in each set does not exceed a threshold. For ...